Małego Twierdzenia Fermata. nie należy mylić z tzw. Wielkim Twierdzeniem Fermata, które frapowało matematyków przez wiele stuleci i zostało ostatecznie udowodnione przez Andrew Wiles'a w 1994 roku.
Zgodnie ze swoim zwyczajem, podobnie jak i w przypadku Wielkiego Twierdzenia, Fermat przedstawił Małe Twierdzenie, nie podając dowodu. List, w którym się po raz pierwszy pojawiła ta teza, później nazwana Małym Twierdzeniem Fermata, został napisany dnia 18.IX.1640. Fermat dodał komentarz: "Propozycja ta jest prawdziwa dla wszystkich liczb pierwszych; jej dowód prześlę Ci, jeśli nie będzie zbyt długi". Pierwszy znany dowód tego twierdzenia przedstawił Leibniz w 1683 roku.
Twierdzenie 11.9 [Małe Twierdzenie Fermata]
Dla dowolnej \( p \) liczby pierwszej i dowolnego \( a \) zachodzi:
\( a^p\ \equiv_{p}a . \)
Dowód
Poznamy trzy różne dowody. Najpierw jednak zauważmy, że bez straty ogólności możemy przyjąć iż \( a\in{\{ {0,\ldots,p-1} \} } \), gdyż w miejsce \( a \) możemy rozważać resztę z dzielenia \( a \) przez \( p \). Ponadto, zwróćmy uwagę, iż dla \( a=0 \) teza jest oczywista, natomiast dla \( a\in{\{ {1,\ldots,p-1} \} } \) wystarczy udowodnić, że:
\( a^{p-1}\ \equiv_{p}1 . \)
Pierwszy dowód. Dla \( a\in{\{ {1,\ldots,p-1} \} } \) rozważmy ciąg
\( a_0, a_1, a_2,\ldots, a_{p-1} \)
reszt \( a_k = ka \ {\sf mod} \ p \) liczb \( ka \) modulo \( p \). Pokażemy, że żadna wartość w tym ciągu się nie powtarza. Niech \( 0\leq i < j < p \) i, dla dowodu niewprost, niech
\( ia\ \equiv_{p}ja . \)
Wtedy \( p|(j-i)a \). Ponieważ \( p \) jest liczba pierwszą to \( p|j-i \) lub \( p|a \). Ponieważ jednak obie liczby \( a \) oraz \( j-i \) leżą w zbiorze \( {\{ {1,2,\ldots,p-1} \} } \), żaden z tych dwu przypadków nie jest możliwy. A zatem \( {\{ {a_0, a_1, a_2,\ldots, a_{p-1}} \} }= {\{ {0,1,2,\ldots,p-1} \} } \). Oczywiście \( a_0=0 \), więc iloczyny pozostałych elementów w tych dwu zbiorach muszą być równe, co daje:
\( a\cdot 2a\cdot\ldots\cdot(p-1)a \equiv_p a_1 \cdot a_ 2\cdot\ldots\cdot a_{p-1} = 1\cdot2\cdot\ldots\cdot(p-1), \)
lub inaczej:
\( (p-1)! \cdot a^{p-1} \equiv_p (p-1)!. \)
Ponieważ \( p \) jest liczbą pierwszą, wszystkie liczby ze zbioru \( {\{ {1,\ldots,p-1} \} } \) są względnie pierwsze z \( p \), więc i \( (p-1)!\perp p \). Można więc zastosować regułę skracania:
\( a^{p-1}\ \equiv_{p}1 . \)
Drugi dowód. Dla dowodu indukcyjnego względem \( a=0,1,2,\ldots,p-1 \) zauważmy najpierw, że w oczywisty sposób \( 0^p\ \equiv_{p}0 \) oraz \( 1^p\ \equiv_{p}1 \) i załóżmy, że \( k^p\ \equiv_{p}k \). Aby udowodnić, że:
\( (k+1)^p\ \equiv_{p}k+1 \)
pokażemy znacznie mocniejszą równość
\( (x+y)^p\ \equiv_{p}x^p+y^p , \)
która przy \( x=k \) i \( y=1 \) pozwoli zakończyć dowód indukcyjny.
Rozwijając dwumian \( (x+y)^p \) mamy:
\( \displaystyle (x+y)^p=\sum_{i=0}^p{p\choose i}x^iy^{p-i}. \)
Współczynnik \( {p\choose i}=\frac{p!}{i!(p-i)!} \) jest zawsze liczbą całkowitą. Ponadto, jeśli \( 0 < i < p \), to wszystkie czynniki obu silni mianownika są względnie pierwsze z \( p \), bo \( p \) jest pierwsza, a czynniki te są mniejsze niż \( p \). Oznacza to, iż w rozkładzie \( {p\choose i} \) na czynniki pierwsze musi znaleźć się \( p \). To zaś implikuje \( {p\choose i}\ \equiv_{p}0 \) dla \( 0 < i < p \). A więc
\( \displaystyle (x+y)^p =\sum_{i=0}^p{p\choose i}x^iy^{p-i} \equiv_p \sum_{i\in{\{ {0,p} \} }}{p\choose i}x^iy^{p-i} =x^p+y^p. \)
Trzeci dowód. Niech \( a\in{\{ {1,\ldots,p-1} \} } \).
Rozważmy słowa długości \( p \) nad alfabetem \( a \)-elementowym.
Przykład
Niech \( p=7 \), \( a=3 \). Symbolami alfabetu niech będą A,B,C. Oto mocno skrócona lista \( 3^7=2187 \) wszystkich słów \( 7 \)-literowych nad tym alfabetem.
| AAAAAAA, | AAAAAAB, | AAAAAAC, | AAAAABA, | AAAAABB, | |
| AAAAABC, | AAAAACA, | AAAAACB, | AAAAACC, | ... | |
| ... | |||||
| CCCCCBB, | CCCCCBC, | CCCCCCA, | CCCCCCB, | CCCCCCC. |
Wszystkich takich słów jest \( a^p \). Pokażemy, że po usunięciu słów jednoliterowych, pozostałe \( a^p-a \) słów będzie można podzielić na rozłączne \( p \)-elementowe grupy. To oczywiście natychmiast da \( p|a^p-a \), czyli pożądaną równość \( a^p\ \equiv_{p}a \).
Słowo \( v \) nazwiemy przesunięciem cyklicznym słowa \( w=w_1\ldots w_k \) o \( i \) liter, jeśli
\( v=w_{i+1}w_{i+2}\ldots w_kw_1\ldots w_{i-1}w_i. \)
Przykład
Przesunięcia cykliczne słowa CBAABCB:
| CBAABCB, | BAABCBC, | AABCBCB, | ABCBCBA, | BCBCBAA, | |
| CBCBAAB, | BCBAABC. |
Przesunięcia cykliczne słowa ABCABC:
| ABCABC, | BCABCA, | CABCAB. |
Drugi przykład pokazuje, że niektóre przesuniecia cyklicze sa równe. W istocie mamy:
Lemat 11.10
Niech \( v \) będzie słowem, którego nie da się przedstawić jako \( u^l=u\ldots u \), dla żadnego słowa \( u \) i żadnej liczby \( l>0 \). Z kolei niech \( w= v^k=v\ldots v \), dla pewnego \( k>0 \). Wtedy słowo \( w \) ma dokładnie \(| \) różnych przesunięć cyklicznych.
Dowód
Oczywiście, jeśli liczba liter, o które różnią się dwa przesunięcia cykliczne jest wielokrotnością długousi słowa \( v \), to te dwa przesunięcia dają to samo słowo. A zatem \( w \) ma co najwyżej \( | \) różnych przesunięć cyklicznych. Z drugiej strony, gdyby dwa przesunięcia cykliczne słowa \( v \) były równe, to dawałyby to samo słowo. Istotnie, gdy \( v=v_1\ldots v_m \) i \( v_1,\ldots,v_m \) są literami alfabetu, to każde przesunięcie cykliczne prowadzi do jednego ze słów z listy:
\( \begin{array} {rcll} v_1v_2v_3\ldots v_m & v^{k-1} & & , \\ v_2v_3\ldots v_m & v^{k-1} & v_1 & , \\ v_3\ldots v_m & v^{k-1} & v_1v_2 & , \\ & \vdots & & \\ v_m & v^{k-1} & v_1\ldots v_{m-1} & . \end{array} \)
Ponieważ \( |=m \), pozostaje pokazać, że słowa na tej liście sa różne. Dla dowodu niewprost, bez straty ogólności, możemy założyć, że:
\( v_1\ldots v_m v^{k-1}=v_i\ldots v_m v^{k-1}v_1v_2\ldots v_{i-1}, \)
dla pewnego \( 1 < i\leq m \). Wtedy
\( v_1\ldots v_m=v_i\ldots v_mv_1\ldots v_{i-1}. \)
To z kolei prowadzi do ciągu równości w poniższym diagramie:
\( \begin{array} {lcllcllcl} v_1 & \ldots & v_{m-(i-1)} & v_{m-(i-1)+1} & \ldots & v_{m-2(i-1)} & v_{m-2(i-1)+1} & \ldots & v_{m-3(i-1)}\ldots \\ & \parallel & & & \parallel & & & \parallel & \\ v_i & \ldots & v_m & v_1 & \ldots & v_{m-(i-1)} & v_{m-(i-1)+1} & \ldots & v_{m-2(i-1)}\ldots \end{array} \)
Czyli słowo \( v \) jest postaci \( v=x^l \) dla \( x=v_i\ldots v_m \) i \( l=\frac{m}{m-(i-1)} \), wbrew założeniom lematu.
Wyposażeni w Lemat, możemy powrócić do trzeciego dowodu Małego Twierdzenia Fermata. Niech więc \( w \) będzie słowem, w którym występują dwie różne litery alfabetu. Słowo to nie może być postaci \( v^l \), gdzie \( l\geq2 \), gdyż inaczej \( | |p \), a skoro \( p \) jest liczbą pierwszą, to \( |=1 \) lub \( |=p=| \). W pierwszym przypadku \( w \) jest jednoliterowe, a w drugim \( v=w \) i \( l=1 \). A zatem każde z \( a^p-a \) słów \( w \) ma dokładnie \( p \) różnych przesunięć cyklicznych. To dowodzi, iż \( p|a^p-a \), czyli \( a^p\ \equiv_{p}a \).
W jednym z dalszych wykładów poznamy jeszcze jeden dowód Małego Twierdzenia Fermata, oparty na elementarnej wiedzy z teorii grup.
Wykorzystując Małe Twierdzenie Fermata możemy trochę poprawić szybkość potęgowania modularnego. Asymptotycznie jednak złożoność pozostanie taka sama. Zauważmy bowiem, że:
\( a^b \equiv_p a^{b'}, \)
gdzie \( b' \) jest resztą z dzielenia \( b \) przez \( p-1 \).
Przykład
Policzmy \( 7^{126} \ {\sf mod} \ 11 \).