Ugrás a tartalomhoz

Matematikatörténet problémákon keresztül

Balka Richárd, Egri-Nagy Attila, Juhász Tibor

Kempelen Farkas Hallgatói Információs Központ

A álprímekről

A álprímekről

Az úgynevezett kis Fermat-tételt, miszerint ha az egész szám nem osztható a prímmel, akkor

Pierre Fermat sejtette meg 1636-ban, bizonyítást azonban nem adott rá. Az első bizonyítást a rendelkezésre álló adatok alapján Gottfried Wilhelm Leibniz-nek tulajdonítják. Felmerül a kérdés, hogy ez a tétel alkalmas-e prímtesztnek: igaz-e hogy ha eleget tesz a fenti kongruenciának, akkor szükségképpen prím. Azt, hogy a kérdésre a válasz nemleges, Bolyai János a következő példával illusztrálta: és választással osztható -gyel, és nyilván nem prím. Valóban, , és így

ahonnan a kongruencia mindkét oldalának négyzetre emelésével kapjuk az állítást. Bolyai egy az édesapjának címzett levelében azt állítja, hogy erre a példára nem vaktában, hanem „elmélet után menve” talált. Ezen „elmélet” alatt vélhetően az alábbi tételét értette.

6.2. Tétel. Legyenek és prímszámok, valamint olyan egész, melynek sem sem nem osztója. Ha

akkor

Bizonyítás gyanánt Bolyai eredeti gondolatmenetét közöljük. A kis Fermat-tétel szerint

Az első kongruencia mindkét oldalát , a másodikét kitevőre emelve kapjuk, hogy

Mivel a modulusok relatív prímek,

teljesül minden a feltételeknek eleget tevő -ra, -re és -ra. Ha ezt megszorozzuk az

kongruenciával, akkor a tétel állításában szereplő kongruenciát kapjuk, tehát elegendő ez utóbbi teljesülésének feltételeit vizsgálni. (6.2) szerint léteznek olyan és egészek, hogy és , így (6.4) pontosan akkor teljesül, ha

ami az és kongruenciák együttes fennállásával ekvivalens. Tehát a tétel érvényes.

Bolyai az speciális esetet vizsgálva juthatott el a , prímekhez. Ekkor ugyanis és , melyből a tétel szerint következik.

Megjegyezzük, hogy a fenti tételt (csak az esetre) először Sir James Hopwood Jeans publikálta [5] évtizedekkel Bolyai János halála után. Ha az összetett szám és valamely -ra, akkor -et alapú álprímnek nevezzük. A 341, mint példa ilyenre, már Bolyai előtt is ismert volt: Pierre Fréderique Sarrus találta meg először 1820-ban.

Bolyai igen szellemes módszerrel látta be, hogy az egész is alapú álprím. Ehhez a

triviálisan fennálló kongruenciát vette alapul, majd annak mindkét oldalát először négyzetre, majd -ra emelve a

kongruenciához jutott. Mivel összetett szám, valóban álprím.