Mažoji Ferma teorema

Mažoji Ferma teorema - skaičių teorijos teorema, suformuluota prancūzų matematiko Pjero Ferma, skelbia, kad:

Pjeras Ferma

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

Naudojant modulinę aritmetiką tai užrašoma taip:

$a^{p-1}\equiv 1{\pmod {p}}.$

Pirmąjį šios teoremos įrodymą 1736 m. paskelbė Leonardas Euleris, tačiau yra žinoma, kad Gotfrydas Leibnicas pateikė identišką įrodymą neskelbtame rankraštyje iki 1683 m.

Mažoji Ferma teorema gali būti apibendrinta iki Oilerio teoremos.

Į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.

Pavyzdžiai

• 4³ − 4 = 60 dalijasi iš 3.
• 7² − 7 = 42 dalijasi iš 2.
• 3⁷ − 3 = 2184 dalijasi iš 7.
• 2⁹⁷ − 2 = 158 456 325 028 528 675 187 087 900 670 dalijasi iš 97.

Taikymas

Mažoji Ferma teorema yra viena iš svarbiausių skaičių teorijos teoremų, kuri naudojama kitose srityse. Pavyzdžiui, kriptografijoje, nes ji sukūrė keletą pirminių skaičių tikrinimo metodų ir naudojama RSA šifravimo algoritmo teisingumui patikrinti.