Fermat-luku on erityinen positiivinen luku, joka on muotoa

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

Missä n on ei-negatiivinen kokonaisluku. Fermat-luvut on nimetty matemaatikko Pierre de Fermatin mukaan. Yleisesti merkitään

Määritelmä ja perusesimerkkejä

Fermat-luku määritellään tarkemmin kaavalla Fn = 22n + 1 (n ≥ 0). Ensimmäiset Fermat-luvut ovat (OEIS-sarja A000215):

  • F0 = 220 + 1 = 21 + 1 = 3
  • F1 = 221 + 1 = 22 + 1 = 5
  • F2 = 222 + 1 = 24 + 1 = 17
  • F3 = 223 + 1 = 28 + 1 = 257
  • F4 = 224 + 1 = 216 + 1 = 65537
  • F5 = 225 + 1 = 232 + 1 = 4294967297 = 641 × 6700417
  • F6 = 226 + 1 = 264 + 1 = 18446744073709551617 = 274177 × 67280421310721
  • F7 = 227 + 1 = 2128 + 1 = 340282366920938463463374607431768211457 = 59649589127497217 × 5704689200685129054721
  • F8 = 228 + 1 = 2256 + 1 = 115792089237316195423570985008687907853269984665640564039457584007913129639937 = 1238926361552897 × 93461639715357977769163558199606896584051237541638188580280321

Alkuluvut ja tunnetut tekijät

Fermat oletuksessaan väitti, että kaikki luvut muotoa Fn olisivat alkulukuja, mutta tämä osoittautui vääräksi: Euler löysi vuonna 1732 luvun 641, joka jakaa F5, joten F5 ei ole alkuluku. Nykyisin tiedetään, että ainoat tunnetut Fermat-luvut, jotka ovat alkulukuja, ovat F0, ..., F4 (3, 5, 17, 257, 65537).

Monia suurempia Fermat-lukuja on faktoroitu osittain tai kokonaan; esimerkiksi useiden Fn tekijöitä on löydetty hajautetussa laskennassa. Vuoteen 2007 mennessä vain 12 ensimmäistä Fermat-lukua oli laskettu kokonaan (kirjoitettu alkulukujen tulona), ja myöhemmin on löydetty lisää tekijöitä useille suuremmille n:ille. Tästä aiheesta löytyy laajoja luetteloita, kuten "Prime Factors of Fermat Numbers".

Tärkeitä ominaisuuksia

  • Parittaisuus ja toisistaan riippumattomuus: Kaikki Fermat-luvut ovat parittomia (koska 2k on parillinen). Lisäksi Fermat-luvut ovat keskenään koprimeja: jos m ≠ n, niin gcd(Fm, Fn) = 1. Tämä seuraa identiteetistä F0 · F1 · ... · Fn−1 = Fn − 2, joten mikään alkutekijä ei voi esiintyä kahdessa eri Fermat-luvussa.
  • Rajaus alkutekijöille: Jos p on pariton alkutekijä Fermat-luvulle Fn, niin 2n+1 on ordp(2). Tästä seuraa, että p ≡ 1 (mod 2n+1); toisin sanoen jokaisen Fn:n parittoman alkutekijän on oltava muotoa 1 + t·2n+1.
  • Pépinin testi: Fermat-luvun Fn (n ≥ 1) alkuluvun testaamiseen käytetään tehokasta Pépinin testiä: Fn on alkuluku täsmälleen silloin kun 3(Fn−1)/2 ≡ −1 (mod Fn). Testissä kantaa 3 voi korvata muullakin luvulla, jonka Jacobin symboli (a/Fn) = −1.

Merkitys ja sovellukset

Fermat-luvuille on useita matemaattisia yhteyksiä:

  • Konstruktio ja geometria: Carl Friedrich Gauss osoitti, että säännöllinen n-kulmio on rakentavissa suorakulmaisilla välineillä (viivain ja harppi) täsmälleen silloin kun n on muoto 2k · p1 · p2 · ... · pr, missä p1,...,pr ovat erilaisia Fermat-alkulukuja. Tämän vuoksi löydetyt Fermat-alkuluvut (3, 5, 17, 257, 65537) liittyvät suoraan monien säännöllisten monikulmioiden konstruktion mahdollisuuteen.
  • Käytännön laskenta ja hajautus: Fermat-lukujen faktorisointi on kiinnostavaa paitsi teoreettisesti myös käytännön hajautetun laskennan kannalta; suurten Fermat-lukujen tekijöitä etsitään aktiivisesti tietokoneilla ja yhteisöprojekteissa.

Tila vuonna 2024

Tähän mennessä (2024) ei ole löydetty uusia Fermat-alkulukuja Fn indeksillä n ≥ 5; kaikki tunnetut Fermat-alkuluvut ovat siis F0–F4. Suurten Fermat-lukujen täydellinen faktorisointi on erittäin vaikeaa ja monille n on löydetty vain osatekijöitä. Tutkimus jatkuu sekä teoreettisesti että laskennallisesti.

Lisätietoja ja täydellisiä listoja tunnetuista tekijöistä löydät alan tietokannoista ja jaetuista projekteista (esim. listaukset Fermat-lukujen alkutekijöistä).