Fermatov mali izrek

Iz Wikipedije, proste enciklopedije

Za druge pomene glej Fermatov izrek.

Fermatov mali izrek ali tudi mali Fermatov izrek pravi, da kadar je p praštevilo, potem za vsako celo število a velja:

$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 Freniclu datiranem 18. oktobra 1640 v naslednji obliki: p deli a^p-1 - 1 kadar je p praštevilo in a je p tuje ali:

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

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

[uredi] 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:

$(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 $({}_{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 $({}_{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.

Očitno je a^p mod p = a pri a = 1.
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.

[uredi] Posplošitve

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

$a^{\varphi (n)} = 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 z Carmichaelovim izrekom, ki je v angleščini zapisan tukaj: http://mathworld.wolfram.com/CarmichaelsTheorem.html.

[uredi] 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.