Kis Fermat-tétel

számelméleti állítás
Ez a közzétett változat, ellenőrizve: 2023. június 5.

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

szerkesztés

Fermat felfedezése

szerkesztés

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

szerkeszté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

szerkesztés

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

szerkesztés
  • 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

szerkesztés
  • 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 mn (mod p-1), akkor aman (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.
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.
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

szerkesztés

További információk

szerkesztés