Fermatova števila (F_n = 2^{2^n}+1): definicija, formula, primeri in praštevila

Fermatova števila: definicija, formula F_n=2^{2^n}+1, primeri, faktorizacije in znane Fermatove praštevila (F0–F4). Raziskujte lastnosti, dokaze in zgodovino.

Fermatovo število je posebno pozitivno število, poimenovano po Pierru de Fermatu. Definicija je preprosta:

F_n = 2^{2^n} + 1, kjer je n nenegativno celo število. Za vizualni zapis formule je v izvirnem gradivu prisoten tudi naslednji prikaz:

Primeri

• 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

Več faktorizacij (vključno s faktorji za mnoga nadaljnja Fermatova števila) je zbranih v različnih virov; do leta 2007 je bilo v celoti razloženih prvih 12 Fermatovih števil. Faktorizacije so pogosto na voljo na spletnih straneh, ki sledijo faktorjem Fermatovih števil (npr. "Prime Factors of Fermat Numbers").

Lastnosti

• Povezava med Fermatovimi števili: veljajo identitete
  F_n = (F₀ · F₁ · … · F_n−1) + 2, kar izhaja iz telescopičnega produkta (product_{i=0}^{n-1} F_i = 2^{2^{n}} − 1). Ta enostavna identiteta se pogosto uporablja v dokazih lastnosti Fermatovih števil.
• Medsebojna tuja delitelja: iz prejšnje enačbe sledi, da sta vsaki dve različni Fermatovi števili sorazmerno praštevilsko (pairwise coprime): če p deli F_i in F_j za i < j, potem p deli tudi (F_0·…·F_{j−1}) + 2 in (F_0·…·F_{j−1}) − 2, torej deli 4, kar vodi v protislovje za velike p. Zato nobeno praštevilo ne deli dveh različnih Fermatovih števil.
• Pogoj za praštevilo oblike 2^m + 1: če je število 2^m + 1 praštevilo in m > 0, potem mora biti m potenca dvojke. Dokaz: če m = a·b s liho b > 1, potem velja 2^m + 1 = (2^a)^b + 1 in izraz (x^b + 1) z liho b faktorira kot (x + 1)·(…), zato je 2^a + 1 pravi delitelj, kar pomeni, da 2^m + 1 ni praštevilo. Zato so vsi Fermatovi kandidati za praštevila pravzaprav števil F_n z m = 2^n.

Praštevila med Fermatovimi števili

Fermatova praštevilska števila so Fermatova števila, ki so praštevila. Do danes so znana le pet Fermatovih praštevil: F₀, F₁, F₂, F₃ in F₄. Vsi naslednji Fermatovi členki, ki so bili preverjeni (npr. F₅, F₆, ...), se izkažejo za sestavljene.

Pepinov test

Za preverjanje praštevilnosti Fermatovih števil (n ≥ 1) se pogosto uporablja Pepinov test. Test pravi:

F_n je praštevilo natanko tedaj, ko velja 3^{(F_n−1)/2} ≡ −1 (mod F_n).

Pri izvajanju Pepinovega testa se običajno računa modularni potek z izkoriščanjem hitrega modularnega potenciranja. Test je zelo učinkovit za posamezna Fermatova števila, ki jih je mogoče obdelati z razpoložljivimi računalniškimi sredstvi, dokler velikost F_n ni previsoka.

Zgodovina in zanimivi primeri

• Leonhard Euler je že leta 1732 pokazal, da je F₅ sestavljeno število, saj ga deli 641 (Euler je dejansko pokazal, da 641 | 2^{32} + 1, in našel še dopolnilni faktor 6700417).
• Kljub temu da Fermat prvotno domnevno trdil, da so vsa F_n praštevila, se je izkazalo, da to ne drži. Ne vemo pa, ali obstaja neskončno mnogo Fermatovih praštevil — to ostaja odprto vprašanje v teoriji števil.

Faktorizacije in odprta vprašanja

Veliko Fermatovih števil je bilo delno faktoriranih, za nekatera so znani vsi praštevilski faktorji, za druga pa le nekateri. Organizirane pobude in spletne zbirke (npr. strani, ki spremljajo "Prime Factors of Fermat Numbers") redno objavljajo najnovejše ugotovitve. Glavna odprta vprašanja so:

• Ali obstaja še kakšno Fermatovo praštevilo z n ≥ 5?
• Koliko Fermatovih števil je popolnoma faktoriranih in kako učinkovito se domnevne velike faktorizacije izračunajo z današnjimi orodji?

Če želite poglobljeno študijo ali seznam znanih faktorjev, poiščite specializirane vire in baze podatkov faktorjev Fermatovih števil ter objave v literaturi o faktorizaciji velikih števil.

Vprašanja in odgovori

V: Kaj je Fermatovo število?

V: Koliko je Fermatovih števil?

V: Katerih je prvih devet Fermatovih števil?

V: Kaj lahko rečemo o praštevilkah v obliki 2n + 1?

V: Kje lahko najdemo faktorizacije za vseh 12 znanih faktoriranih Fermatovih števil?

V: Kdo je bil Pierre de Fermaat?

Išči po črki