Mažoji Ferma teorema

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.
Peršokti į: navigaciją, paiešką

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[taisyti | redaguoti kodą]

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.