Fermat-luvut: määritelmä, kaava ja tunnetut alkuluvut

Fermat-luku on erityinen positiivinen luku, joka on muotoa

F_n = 2^2ⁿ + 1 $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 F_n = 2^2ⁿ + 1 (n ≥ 0). Ensimmäiset Fermat-luvut ovat (OEIS-sarja A000215):

F₀ = 2^2⁰ + 1 = 2¹ + 1 = 3
F₁ = 2^2¹ + 1 = 2² + 1 = 5
F₂ = 2^2² + 1 = 2⁴ + 1 = 17
F₃ = 2^2³ + 1 = 2⁸ + 1 = 257
F₄ = 2^2⁴ + 1 = 2¹⁶ + 1 = 65537
F₅ = 2^2⁵ + 1 = 2³² + 1 = 4294967297 = 641 × 6700417
F₆ = 2^2⁶ + 1 = 2⁶⁴ + 1 = 18446744073709551617 = 274177 × 67280421310721
F₇ = 2^2⁷ + 1 = 2¹²⁸ + 1 = 340282366920938463463374607431768211457 = 59649589127497217 × 5704689200685129054721
F₈ = 2^2⁸ + 1 = 2²⁵⁶ + 1 = 115792089237316195423570985008687907853269984665640564039457584007913129639937 = 1238926361552897 × 93461639715357977769163558199606896584051237541638188580280321

Alkuluvut ja tunnetut tekijät

Fermat oletuksessaan väitti, että kaikki luvut muotoa F_n olisivat alkulukuja, mutta tämä osoittautui vääräksi: Euler löysi vuonna 1732 luvun 641, joka jakaa F₅, joten F₅ ei ole alkuluku. Nykyisin tiedetään, että ainoat tunnetut Fermat-luvut, jotka ovat alkulukuja, ovat F₀, ..., F₄ (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 2^k on parillinen). Lisäksi Fermat-luvut ovat keskenään koprimeja: jos m ≠ n, niin gcd(F_m, F_n) = 1. Tämä seuraa identiteetistä F₀ · F₁ · ... · F_n−1 = F_n − 2, joten mikään alkutekijä ei voi esiintyä kahdessa eri Fermat-luvussa.
Rajaus alkutekijöille: Jos p on pariton alkutekijä Fermat-luvulle F_n, niin 2ⁿ⁺¹ on ord_p(2). Tästä seuraa, että p ≡ 1 (mod 2ⁿ⁺¹); toisin sanoen jokaisen F_n:n parittoman alkutekijän on oltava muotoa 1 + t·2ⁿ⁺¹.
Pépinin testi: Fermat-luvun F_n (n ≥ 1) alkuluvun testaamiseen käytetään tehokasta Pépinin testiä: F_n on alkuluku täsmälleen silloin kun 3^(F_n−1)/2 ≡ −1 (mod F_n). Testissä kantaa 3 voi korvata muullakin luvulla, jonka Jacobin symboli (a/F_n) = −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 2^k · 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 F_n indeksillä n ≥ 5; kaikki tunnetut Fermat-alkuluvut ovat siis F₀–F₄. 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ä).

Mielenkiintoisia asioita Fermat'n luvuista

Kahdella Fermat-luvulla ei ole yhteisiä jakajia.
Fermat'n luvut voidaan laskea rekursiivisesti: Jos haluat saada N:nnen luvun, kerrotaan kaikki sitä edeltävät Fermat-luvut ja lisätään tulokseen kaksi.

Mihin niitä käytetään

Nykyään Fermat'n lukuja voidaan käyttää satunnaislukujen tuottamiseen välillä 0 ja jonkin N-arvon välillä, joka on 2:n potenssi.

Fermat'n arvaus

Fermat arveli näitä lukuja tutkiessaan, että kaikki Fermat-luvut olivat alkulukuja. Leonhard Euler osoitti tämän vääräksi, kun hän kertoi F 5 {\displaystyle F_{5}} $F_{5}$ vuonna 1732.

Kysymyksiä ja vastauksia

K: Mikä on Fermat'n luku?

A: Fermat-luku on erityinen positiivinen luku, joka on nimetty Pierre de Fermatin mukaan. Se saadaan kaavalla F_n = 2^2^(n) + 1, jossa n on ei-negatiivinen kokonaisluku.

K: Kuinka monta Fermat-lukua on olemassa?

V: Vuoteen 2007 mennessä vain 12 ensimmäistä Fermat-lukua on laskettu täysin faktorisoituna.

K: Mitkä ovat yhdeksän ensimmäistä Fermat-lukua?

A: Yhdeksän ensimmäistä Fermat-lukua ovat F0 = 3, F1 = 5, F2 = 17, F3 = 257, F4 = 65537, F5 = 4294967297 (641 × 6700417), F6 = 18446744073709551617 (274177 × 67280421310721), F7 = 340282366920938463463374607431768211457 (59649589127497217 × 5704689200685129054721), ja F8 = 115792089237316195423570985008687907853269984665640564039457584007913129639937 (1238926361552897 × 93461639715357977769163558199606896584051237541638188580280321).

Kysymys: Mitä voidaan sanoa alkuluvuista, joiden muoto on 2n + 1?

V: Jos 2n + 1 on alkuluku ja n > 0, voidaan osoittaa, että n:n on oltava kahden potenssi. Jokainen alkuluku muodossa 2n + 1 on myös Fermat-luku, ja tällaisia alkulukuja kutsutaan Fermat-lukuiksi. Ainoat tunnetut Fermat-luvut ovat 0-4.

Kysymys: Mistä löytyy kaikkien 12 tunnetun faktoroidun Fermat-luvun faktorisoinnit?

V: Kaikkien 12 tunnetun faktoroidun Fermat-luvun faktorisoinnit löytyvät osoitteesta Prime Factors of Fermat Numbers.

K: Kuka oli Pierre de Fermaat?

V: Pierre de Fermaat oli 1600-luvulla elänyt vaikutusvaltainen ranskalainen matemaatikko, jonka työ loi suuren osan modernin matematiikan perustasta. Hänet tunnetaan parhaiten panoksestaan todennäköisyysteoriaan ja analyyttiseen geometriaan sekä kuuluisasta viimeisestä teoreemastaan, joka pysyi ratkaisemattomana vuoteen 1995 asti, jolloin Andrew Wiles lopulta todisti sen algebrallisesta geometriasta peräisin olevien menetelmien avulla.