Fermatov mali izrek

Za druge pomene glej Fermatov izrek.

Fermatov máli izrèk ali tudi máli Fermatov izrèk [fermájev ~] pravi, da kadar je p praštevilo, potem za vsako celo število a velja:

${\displaystyle a^{p}\equiv a{\pmod {p}}\!\,.}$

To pomeni, da kadar vzamemo poljubno celo število a in ga pomnožimo s samim seboj p krat in odštejemo a, bomo dobili število, ki bo deljivo s p. (glej mudularna aritmetika). Imenujemo ga Fermatov mali izrek, da ga ločimo od Fermatovega velikega izreka. Pierre de Fermat je našel izrek okoli leta 1636. Izrek se je pojavil v enem od njegovih pisem svojemu zaupniku Frénicleu datiranem 18. oktobra 1640 v naslednji obliki: p deli a^p-1 - 1 kadar je p praštevilo in a je p tuje ali:

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

Primer za a = 2 so poznali že stari Kitajci. Zgled za osnovo 2:

${\displaystyle 2^{17-1}-1=65535\!\,}$

in ostanek pri deljenju:

${\displaystyle D(65535,17)-17=0,\quad \mathrm {oziroma\ } 65535=17\cdot 3855\!\,,}$

kjer je D() največji skupni delitelj. In za osnovo 3:

${\displaystyle 3^{17-1}-1=43046720;\quad D(43046720,17)-17=0;\quad 43046720=17\cdot 2532160\!\,.}$

Števila:

${\displaystyle {\frac {a^{p-1}-1}{p}}\!\,}$

so Fermatovi količniki za osnovo a. Prvi Fermatovi količniki za osnovo 2 so (OEIS A007663):

1, 3, 9, 93, 315, 3855, 13797, 182361, 9256395, 34636833, 1857283155, ...

Dokaz

Fermat je pojasnil svoj izrek brez dokaza. Prvi ga je dokazal Gottfried Wilhelm Leibniz v svojem rokopisu brez datuma, kjer je tudi zapisal, da je poznal dokaz že pred letom 1683.

Dokaz »malega izreka« je enostaven in osnoven. Uporabimo lahko matematično indukcijo. Pokažemo da izrek velja za a = 1. Če izrek velja za a = k, lahko pokažemo, da velja tudi za a = k + 1 in s tem za vse a.

Potrebujemo naslednjo lemo:

(a + b)^p mod p = a^p + b^p mod p

kadar je p praštevilo. Binomski izrek nam pove:

${\displaystyle (a+b)^{p}=\sum _{i=0}^{p}{p \choose i}a^{i}b^{p-i}=a^{p}+b^{p}+\sum _{i=1}^{p-1}{p \choose i}a^{i}b^{p-i}\!\,.}$

Tukaj je ${\displaystyle ({}_{i}^{p})}$ = p(p - 1)(p - 2)(p - 3) ... (p - (i-1)) / i! če 0 < i < p. Ker je i manjši od p in je p praštevilo, i! ne deli p, zato je celotni člen ${\displaystyle ({}_{i}^{p})}$aⁱb^p-i mnogokratnik p če 0 < i < p. To pomeni, da je celotna vsota od i = 1 do i = p - 1 enaka 0 mod p. Tako je (a + b)^p mod p v resnici enako a^p + b^p mod p, kadar je p praštevilo.

1. Očitno je a^p mod p = a pri a = 1.
2. Predpostavimo sedaj, da pri a = k izrek velja. S tem predpostavimo k^p mod p = k kadar je k < p in poglejmo, kaj se zgodi pri a = k + 1:

(k + 1)^p mod p =

(pokažemo s trditvijo spodaj)

k^p + 1^p mod p = k^p + 1 mod p.

Ker smo predpostavili da velja k^p mod p = k pri k < p, sklepamo, da velja (k + 1)^p mod p = k + 1, kadar je k + 1 < p, kar smo hoteli dokazati.

Posplošitve

Fermatov mali izrek posplošimo z Eulerjevim izrekom: za poljuben modul n in poljubno celo število a tuje n, imamo

${\displaystyle a^{\varphi (n)}\equiv 1{\pmod {n}}\!\,,}$

kjer je φ(n) Eulerjeva funkcija, ki šteje vsa cela števila med 1 in n, ki so n tuja. To je zares posplošitev, ker, če je n = p praštevilo, potem φ(p) = p - 1.

To lahko še naprej posplošimo s Carmichaelovim izrekom.

Psevdopraštevila

Če sta a in p dve takšni tuji števili, da velja a^p-1 - 1 | p, potem p nujno ni praštevilo. Če p ni praštevilo, se imenuje Fermatovo psevdopraštevilo za bazo a. Število p, ki je psevdopraštevilo za bazo a za vsako število a tuje n, se imenuje Carmichaelovo število.