Małe twierdzenie Fermata

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Małe twierdzenie Fermata (MTF) – twierdzenie teorii liczb sformułowane (bez dowodu) przez francuskiego matematyka Pierre'a de Fermata. Twierdzenie to 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 pwzglę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[edytuj | edytuj kod]

Dowód z twierdzeniem Eulera[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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 więcej niż 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[edytuj | edytuj kod]

Zbiór \mathbb Z_p^*=\{1, \ldots, p-1\} jest grupą z działaniem mnożenia modulo p, nazywaną multyplikatywną 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[edytuj | edytuj kod]

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

Bibliografia[edytuj | edytuj kod]

Zobacz też[edytuj | edytuj kod]