Mažoji Ferma teorema

Pjeras Ferma

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$$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$$a{\pmod {p}}\neq 0$, tai visi sekos $1\cdot a,2\cdot a,3\cdot a,...,(p-1)\cdot a$$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}}$$a\cdot k\equiv a\cdot m{\pmod {p}}$. Tada $ak-am\equiv 0{\pmod {p}}$$ak-am\equiv 0{\pmod {p}}$. Iškeliame a: $a\cdot (k-m)\equiv 0{\pmod {p}}$$a\cdot (k-m)\equiv 0{\pmod {p}}$. Tačiau $a{\pmod {p}}\neq 0\Rightarrow k-m\equiv 0{\pmod {p}}$$a{\pmod {p}}\neq 0\Rightarrow k-m\equiv 0{\pmod {p}}$. Kadangi $k<p$$k<p$ ir $m<p$$m<p$, gauname $k=m$$k=m$. Išeina, kad sekoje negali egzistuoti du skirtingi nariai $a\cdot m\equiv a\cdot k{\pmod {p}}$$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};$$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}};$$(p-1)!\cdot a^{p-1}\equiv (p-1)!{\pmod {p}};$ dalijame abi puses iš $(p-1)!$$(p-1)!$:
$a^{p-1}\equiv 1{\pmod {p}}$$a^{p-1}\equiv 1{\pmod {p}}$. Tą patį galima užrašyti ir kaip $a^{p-1}-1{\pmod {p}}=0$$a^{p-1}-1{\pmod {p}}=0$.
Įrodymas baigtas.