Małe twierdzenie Fermata

Q: Czym różni się małe twierdzenie Fermata od wielkiego?

Małe dotyczy reszt z dzielenia przez liczbę pierwszą i ma prosty dowód. Wielkie mówi, że równanie x^n + y^n = z^n nie ma rozwiązań w liczbach naturalnych dla n > 2 - jego dowód (Andrew Wiles, 1995) zajmuje ponad sto stron.

Q: Czy twierdzenie działa dla liczb złożonych?

Nie w ogólności. Dla n = 4 i a = 2 mamy 2^4 = 16 equiv 0 ±od 4, a nie 2. Pierwszość modułu jest istotna - używamy jej w dowodzie w dwóch miejscach.

Q: Co jeśli p dzieli a?

Wtedy obie strony a^p equiv a przystają do zera i twierdzenie nadal jest prawdziwe. Nie zachodzi natomiast wersja a^p-1 equiv 1 - stąd w niej dodatkowe założenie p nmid a.

Jeśli $p$ jest liczbą pierwszą, to dla każdej liczby całkowitej $a$ :

$a^p \equiv a \pmod{p}.$

Jeśli dodatkowo $p$ nie dzieli $a$ , to:

$a^{p-1} \equiv 1 \pmod{p}.$

Co mówi twierdzenie

Zapis $x \equiv y \pmod{m}$ czytamy „ $x$ przystaje do $y$ modulo $m$ ” i znaczy tyle, że $x$ i $y$ dają tę samą resztę z dzielenia przez $m$ - równoważnie: $m$ dzieli różnicę $x - y$ .

Małe twierdzenie Fermata mówi więc: podnieś dowolną liczbę do potęgi $p$ (gdzie $p$ jest pierwsza), a reszta z dzielenia przez $p$ nie zmieni się. To zaskakujące - potęgowanie zmienia liczbę drastycznie, a mimo to reszta wraca na swoje miejsce.

Przykład. Weźmy $p = 7$ i $a = 3$ :

$3^7 = 2187 = 312 \cdot 7 + 3,$

więc rzeczywiście $3^7 \equiv 3 \pmod 7$ . W wersji z wykładnikiem $p - 1$ :

$3^6 = 729 = 104 \cdot 7 + 1 \quad\Longrightarrow\quad 3^6 \equiv 1 \pmod 7.$

Dowód

Pokaż dowódUkryj dowód

Dowodzimy wersji $a^p \equiv a \pmod p$ indukcyjnie po $a$ , dla $a$ naturalnych.

Krok 1. Lemat: dla $0 < k < p$ liczba $\binom{p}{k}$ dzieli się przez $p$ . Ze wzoru

$\binom{p}{k} = \frac{p!}{k! \, (p-k)!}$

widać, że licznik zawiera czynnik $p$ . Mianownik jest iloczynem liczb mniejszych od $p$ , a $p$ jest pierwsza, więc żaden czynnik mianownika nie skróci się z $p$ . Symbol Newtona jest liczbą całkowitą, zatem po skróceniu $p$ nadal w nim zostaje - czyli $p \mid \binom{p}{k}$ .

Krok 2. Baza indukcji. Dla $a = 0$ mamy $0^p = 0 \equiv 0 \pmod p$ .

Krok 3. Krok indukcyjny. Załóżmy, że $a^p \equiv a \pmod p$ . Rozwijamy $(a+1)^p$ dwumianem Newtona:

$(a+1)^p = \sum_{k=0}^{p} \binom{p}{k} a^k = a^p + \binom{p}{1}a^{p-1} + \ldots + \binom{p}{p-1}a + 1.$

Wszystkie składniki „środkowe” mają współczynnik $\binom{p}{k}$ z $0 < k < p$ , a te - na mocy lematu - dzielą się przez $p$ . Modulo $p$ znikają:

$(a+1)^p \equiv a^p + 1 \pmod p.$

Korzystając z założenia indukcyjnego $a^p \equiv a$ :

$(a+1)^p \equiv a + 1 \pmod p.$

To jest teza dla $a + 1$ , więc indukcja jest zamknięta i $a^p \equiv a \pmod p$ zachodzi dla wszystkich $a$ naturalnych. Dla $a$ ujemnych wynika to z okresowości reszt.

Krok 4. Wyprowadzamy drugą wersję. Niech $p \nmid a$ . Zapiszmy pierwszą wersję jako

$a \cdot (a^{p-1} - 1) \equiv 0 \pmod p.$

Liczba pierwsza dzieląca iloczyn musi dzielić jeden z czynników. Ponieważ $p \nmid a$ , musi być $p \mid a^{p-1} - 1$ , czyli

$a^{p-1} \equiv 1 \pmod p. \qquad \blacksquare$

Do czego to skraca rachunki

Twierdzenie zamienia gigantyczne potęgowanie w kilka linijek. Policzmy resztę z dzielenia $2^{100}$ przez $13$ .

Krok 1. $13$ jest pierwsza i $13 \nmid 2$ , więc $2^{12} \equiv 1 \pmod{13}$ .

Krok 2. Dzielimy wykładnik przez $12$ : $100 = 8 \cdot 12 + 4$ .

Krok 3. Rozbijamy potęgę:

$2^{100} = \left(2^{12}\right)^{8} \cdot 2^{4} \equiv 1^{8} \cdot 16 \equiv 16 \equiv 3 \pmod{13}.$

Reszta wynosi $3$ - bez wyliczania liczby $2^{100}$ , która ma $31$ cyfr.

Twierdzenie odwrotne jest fałszywe

Kusi, żeby użyć twierdzenia jako testu pierwszości: sprawdzić, czy $a^{n-1} \equiv 1 \pmod n$ , i uznać $n$ za pierwszą. Taki test czasem kłamie.

$341 = 11 \cdot 31$ jest liczbą złożoną, a mimo to $2^{340} \equiv 1 \pmod{341}$ . Takie liczby nazywamy pseudopierwszymi przy podstawie $2$ .
Gorzej: istnieją liczby złożone, które oszukują test dla każdej podstawy względnie pierwszej z nimi. To liczby Carmichaela; najmniejsza z nich to

$561 = 3 \cdot 11 \cdot 17.$

W 1994 roku udowodniono, że liczb Carmichaela jest nieskończenie wiele. Dlatego w praktyce używa się mocniejszych testów - np. testu Millera-Rabina, którego liczby Carmichaela już nie zwodzą.

Po co to komu

RSA - szyfrowanie z kluczem publicznym. W RSA wiadomość $m$ szyfruje się jako $c = m^e \bmod n$ , a deszyfruje jako $m = c^d \bmod n$ , gdzie $n = p \cdot q$ jest iloczynem dwóch dużych liczb pierwszych. To, że deszyfrowanie faktycznie odtwarza oryginał, wynika wprost z małego twierdzenia Fermata (a ściślej z jego uogólnienia - twierdzenia Eulera): wykładniki $e$ i $d$ dobiera się tak, by $e \cdot d \equiv 1 \pmod{(p-1)(q-1)}$ , i wtedy

$c^d = m^{ed} \equiv m \pmod n.$

Testy pierwszości. Zanim wygeneruje się klucz RSA, trzeba znaleźć duże liczby pierwsze - sprawdzanie dzielników odpada, więc używa się testów opartych właśnie na tym twierdzeniu.

Kto i kiedy

Twierdzenie sformułował Pierre de Fermat w liście z 1640 roku, kończąc je typową dla siebie uwagą, że dowód pomija, „bo byłby zbyt długi”. Pierwszy opublikowany dowód podał Leonhard Euler w 1736 roku, a później uogólnił twierdzenie na dowolny moduł $n$ (twierdzenie Eulera z funkcją $\varphi$ ).

Przymiotnik „małe” odróżnia je od wielkiego twierdzenia Fermata o równaniu $x^n + y^n = z^n$ , które czekało na dowód aż do 1995 roku. Trzecie twierdzenie o tym nazwisku - o ekstremum - należy do analizy matematycznej; wszystkie trzy zestawia strona Twierdzenia Fermata.

Najczęstsze pytania

Czym różni się małe twierdzenie Fermata od wielkiego? Małe dotyczy reszt z dzielenia przez liczbę pierwszą i ma prosty dowód. Wielkie mówi, że równanie $x^n + y^n = z^n$ nie ma rozwiązań w liczbach naturalnych dla $n > 2$ - jego dowód (Andrew Wiles, 1995) zajmuje ponad sto stron.

Czy twierdzenie działa dla liczb złożonych? Nie w ogólności. Dla $n = 4$ i $a = 2$ mamy $2^4 = 16 \equiv 0 \pmod 4$ , a nie $2$ . Pierwszość modułu jest istotna - używamy jej w dowodzie w dwóch miejscach.

Co jeśli $p$ dzieli $a$ ? Wtedy obie strony $a^p \equiv a$ przystają do zera i twierdzenie nadal jest prawdziwe. Nie zachodzi natomiast wersja $a^{p-1} \equiv 1$ - stąd w niej dodatkowe założenie $p \nmid a$ .

Czy z twierdzenia wynika, że liczba jest pierwsza? Nie - to najczęstsza pułapka. Twierdzenie odwrotne jest fałszywe, o czym świadczą liczby Carmichaela, np. $561$ .

Jak to się ma do twierdzenia Wilsona? Oba opisują zachowanie liczb pierwszych w arytmetyce modularnej, ale twierdzenie Wilsona daje warunek równoważny pierwszości (działa w obie strony), tyle że wymaga liczenia silni - w praktyce zbyt kosztownego.

Podsumowanie

Dla liczby pierwszej $p$ i dowolnej liczby całkowitej $a$ zachodzi $a^p \equiv a \pmod p$ .
Gdy $p \nmid a$ , twierdzenie przyjmuje wygodniejszą postać $a^{p-1} \equiv 1 \pmod p$ .
Dowód opiera się na tym, że $p$ dzieli wszystkie środkowe współczynniki dwumianowe $\binom{p}{k}$ dla $0 < k < p$ .
Twierdzenie odwrotne nie jest prawdziwe - liczby Carmichaela (najmniejsza: $561$ ) oszukują test przy każdej podstawie.
To fundament szyfrowania RSA i testów pierwszości używanych przy generowaniu kluczy.