Fermatov mali izrek

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje

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:

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 ap-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. Zgled za osnovo 2:

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

in ostanek pri deljenju:

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

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

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

Števila:

 \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[uredi | uredi kodo]

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 = ap + bp 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})aibp-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 ap + bp mod p, kadar je p praštevilo.

  1. Očitno je ap mod p = a pri a = 1.
  2. Predpostavimo sedaj, da pri a = k izrek velja. S tem predpostavimo kp 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)
kp + 1p mod p = kp + 1 mod p.
Ker smo predpostavili da velja kp 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[uredi | uredi kodo]

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

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

Če sta a in p dve takšni tuji števili, da velja ap-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.