Fermat-számok: definíció, képlet (2^{2^n}+1) és Fermat-prímek

Definíció és képlet

A Fermat-szám egy speciális pozitív szám, amelyet Pierre de Fermat-ról neveztek el. A Fermat-számok általános alakja

F n = 2 2 n + 1 {\displaystyle F_{n}=2^{2^{\\overset {n}{}}}+1}

ahol n egy nemnegatív egész szám. Röviden: F_n = 2^{2^n} + 1.

Az első Fermat-számok

Az első kilenc Fermat-szám (az OEIS A000215 szekvenciája) a következő:

• F0 = 2^{2^0} + 1 = 2^1 + 1 = 3
• F1 = 2^{2^1} + 1 = 2^2 + 1 = 5
• F2 = 2^{2^2} + 1 = 2^4 + 1 = 17
• F3 = 2^{2^3} + 1 = 2^8 + 1 = 257
• F4 = 2^{2^4} + 1 = 2^{16} + 1 = 65537
• F5 = 2^{2^5} + 1 = 2^{32} + 1 = 4294967297 = 641 × 6700417
• F6 = 2^{2^6} + 1 = 2^{64} + 1 = 18446744073709551617 = 274177 × 67280421310721
• F7 = 2^{2^7} + 1 = 2^{128} + 1 = 340282366920938463463374607431768211457 = 59649589127497217 × 5704689200685129054721
• F8 = 2^{2^8} + 1 = 2^{256} + 1 = 115792089237316195423570985008687907853269984665640564039457584007913129639937 = 1238926361552897 × 93461639715357977769163558199606896584051237541638188580280321

Alapvető tulajdonságok

• Összefüggés a termékekkel: a Fermat-számok között igaz a kimondottan hasznos reláció
  F₀ · F₁ · … · F_n-1 = F_n − 2. Ez az egyenlőség ad egyszerű bizonyítást arra, hogy a Fermat-számok páronként relatív prímek.
• Páronként relatív prímek: ha m ≠ n, akkor gcd(F_m, F_n) = 1. Ennek oka, hogy ha p osztója F_k valamely k ≤ n − 1-nek, akkor p nem oszthatja F_n = 2 + (termék), a fenti reláció miatt.
• Prímosztók kongruenciája: ha p egy prím és p | F_n, akkor a 2 moduláris rendjéből következik, hogy a rend ord_p(2) = 2^{n+1}, ezért 2^{n+1} osztójának kell lennie p−1-nek. Tehát minden prím osztó p esetén
  p ≡ 1 (mod 2^{n+1}).

Fermat-prímek és történet

Fermat eredetileg úgy gondolta, hogy minden F_n prím. Ez a sejtés azonban hamisnak bizonyult: Leonhard Euler 1732-ben megmutatta, hogy

• F₅ = 4294967297 nem prímszám; 641 osztója F₅.

A Fermat-prímnek nevezzük azokat a Fermat-számokat, amelyek ténylegesen prímek. Csak az alábbiak ismertek valóban prímeknek:

• F₀, F₁, F₂, F₃, F₄ (vagyis 3, 5, 17, 257, 65537).

Az összes többi F_n esetében n ≥ 5-ről ismert, hogy sok esetben összetett, és több számról kiderült már, hogy nem prímszám; a Fermat-prímek véges vagy végtelen volta máig nyitott kérdés.

Faktorok, számítógépes keresések

Az erőforrásigény miatt a Fermat-számok faktorizálása nehéz feladat. A korábbi eredmények szerint faktorizálás szempontjából sok F_n-hez ismerünk nemtriviális prímosztókat; például a fenti listában szereplő F₅–F₈ esetén már megadtuk is néhány faktort. 2007-ig csak az első 12 Fermat-számot sikerült teljes mértékben faktorizálni; a kutatás azóta is folyamatosan zajlik, részleges és teljes faktorizációkat egyaránt közölnek kutatócsoportok és elosztott számítási projektek.

Alkalmazások és kapcsolódó eredmények

• Szerkeszthető sokszögek: Carl Friedrich Gauss megmutatta, hogy egy szabályos n-szög szerkeszthető körzővel és vonalzóval pontosan akkor, ha n a 2 hatványának és különböző Fermat-prímek szorzatának alakjában írható fel. Emiatt a Fermat-prímek fontossá váltak a klasszikus szerkesztési problémákban.
• Elméleti számelmélet: a Fermat-számok tulajdonságai (paritás, rendek, faktorstruktúra) fontos példákat adnak a moduláris aritmetikában, rendek tanulmányozásában és prímkeresési technikák tesztelésében.

Összefoglalás

A Fermat-számok egyszerű, de mélyen strukturált számsorozatot adnak: F_n = 2^{2^n} + 1. Bár Fermat remélte, hogy mind prímek, csak az első öt (F₀–F₄) ismeretes biztosan prímként; a többi legtöbb esetben összetett, és számos prímfaktort találtak már. A számok páronként relatív prímek, és fontos szerepük van például a szabályos sokszögek szerkeszthetőségéről szóló elméletben.