Kis Fermat-tétel

A Wikipédiából, a szabad lexikonból.

A kis Fermat-tétel egy számelméleti tétel, mely a maradékok (egész számok közti kongruenciák, moduláris aritmetika) 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 tétel szerint bármely $p$ prímszámra teljesül bármely $a \in \mathbb{Z}$ egész szám esetén, hogy

$a^p \equiv a \pmod{p}$ .

Azaz ha veszünk tetszés szerint egy $a$ egész számot, megszorozzuk önmagával $p$ -szer, és levonjuk belőle az a-t, akkor az eredmény $p$ -vel osztható.

Gyakrabban a következő (és történelmileg hitelesebb) alakban is szokás kimondani: ha $p$ prímszám és $a \in \mathbb{Z}$ egy e prímhez relatív prím egész, akkor

$a^{p-1} \equiv 1 \pmod{p}$ .

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

Tartalomjegyzék

1 Történelem
- 1.1 Fermat felfedezése
- 1.2 A Kínai sejtés?
2 Bizonyítási lehetőségek
3 Megfordítások
4 Általánosítások
5 Lásd még

[szerkesztés] Történelem

[szerkesztés] 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 a^p-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.

[szerkesztés] 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 $2^p \equiv 2 \pmod{p}$ . Az igaz, hogy ha p prím, akkor $2^p \equiv 2 \pmod{p}$ (ez a kis Fermat-tétel egy speciális esete, ha $a = 2$ ), ám ennek megfordítása, s így a sejtés egészében, hamis, mert ha $2^m \equiv 2 \pmod{m}$ akkor még nem biztos, hogy $m$ prím.

Pierre Fréderique Sarrus francia matematikus találta 1820-ban az $m = 341$ 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 $2^{341} \equiv 2 \pmod{341}$ , de $341 = 11 \cdot 31$ 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).

[szerkesztés] 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 $a^p \equiv a \pmod{p}$ . Ekkor, ha az $a$ és $p$ számok relatív prímek, azaz legnagyobb közös osztójuk 1: $\left( a, p \right) = 1$ , a fenti kongruencia egyszerűsíthető a $p$ modulushoz relatív prím szorzóval, és így $a^{p-1} \equiv a^{1-1} \equiv a^0 \equiv 1 \pmod{p}$ (ha pedig $a$ és $p$ nem lennének relatív prímek, $p|a \Rightarrow p|a^p$ miatt $a, a p$ mindketten 0-val lennének kongruensek mod(p), és így szintén kongruensek lennének).
Fordítva, az $a^{p-1} \equiv 1 \pmod{p}$ kongruencia tetszőleges $a,p \in \mathbb{Z}$ számok esetén szorozható a-val, és így $a^p \equiv a \pmod{p}$ adódik.

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

[szerkesztés] Megfordítások

Az egyik ilyen az az állítás lehet, hogy ha $a^{n-1} \equiv 1 \pmod{n}$ , és $\left( a,n \right) = 1$ , akkor $n$ prím. Ezt azonban láttuk, hogy nem igaz: minden $a \in \mathbb{Z}$ alapszámhoz léteznek olyan $n$ 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; 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). Pl. p=5-re már $4^2 \equiv 16 \equiv 1 \pmod{5}$ , é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.).

[szerkesztés] Általánosítások

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

$a^{p-1}\pmod{p}\equiv \left\{ \begin{matrix} 0,\quad\,\ \ &&\mbox{ha }p|a; \ \ \ \ \ \ \ \ \ \ \ \\ \ 1,\qquad\,&&\mbox{ha }\left(p,a\right)=1;\ \ \,\\ \end{matrix} \right.$

Ez az összes $\left( a,p \right) \in \mathbb{Z}$ számpárra megadja az

a p - 1

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 m ≡ n (mod p-1), akkor a^m ≡ aⁿ (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, pl. az

a p

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írá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

n

pozitív egész számra, $\varphi (n)$ -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

n

helyen), érvényes

$a^{\varphi (n)} \equiv 1 \pmod{n}$ .

Ez azért általánosítás, mert $\varphi(p) = p-1$ ha

p

prímszám.

Ezt tovább terjeszti a következő állítás:

Egy n elemű csoportban gⁿ=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.

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