Małe Twierdzenia Fermata

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.

Potęgowanie modulo liczba pierwsza.

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 \).

  • \( 11 \) jest liczba pierwszą, czyli możemy skorzystać z Małego Twierdzenia Fermata,
  • \( 126 \ {\sf mod} \ 10 =6 \),
  • \( 7^{126}\equiv_{11}7^6 \),
  • \( 6=(110)_2 \),
  • liczymy wybrane potęgi \( 7 \) modulo \( 11 \):
    • \( 7^2=49\equiv_{11}5 \),
    • \( 7^4\equiv_{11}5\cdot5=25\equiv_{11}4 \).
  • \( 7^{127}\equiv_{11}7^6=7^4\cdot7^2\equiv_{11}4\cdot5=20\equiv_{11}9 \).
  • wykonaliśmy \( 3 \) mnożenia.