Kis Fermat-tétel

A Wikipédiából, a szabad enciklopédiából

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 Leibniz tette meg (ld. 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 a-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 e 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 a kis tétele bizonyítását (sem, ahogy általában is nagyon ritkán adott bizonyítást eredményeire). Az első, akinek ez bizonyíthatóan sikerült, Gottfried Wilhelm Leibniz, egy dátumozatlan 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.

Ld. 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 modulo p (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
.
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 gn=1 teljesül minden g elemre (ez 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 n = p prím, akkor e csoport p-1 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]