Fermatovo praštevilo

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje

Fermatovo práštevílo [fermájevo ~] je število oblike:

 F_{n} \equiv 2^{2^{ \overset{n} {}}} + 1 \!\, ,

kjer je n naravno število.

Cela števila v splošni obliki:

2^{2^n}+1 ,

kjer je n naravno število se imenujejo Fermatova števila. Fermat je nepravilno domneval, da so vsa takšna števila praštevila, čeprav ni imel dokaza. Prvih pet Fermatovih števil 3, 5, 17, 257, 65537, ki odgovarjajo n = 0, 1, 2, 3, 4, so vsa praštevila. Euler je prvi leta 1732 dokazal, da ta Fermatova domneva ne velja, in pokazal kako je število 641 delitelj Fermatovega števila F5, saj je:[1]

 \begin{align} F_{5} &= 2^{2^{5}} + 1 = 2^{4} \left( 2^{7} \right)^{4} + 1 = \left( 2^{7} \cdot 5 - 5^{4} + 1 \right) \left( 2^{7} \right)^{4} + 1 \\
&= \left( 1 + 2^{7} \cdot 5 \right) \left( 2^{7} \right)^{4} + 1 - \left( 2^{7} \cdot 5 \right)^{4} \\
&= \left( 1 + 2^{7} \cdot 5 \right) \left( \left( 2^{7} \right)^{4} \left( 1 - 5 \cdot 2^{7} \right) \left( 1 + \left( 5 \cdot 2^{7} \right)^{2} \right) \right) \\
&= 641 \cdot 6700417 = 4294967297 \!\, , \end{align}

oziroma:

 F_{5} = 2^{32} + 1 = \left( 2^{9} + 2^{7} + 1 \right) \left( 2^{27} - 2^{21} + 2^{19} - 2^{17} + 2^{14} - 2^{9} - 2^{7} + 1 \right) \!\, .

Euler je dokazal, da mora biti vsak faktor Fn oblike k2n+1 + 1, kar je kasneje Lucas leta 1878 izboljšal na k2n+2 + 1.

V bistvu ne poznamo nobenega Fermatovega števila za n > 4, ki bi bilo praštevilo in tako domnevamo, da so to tudi vsa praštevila te oblike. Ne vemo tudi ali obstaja neskončno mnogo Fermatovih praštevil. Prva Fermatova števila so (OEIS A000215):

F0 = 21 + 1 = 3
F1 = 22 + 1 = 5
F2 = 24 + 1 = 17
F3 = 28 + 1 = 257
F4 = 216 + 1 = 65537
F5 = 232 + 1 = 4294967297 = 641 · 6700417
F6 = 264 + 1 = 18446744073709551617 = 274177 · 67280421310721
F7 = 2128 + 1 = 340282366920938463463374607431768211457 = 59649589127497217 · 5704689200685129054721
F8 = 2256 + 1 = 115792089237316195423570985008687907853269984665640564039457584007913129639937 = 1238926361552897 · 93461639715357977769163558199606896584051237541638188580280321

Poznamo le razcep prvih 12 Fermatovih števil.

Gauss je dokazal, da lahko vsak pravilni mnogokotnik z m oglišči konstruiramo samo z ravnilom in šestilom tedaj in le tedaj, kadar lahko zapišemo m kot:

m = 2k Fr1 Fr2 ... Frt,

kjer je k ≥ 0 in so drugi množitelji (faktorji) poljubna praštevila zgornje oblike Fermatovega števila Fn.

Osnovne značilnosti[uredi | uredi kodo]

Za Fermatova števila veljajo naslednje rekurenčne enačbe:

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

za n ≥ 1 in:

 F_{n} = F_{n-1} + 2^{2^{n-1}}F_{0} \cdots F_{n-2} \!\,
 F_{n} = F_{n-1}^2 - 2(F_{n-2}-1)^2 \!\,
 F_{n} = F_{0} \cdots F_{n-1} + 2 \!\,

za n ≥ 2. Vse enačbe lahko dokažemo s popolno indukcijo. Iz zadnje enačbe sledi Goldbachov izrek: nobeni dve Fermatovi števili nimata skupnega faktorja, oziroma različna Fermatova števila so si med seboj tuja.

Fermatova števila so poseben primer Prothovih števil (za n=2^{n} in k=1).

Glej tudi[uredi | uredi kodo]

Sklici[uredi | uredi kodo]

  1. ^ Hsiung (1995), str. 39.

Viri[uredi | uredi kodo]

Zunanje povezave[uredi | uredi kodo]