Fermat-számok

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

A Fermat-számok a matematikában elsőként Pierre de Fermat (ejtsd: pier dö fermá) által tanulmányozott (és róla elnevezett) pozitív egész számok, mégpedig a következő sorozat elemei:

 F_{n} = 2^{2^n} + 1

(n nemnegatív egész). Tehát ha egy kettőhatványt kettes hatványalapra emelünk és hozzáadunk egyet, Fermat-számot kapunk.

Az első nyolc Fermat-szám:

F0 = 21 + 1 = 3
F1 = 22 + 1 = 5
F2 = 24 + 1 = 17
F3 = 28 + 1 = 257
F4 = 216 + 1 = 65537
F5 = 232 + 1 = 4294967297 = 641 × 6700417
F6 = 264 + 1 = 18446744073709551617 = 274177 × 67280421310721
F7 = 2128 + 1 = 340282366920938463463374607431768211457 = 59649589127497217 × 5704689200685129054721

Jelenleg csak az első 12 Fermat-szám prímtényezőkre bontását ismerjük teljesen. Az ismert információk megtalálhatók a (Prime Factors of Fermat Numbers) lapon.

Fermat-prímek[szerkesztés | forrásszöveg szerkesztése]

Ha Fn = 2n + 1 prímszám, akkor – amint ez megmutatható – n szükségképp 2-hatvány. (Ha nem ilyen, akkor van 1-nél nagyobb páratlan osztója, mondjuk n = ab, ahol 1 < b páratlan, úgy 2n + 1 = (2a)b + 1 ≡ (‒1)b + 1 ≡ 0 (mod 2a + 1).) Más szóval, minden 2n + 1 alakú prím Fermat-szám, így Fermat-prímnek nevezendő. Az ismert Fermat-prímek a következők: F0,…,F4.

Tulajdonságok[szerkesztés | forrásszöveg szerkesztése]

A Fermat-számok sorozata eleget tesz a következő, rekurzív definícióra is alkalmas egyenlőségeknek (n ≥ 2-re), melyek mindegyike indukcióval belátható:

 F_{n} = (F_{n-1}-1)^{2}+1
 F_{n} = F_{n-1}^2 - 2(F_{n-2}-1)^2
 F_{n} = F_{n-1} + 2^{2^{n-1}}F_{0} \cdots F_{n-2}
 F_{n} = F_{0} \cdots F_{n-1} + 2  =  \prod_{i=0}^{n-1} F_{i} +2

Az utolsó egyenlőség felhasználásával belátható Goldbach tétele; ti. bármely két Fermat-szám relatív prím (mellesleg, ebből meg bizonyítható, hogy végtelen sok prímszám van).

Prímteszt[szerkesztés | forrásszöveg szerkesztése]

Mint speciális alakú számokra oly gyakran, egyszerű prímteszt van Fermat-számokra. Ha n\geq 1, akkor az F_n=2^{2^n}+1 Fermat-szám pontosan akkor prím, ha

3^{\frac{F_n-1}{2}}\equiv -1 \pmod{F_n}

teljesül.

Prímosztók[szerkesztés | forrásszöveg szerkesztése]

Ha k legalább 2, az Fk szám minden prímosztója p=x2k+2+1 alakú. Ennek bizonyításához legyen d 2 rendje mod p, azaz a legkisebb olyan kitevő, hogy 2^d\equiv 1\pmod{p}. Mivel

2^{2^k}\equiv -1 \pmod{p},

d nem osztja 2k-t de osztja 2k+1-et. de ekkor d csak 2k+1 lehet. Másrészt a kis Fermat-tétel miatt d osztója p-1-nek, azaz p=x2k+1+1 alakú, tehát 8-cal osztva 1-et ad maradékul. Ezért a Legendre-szimbólum tulajdonságai miatt

2^{\frac{p-1}{2}}\equiv\left(\frac{2}{p}\right)\equiv 1\pmod{p}

ahonnan adódik, hogy d osztja (p-1)/2-t, ami azonos azzal, amit állítottunk.

Ez megkönnyíti a Fermat-számok prímfelbontását, ami a Mersenne-prímek kutatásához hasonló internetes-programozói versennyé kezd válni. Például ha F5-öt próbáljuk felbontani, a prímosztókat 128x+1 alakban kell keresnünk. Az x=1,3,4 esetek kiesnek, mert ekkor 128x+1 összetett, x=2-re 257=F3-t kapjuk, ami a fentiek szerint nem oszthatja F5-öt tehát az első igazi eset p=641 és ez valóban osztó.

Sejtések[szerkesztés | forrásszöveg szerkesztése]

Sok sejtést lehet a Fermat-számokról felállítani és ezek mindegyike reménytelenül nehéz. Sejtjük, de nem tudjuk bizonyítani, hogy az ismerteken kívül nincs több prím. De még azt sem tudjuk, hogy végtelen sok összetett Fermat-szám van, hogy mind négyzetmentes, vagy akár, hogy végtelen sok négyzetmentes Fermat-szám van. Azt könnyű belátni, hogy egyik sem valódi prímhatvány.


Források[szerkesztés | forrásszöveg szerkesztése]

  • 17 Lectures on Fermat Numbers: From Number Theory to Geometry, Michal Krizek, Florian Luca, Lawrence Somer, Springer, CMS Books 9, 257 oldal ISBN 0387953329
  • Courant-Robins: Mi a matematika?.