Małe twierdzenie Fermata

Małe twierdzenie Fermata (MTF) – twierdzenie teorii liczb sformułowane (bez dowodu) przez francuskiego matematyka Pierre’a de Fermata. Twierdzenie jest podstawą dla testu pierwszości Fermata. Poniżej każdego sformułowania twierdzenia znajduje się zapis w arytmetyce modularnej.

Małe twierdzenie Fermata:

jeżeli $p$ jest liczbą pierwszą, to dla dowolnej liczby całkowitej $a,$ liczba $a^p-a$ jest podzielna przez $p.$

$a^p-a\equiv 0(\mathrm{mod}p),$

lub inaczej:

jeśli $p$ jest liczbą pierwszą, a $a$ jest taką liczbą całkowitą, że liczby $a$ i $p$ są względnie pierwsze, to $a^{p-1}-1$ dzieli się przez $p.$ Innymi słowy,

$a^{p-1}-1\equiv 0(\mathrm{mod}p),$

albo

$a^{p-1}\equiv 1(\mathrm{mod}p).$

Dowody

Dowód z twierdzeniem Eulera

Jeżeli $p$ jest taką liczbą pierwszą, która nie dzieli $a,$ to $p$ jest względnie pierwsze z $a,$ a więc w myśl twierdzenia Eulera o liczbach względnie pierwszych teza twierdzenia jest prawdziwa.

Dowód kombinatoryczny

Plik:MTFproof.png

Graficzne przedstawienie dowodu

Bez straty ogólności można założyć, że $a$ jest liczbą naturalną. Rozpatrzmy wszystkie możliwe kolorowania koła podzielonego na p części za pomocą a kolorów. Kolorowania, które możemy na siebie nałożyć po obróceniu, liczymy jako dwa różne. Wszystkich kolorowań jest $a^p.$

Wszystkie kolorowania, w których wykorzystaliśmy co najmniej dwa kolory możemy obracać tak, że otrzymamy zestawy po p parami różnych kolorowań, które są swoimi obrotami (przykładowe cztery z pewnego zestawu dla p=7, a=3 są przedstawione na rysunku). Jeżeli w pewnym zestawie utworzonym w ten sposób wystąpiłyby takie same kolorowania, to oznaczałoby to, że kąt pełny jest wielokrotnością pewnego kąta $\frac{2\pi n}{p},$ o który trzeba obrócić jedno z tych kolorowań, aby otrzymać drugie. W przypadku, gdy wykorzystaliśmy jeden kolor, nie jest to możliwe. Zatem:

liczba wszystkich kolorowań jest iloczynem $p$ i liczby zestawów po p kolorowań + liczba kolorowań jednokolorowych

$a^p=pn+a,$

gdzie n jest pewną liczbą naturalną.

Kolorów jest a, więc kolorowań jednokolorowych też jest a. Wynika stąd, że $p$ dzieli liczbę $a^p-a.$

Dowód wykorzystujący metody teorii grup

Zbiór ${\mathbb{Z}}_p^{*}=\{1,\dots ,p-1\}$ jest grupą z działaniem mnożenia modulo p, nazywaną multiplikatywną grupą klas reszt modulo p. Grupa ta jest rzędu $p-1$ (ma $p-1$ elementów). Niech $a$ będzie dowolnym elementem tej grupy. Oznaczmy przez $k$ rząd tego elementu, tzn. najmniejszą liczbę $k\in \mathbb{N}$ spełniającą warunek $a^k=1.$ Innymi słowy

$a^k\equiv 1(\mathrm{mod}p).$

Z twierdzenia Lagrange’a wynika, że rząd elementu $a$ dzieli rząd grupy ${\mathbb{Z}}_p^{*},$ czyli $k|p-1.$ A zatem istnieje pewna liczba naturalna $m$ spełniająca warunek

$p-1=km.$

Wówczas

$a^{p-1}\equiv a^{km}\equiv (a^k{)}^m\equiv 1^m\equiv 1(\mathrm{mod}p).$

Dowód indukcyjny

Załóżmy, że $a$ jest liczbą naturalną. Twierdzenie to jest prawdziwe, gdy $a=1.$ Zatem załóżmy indukcyjnie, że:

$a^p\equiv a(\mathrm{mod}p)$ dla $a⩾1.$

Wówczas:

$(a+1{)}^p=\sum _{k=0}^p(\genfrac{}{}{0ex}{}{p}{k})a^k=a^p+a^0+\sum _{k=1}^{p-1}(\genfrac{}{}{0ex}{}{p}{k})a^k.$

Ponieważ

$(\genfrac{}{}{0ex}{}{p}{k})=\frac{p(p-1)(p-2)\dots (p-k+1)}{k!},$

więc dla $0<k<p$ żaden z czynników $k!$ nie jest równy $p,$ dlatego $(\genfrac{}{}{0ex}{}{p}{k})$ jest wielokrotnością $p.$ Zatem:

$(\genfrac{}{}{0ex}{}{p}{k})\equiv 0(\mathrm{mod}p).$

Ostatecznie:

$(a+1{)}^p\equiv a^p+a^0+\sum _{k=1}^{p-1}(\genfrac{}{}{0ex}{}{p}{k})a^k\equiv a^p+a^0\equiv a+1.$

Zatem na mocy indukcji $a^p\equiv a(\mathrm{mod}p),$ czyli p dzieli $a^p-a.$

Zobacz też

• liczby pseudopierwsze

Bibliografia

• Szablon:Cytuj książkę

Linki zewnętrzne

• Szablon:Pismo Delta
• Szablon:Otwarty dostęp Małe twierdzenie Fermata, Wydział Matematyki i Nauk Informacyjnych Politechniki Warszawskiej (MiNI PW), kanał „Archipelag Matematyki” na YouTube, 4 października 2017 [dostęp 2024-09-04].
• Szablon:MathWorld [dostęp 2022-07-02].
• Szablon:Otwarty dostęp Fermat's little theorem Szablon:Lang, Encyclopedia of Mathematics, encyclopediaofmath.org, [dostęp 2023-06-18].