Informatyka MIMUW

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.

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:

Przesunięcia cykliczne słowa ABCABC:

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.