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 [[matematyk]]a [[Pierre de Fermat|Pierre'a de Fermata]]. Twierdzenie to 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]].

 

: jeżeli <math>p</math> jest [[liczba pierwsza|liczbą pierwszą]], to dla dowolnej liczby całkowitej <math>a</math>, liczba <math>a^p - a</math> jest podzielna przez <math>p</math>.

:: <math>a^p - a \equiv 0 \pmod p</math>,

 

: jeśli <math>p</math> jest liczbą pierwszą, a <math>a</math> jest taką liczbą całkowitą, że liczby <math>a</math> i <math>p</math> są [[liczby względnie pierwsze|względnie pierwsze]], to <math>a^{p-1} - 1</math> dzieli się przez <math>p</math>.

:: <math>a^{p-1} - 1 \equiv 0 \pmod p</math>,

 

: jeżeli <math>p</math> jest liczbą pierwszą, a <math>a</math> liczbą całkowitą, która nie jest podzielna przez <math>p</math>, to <math>a</math> podniesione do potęgi <math>p-1</math> da w dzieleniu przez <math>p</math> resztę równą <math>1</math>.

:: <math>a^{p-1} \equiv 1 \pmod p</math>.

 

== Dowody ==

Jeżeli <math>p</math> jest taką [[liczby pierwsze|liczbą pierwszą]], która nie dzieli <math>a</math>, to <math>p</math> jest względnie pierwsze z <math>a</math>, a więc w myśl [[Twierdzenie Eulera o liczbach względnie pierwszych|twierdzenia Eulera o liczbach względnie pierwszych]] teza twierdzenia jest prawdziwa.

 

Kolorów jest ''a'', więc kolorowań jednokolorowych jest ''a''. Wynika stąd, że <math>p</math> dzieli liczbę <math>a^p-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ą 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>