Fermat tétele

Az itt következő bizonyítás Erdős Pál - Surányi János: Válogatott fejezetek a számelméletből, Tankönyvkiadó Vállalat, Budapest 1960 könyvből való.

A tétel alapvető jelentőségű a nyilvános kulcsú titkosítások számára.

A hivatkozott VI. és VII. tételeket, amelyeket a bizonyítás felhasznál itt nem bizonyítjuk, csak a kimondjuk. A tételek bizonyítása megtalálható a hivatkozott könyvben. (Kérdés, hogy a könyv hol található meg.)

Megjegyzés a jelölésről.


Tétel:
Ha p prímszám, és nem osztója egy a egésznek, akkor ap-1-1 osztható p-vel.

Bizonyítás:
A bizonyítás abból fog állni, hogy megvizsgáljuk sorra az a, 2a, ..., (p-1)a számok maradékát p-vel való osztásnál: legyen

ka=pqk+rk, 0<=rk<p (k=1,2,...,p-1).

Egyik rk sem lehet nulla, mert k nem osztható p-vel, s így relatív prím hozzá, a-ra feltétel szerint ugyanaz áll, s így a VII. tétel szerint ka is relatív prím p-hez.

Az összes maradékok különböznek egymástól. Legyen ugyanis k1>k2 és vonjuk ki a k1-edik egyenletből a k2-ediket:

(k1-k2)a=p(qk1 - qk2)+(rk1 - rk2).

Itt a (k1-k2) szám p-nél kisebb pozitív egész, és így a bal oldal az előbbiekhez hasonló okoskodás szerint nem osztható p-vel, tehát rk1-rk2 sem lehet 0.

Az r1,r2,...,rp-1 számok tehát az 1,2,...,p-1 számok közül kerülnek ki, és nincs köztük két egyenlő. Ebből viszont az következik, hogy valamilyen sorrendben az 1,2,...,p-1 számok mindegyike előfordul közöttük. Szorozzuk össze most az egyenlőségeinket és vizsgáljuk meg a jobb oldalt. Itt, ha tagonként beszorzunk, az r1 r2 ... rp-1 tagon kívül csupa p-vel osztható tag keletkezik, e tag pedig utolsó megállapításunk szerint (p-1)!-sal egyenlő. Ilyen alakú egyenlőséget kapunk tehát:

(p-1)! ap-1=pQ+(p-1)!

ahol Q valamilyen egész szám. Ezt úgy is mondhatjuk, hogy

(p-1)! (ap-1-1)

osztható p-vel. (p-1)! azonban relatív prím p-hez a VII. tétel értelmében, mert mindegyik tényezője relatív prím hozzá. Így a VI. tétel szerint ap-1-1 osztható p-vel, és ezt akartuk bizonyítani.


toc