Mažoji Ferma teorema

Mažoji Ferma teorema, suformuluota prancūzų matematiko Pjero Ferma, skelbia, kad:

„Jeigu a nesidalija iš p ir jei p yra pirminis skaičius, tai ($a^{p-1}-1$) dalijasi iš p.“

Įrodymas

Visi skaičiai nuo 1 iki p-1 dalijami iš p duoda skirtingas liekanas. Įrodysime, kad jei $a\pmod{p} \neq 0$, tai visi sekos $1 \cdot a , 2 \cdot a , 3 \cdot a , ... , (p-1) \cdot a$ nariai dalijami iš p irgi duos skirtingas liekanas.
Tarkime, kad egzistuoja tokie du sekos nariai, kurie duoda vienodas liekanas: $a \cdot k \equiv a \cdot m\pmod{p}$. Tada $ak- am \equiv 0\pmod{p}$. Iškeliame a: $a \cdot (k - m) \equiv 0\pmod{p}$. Tačiau $a\pmod{p} \neq 0 \Rightarrow k-m \equiv 0\pmod{p}$. Kadangi $k < p$ ir $m < p$, gauname $k=m$. Išeina, kad sekoje negali egzistuoti du skirtingi nariai $a \cdot m \equiv a \cdot k\pmod{p}$.
Pertvarkome seką:
$1 \cdot a \cdot 2 \cdot a \cdot ... \cdot (p-1) \cdot a = (p-1)! \cdot a^{p-1};$
$(p-1)! \cdot a^{p-1} \equiv (p-1)!\pmod{p};$ dalijame abi puses iš $(p-1)!$:
$a^{p-1} \equiv 1\pmod{p}$. Tą patį galima užrašyti ir kaip $a^{p-1} - 1\pmod{p} = 0$.
Įrodymas baigtas.