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 jest liczbą pierwszą, to dla dowolnej liczby całkowitej liczba jest podzielna przez

lub inaczej[1]:

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

DowodyEdytuj

Dowód z twierdzeniem EuleraEdytuj

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 kombinatorycznyEdytuj

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 grupEdytuj

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 indukcyjnyEdytuj

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

PrzypisyEdytuj

  1. Fermata twierdzenie małe, [w:] Encyklopedia PWN [online] [dostęp 2021-09-30].

BibliografiaEdytuj

Linki zewnętrzneEdytuj