Małe twierdzenie Fermata

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Małe twierdzenie Fermata (MTF) – twierdzenie teorii liczb sformułowane (bez dowodu) przez francuskiego matematyka Pierre'a de Fermata. Na 42 lata przed Fermatem twierdzenie to sformułował polski matematyk Jan Brożek[1]. 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 jest liczbą pierwszą, to dla dowolnej liczby całkowitej , liczba jest podzielna przez .
,

lub inaczej

jeśli jest liczbą pierwszą, a jest taką liczbą całkowitą, że liczby i względnie pierwsze, to dzieli się przez . Innymi słowy,
,
albo
.

Dowody[edytuj]

Dowód z twierdzeniem Eulera[edytuj]

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

Dowód kombinatoryczny[edytuj]

Graficzne przedstawienie dowodu

Bez straty ogólności można założyć, że 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 .

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 , 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 i liczby zestawów po p kolorowań + liczba kolorowań jednokolorowych
,
gdzie n jest pewną liczbą naturalną.

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

Dowód wykorzystujący metody teorii grup[edytuj]

Zbiór jest grupą z działaniem mnożenia modulo p, nazywaną multyplikatywną grupą klas reszt modulo p. Grupa ta jest rzędu (ma elementów). Niech będzie dowolnym elementem tej grupy. Oznaczmy przez rząd tego elementu, tzn. najmniejszą liczbę spełniającą warunek . Innymi słowy

Z twierdzenia Lagrange'a wynika, że rząd elementu dzieli rząd grupy , czyli . A zatem istnieje pewna liczba naturalna spełniająca warunek

Wówczas

.

Dowód indukcyjny[edytuj]

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

dla

wówczas:

Ponieważ

więc dla żaden z czynników nie jest równy , dlatego jest wielokrotnością . Zatem:

Ostatecznie:

Zatem na mocy indukcji , czyli p dzieli .

Przypisy

Bibliografia[edytuj]

Zobacz też[edytuj]