Fermat-számok

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

${\displaystyle F_{n}=2^{2^{n}}+1}$, ahol ${\displaystyle 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:

F₀ = 2¹ + 1 = 3

F₁ = 2² + 1 = 5

F₂ = 2⁴ + 1 = 17

F₃ = 2⁸ + 1 = 257

F₄ = 2¹⁶ + 1 = 65537

F₅ = 2³² + 1 = 4294967297 = 641 × 6700417

F₆ = 2⁶⁴ + 1 = 18446744073709551617 = 274177 × 67280421310721

F₇ = 2¹²⁸ + 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

Bővebben: Fermat-prímek

Ha F_n = 2ⁿ + 1 prímszám, akkor – amint ez megmutatható – n szükségképp 2-hatvány. Ugyanis ha nem lenne 2-nek egy hatványa, akkor létezne ${\displaystyle n}$-nek 1-nél nagyobb páratlan osztója, mondjuk n = ab, ahol ${\displaystyle b\geq 3}$ páratlan és ${\displaystyle a\geq 1}$ természetes számok, így pedig ${\displaystyle 2^{n}+1=2^{(ab)}+1=(2^{a})^{b}+1\equiv (-1)^{b}+1=0{\pmod {(2^{a}+1)}}}$. Más szóval, minden 2ⁿ + 1 alakú prím Fermat-szám, így Fermat-prímnek nevezendő. Az ismert Fermat-prímek a következők: F₀, F₁, F₂, F₃ és F₄.

Tulajdonságok

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ó:

${\displaystyle F_{n}=(F_{n-1}-1)^{2}+1}$,

${\displaystyle F_{n}=F_{n-1}^{2}-2(F_{n-2}-1)^{2}}$,

${\displaystyle F_{n}=F_{n-1}+2^{2^{n-1}}F_{0}\cdots F_{n-2}}$,

${\displaystyle F_{n}=F_{0}\cdots F_{n-1}+2}$ ${\displaystyle =}$ ${\displaystyle \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).

Azt viszonlyag könnyű belátni, hogy egyik Fermat-szám sem valódi prímhatvány.

Prímteszt

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

${\displaystyle 3^{\frac {F_{n}-1}{2}}\equiv -1{\pmod {F_{n}}}}$

teljesül.

Prímosztók

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

Mivel

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

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

${\displaystyle 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 F₅-ö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=F₃-t kapjuk, ami a fentiek szerint nem oszthatja F₅-öt tehát az első igazi eset p=641 és ez valóban osztó.

Sejtések

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.

Források

• 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?