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
szerkesztésFermat felfedezése
szerkesztésPierre 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ésKí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ésFermat 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 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
szerkesztés- Bolyai számelméleti kutatásai
- Ribenboim, P. (1995). The New Book of Prime Number Records (3rd ed.). New York: Springer-Verlag. ISBN 0-387-94457-5.