Małe twierdzenie Fermata: Różnice pomiędzy wersjami

'''Małe twierdzenie Fermata''' (MTF) – twierdzenie [[teoria liczb|teorii liczb]] sformułowane (bez dowodu) przez francuskiego [[matematyka]] [[Pierre de Fermat|Pierre'aPierre’a de Fermata]]. Na 42 lata przed Fermatem twierdzenie to sformułował polski matematyk [[Jan Brożek]]{{odn|Iłowiecki|1981|s=71}}. Twierdzenie jest podstawą dla [[test pierwszości Fermata|testu pierwszości Fermata]]. Poniżej każdego sformułowania twierdzenia znajduje się zapis w [[arytmetyka modularna|arytmetyce modularnej]].

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 <math>\tfrac{2 \pi n}{p} </math>, 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:

: Liczbaliczba wszystkich kolorowań jest iloczynem <math>p</math> i liczby zestawów po ''p'' kolorowań + liczba kolorowań jednokolorowych

:: <math>a^p = pn + a</math>,

Zbiór <math>\mathbb Z_p^*=\{1, \ldots, p-1\}</math> jest [[grupa (matematyka)|grupą]] z działaniem mnożenia modulo ''p'', nazywaną [[Arytmetyka modularna|multyplikatywnąmultiplikatywną grupą klas reszt modulo ''p'']]. Grupa ta jest rzędu <math>p-1</math> (ma <math>p-1</math> elementów). Niech <math>a</math> będzie dowolnym elementem tej grupy. Oznaczmy przez <math>k</math> [[rząd (teoria grup)|rząd]] tego elementu, tzn. najmniejszą liczbę <math>k \in \mathbb N</math> spełniającą warunek <math>a^k = 1</math>. Innymi słowy

: <math>a^k \equiv 1 \pmod p</math>.

Z [[twierdzenieTwierdzenie Lagrange'aLagrange’a (teoria grup)|twierdzenia Lagrange'aLagrange’a]] wynika, że rząd elementu <math>a</math> dzieli rząd grupy <math>\mathbb Z_p^*</math>, czyli <math>k | p-1</math>. A zatem istnieje pewna liczba naturalna <math>m</math> spełniająca warunek

: <math>p-1 = km</math>.

: <math>a^p \equiv a \pmod p</math> dla <math>a \geqslant 1</math>.

: <math>(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 </math>.

: <math>{p \choose k} = \frac{p(p-1)(p-2)\cdots (p-k+1)}{k!} </math>,

więc dla <math>0<k<p</math> żaden z czynników <math>k!</math> nie jest równy <math>p</math>, dlatego <math>{p \choose k}</math> jest wielokrotnością <math>p</math>. Zatem:

: <math>{p \choose k}</math> jest\equiv wielokrotnością0 \pmod <math>p</math>. Zatem:

: <math>(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 </math>.

Zatem na mocy indukcji <math> a^p \equiv a \pmod p</math>, czyli ''p'' dzieli <math>a^p - a</math>.

* {{cytuj książkę|nazwisko=Sierpiński|imię=Wacław|autor link=Wacław Sierpiński|tytuł=Arytmetyka teoretyczna|wydanie=2|wydawca=[[Wydawnictwo Naukowe PWN|PWN]]|miejsce=Warszawa|rok=1959|strony=144-147144–147}}