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]