Małe twierdzenie Fermata

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

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

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

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

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

Zbiór jest grupą z działaniem mnożenia modulo p, nazywaną multiplikatywną 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 | edytuj kod]

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

Zobacz też[edytuj | edytuj kod]

Przypisy[edytuj | edytuj kod]

Bibliografia[edytuj | edytuj kod]