Kis Fermat-tétel

A kis Fermat-tétel egy számelméleti tétel, mely a maradékok (egész számok közti kongruenciák) elméletében alapvető fontosságú. A jóval nehezebb, több évszázadig megoldatlan „nagy” Fermat-tételtől (külföldön Fermat utolsó tételétől – Fermat's last theorem) való megkülönböztetés miatt szokás „kis” Fermat-tételnek nevezni. Fermat egyik tételre sem adott bizonyítást, később ezt a kis Fermat-tétel esetében Leibniz tette meg (l. lentebb).

 A kis Fermat-tétel szerint bármely  prímszámra teljesül, bármely  egész szám esetén, hogy
.
Azaz ha veszünk tetszés szerint egy  egész számot, megszorozzuk önmagával -szer, és levonjuk belőle az -t, akkor az eredmény -vel osztható. 
 Gyakrabban a következő (és történelmileg hitelesebb) alakban is szokás kimondani: ha  prímszám és  egy ezen prímhez relatív prím egész, akkor
.

A tétel nemcsak a matematikában, hanem annak alkalmazásaiban is fontos, mert egyik alapja a Fermat-prímtesztnek, aminek szerepe van például az egyik legmodernebb rejtjelezési módszerben, az RSA-eljárásban.

Történelem

Fermat felfedezése 

Pierre de Fermat 1636-ban jött rá e tételre, és egy 1640. október 18-i levelében írta meg e felfedezését Frenicle-nek, egyik barátjának, a következőképpen: p osztója ap-1 – 1 -nek, ha p prím és a relatív prím p-hez. Fermat nem adta meg tétele bizonyítását (ahogy általában is csak nagyon ritkán adott bizonyítást eredményeire). Az első, akinek ez bizonyíthatóan sikerült, Gottfried Wilhelm Leibniz, egy keltezés nélküli kéziratban, ahol azt is írta, hogy már 1683. előtt is ismert bizonyítást e tételre.

A kínai sejtés 

Kínai matematikusok tőle függetlenül alkottak egy ehhez kapcsolódó hipotézist (amit néha Kínai sejtésnek neveznek): p akkor és csak akkor prím, ha . Az igaz, hogy ha p prím, akkor  (ez a kis Fermat-tétel egy speciális esete, ha ), ám ennek megfordítása, s így a sejtés egészében, hamis, mert ha  akkor még nem biztos, hogy  prím.

Pierre Fréderique Sarrus francia matematikus találta 1820-ban az  ellenpéldát (Fermat-álprímet). (Érdekesség, hogy Bolyai János is foglalkozott e problémával, bár efféle felfedezéseiből semmit nem publikált). Ellenőrizhető, hogy ez a 2 alapra tényleg álprím, mert teljesül ugyan , de  nem prím.

Széles körben állítják, hogy a kínai sejtést már kb. 2000 évvel Fermat 1600-as évekbeli munkája előtt megtalálták. Annak ellenére, hogy a sejtésnek „csak a fele igaz”, figyelemre méltó, hogy az ősi idők matematikusai már ismerhették. Néhányan pedig állítják, hogy az előző nézet egy félreértés eredménye, és valójában a kínai sejtés sokkal később, 1872-ben keletkezett (Ribenhoim, 1995).

Bizonyítási lehetőségek 

Fermat nem adott bizonyítást e tételre, az első, akinek ez bizonyíthatóan sikerült, Gottfried Wilhelm Leibniz, állítása szerint ő már 1683 előtt is ismert bizonyítást e tételre.

Az egyik legelemibb és legdidaktikusabbnak tartott matematikai bizonyítás egy egyszerű fogalomra, a teljes maradékrendszer fogalmára épül, de létezik olyan indukciós bizonyítás is, ami csak egyetlen komolyabb tételt, Newton binomiális tételét használja. Léteznek azonban szimbólumsorozatokra alapozó bizonyítások, és egészen komoly fogalmakat (csoportok, vagy például a dinamikus rendszerek) használóak is. Ez utóbbiak közül a csoportelméleti bizonyítás igen fontos, mert kiderül belőle, hogy a kis Fermat-tétel, és 
egyik közvetlen általánosítása, az Euler–Fermat-tétel speciális esete a csoportelmélet egyik legalapvetőbb fogalmára, a rendfogalomra vonatkozó egyik tételnek.

Az könnyen látható, hogy a kis Fermat-tétel fent megadott két alakja ekvivalens.
 Valóban, legyen . Ekkor, ha az  és  számok relatív prímek, azaz legnagyobb közös osztójuk 1: , a fenti kongruencia egyszerűsíthető a  modulushoz relatív prím szorzóval, és így  (ha pedig  és  nem lennének relatív prímek,  miatt  mindketten 0-val lennének kongruensek mod(p), és így szintén kongruensek lennének). 
 Fordítva, az  kongruencia tetszőleges  számok esetén szorozható a-val, és így  adódik.

Lásd még: A kis Fermat-tétel bizonyításai.

Megfordítások 

 Az egyik ilyen az az állítás lehet, hogy ha , és  , akkor  prím. Ezt azonban láttuk, hogy nem igaz: minden  alapszámhoz léteznek olyan  számok, ún. a alapú álprímek vagy pszeudoprímek, melyekre a fenti kongruencia igaz, de mégsem prímek. Ezek okozzák, hogy az ún. Fermat-prímteszt determinisztikusan nem megbízható. Sőt, vannak olyan kitevők is, melyek minden, hozzájuk relatív prím, de egyébként tetszőleges alaphoz álprímek. Ezek a Carmichael-számok (abszolút pszeudoprímek); a legkisebb ilyen az 561.
 Az sem igaz, hogy p-1 a legkisebb 1-et adó kitevő. Tehát ha teljesül a kongruencia mod(p) és a relatív prímség a-hoz egy n számra, attól még nem feltétlenül igaz, hogy szükségképp az p-1 (vagy annak többszöröse). Például p=5-re már , és 2 nem 5-1=4, hanem annál jóval kisebb (bár Lagrange tétele miatt szükségképp osztója 4=p-1-nek.).

Általánosítások 

 Az eredeti kis Fermat-tétel egy kissé kiteljesített alakja a következő:

Ez az összes  számpárra megadja az  kifejezés értékét  (mert egy prím vagy oszt egy számot, vagy relatív prím hozzá).

 A legelemibb általánosítás a következőt mondja: 
 Ha p prím és m, n pozitív egész számok úgy, hogy m ≡ n (mod p-1), akkor am ≡ an (mod p) teljesül minden a egészre.
Ez következménye a kis Fermat-tételnek, és egyszerűen abból következik, hogy modulo p szemlélve a számokat, például az  kifejezést, ez véges sokféle maradékot adhat, melyeknek ezért ciklikusan, p periódussal ismétlődniük kell. E tétel az RSA (nyilvános kulcsú) titkosítási eljárásban talál fontos alkalmazásra.
 Egy, a moduláris számelméletben igen fontos általánosítás, prím modulus helyett tetszőleges egész modulusra az Euler–Fermat-tétel:
 Tetszőleges  pozitív egész számra, -nel jelölve az ehhez relatív prím pozitív egész számok számát (ez az ún. Euler-féle φ-függvény értéke az  helyen), érvényes az
 . 
Ez azért általánosítás, mert , ha  prímszám. 
 Ezt tovább terjeszti a következő állítás:
 Egy n elemű csoportban  teljesül minden g elemre (a Lagrange-tétel egy egyszerű következménye).
 Ezt alkalmazva a mod n redukált maradékosztályok szorzással alkotott csoportjára, az Euler–Fermat-tételt kapjuk. Speciálisan ha  prím, akkor e csoport  elemű, ekkor a kis Fermat-tétel adódik. Így minden redukált maradékosztályt eme számra, a csoport rendjére mint kitevőre emelve, tényleg az 1 maradékosztály adódik.
 Egy másféle általánosítás a Carmichael-tétel, amely a Carmichael-függvénnyel (lambda-függvény) áll kapcsolatban.
 Egy másik általánosítás lehetséges véges testekben is.
 Eszerint tetszőleges -elemű  véges testben az  polinomra:
  . 
Ez, ha q prímszám, a Fermat-tételt adja, hiszen eszerint xq azonosan x.

Lásd még 

 Bolyai számelméleti kutatásai
 Ribenboim, P. (1995). The New Book of Prime Number Records (3rd ed.). New York: Springer-Verlag. .

További információk 
 Alice és Bob - 22. rész: Alice, Bob és a kínaiak
 Alice és Bob - 23. rész: Alice és Bob prímszámok után nyomoz

Számelméleti tételek