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{\pmod {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{\pmod {p}},$

albo

$a^{p-1}\equiv 1{\pmod {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

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 ${\tfrac {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{\pmod {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{\pmod {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{\pmod {p}}$ dla $a\geqslant 1.$

Wówczas:

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

Ponieważ

${p \choose 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 $p \choose k$ jest wielokrotnością $p.$ Zatem:

${p \choose k}\equiv 0{\pmod {p}}.$

Ostatecznie:

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

Zatem na mocy indukcji $a^{p}\equiv a{\pmod {p}},$ czyli p dzieli $a^{p}-a.$

Zobacz też

• liczby pseudopierwsze

Bibliografia

• Wacław Sierpiński: Arytmetyka teoretyczna. Wyd. 2. Warszawa: Państwowe Wydawnictwo Naukowe, 1959, s. 144–147.

Linki zewnętrzne

• TomaszT. Kazana TomaszT., Małe Twierdzenie Fermata, [w:] pismo „Delta”, deltami.edu.pl, kwiecień 2017, ISSN 0137-3005 [dostęp 2022-07-20]  (pol.).
• Eric W.E.W. Weisstein Eric W.E.W., Fermat’s Little Theorem, [w:] MathWorld, Wolfram Research  (ang.). [dostęp 2022-07-02].
• Fermat's little theorem (ang.), Encyclopedia of Mathematics, encyclopediaofmath.org, [dostęp 2023-06-18].