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>,

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>