Fermattal (original) (raw)

Frå Wikipedia – det frie oppslagsverket

Fermattala, som er oppkalla etter den franske matematikaren Pierre de Fermat, er positive heiltal av forma

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

der n er 0 eller eit positivt heiltal. Dei fyrste åtte fermattala er:

_F_0 = 21 + 1 = 3

_F_1 = 22 + 1 = 5

_F_2 = 24 + 1 = 17

_F_3 = 28 + 1 = 257

_F_4 = 216 + 1 = 65537

_F_5 = 232 + 1 = 4294967297 = 641 × 6700417

_F_6 = 264 + 1 = 18446744073709551617 = 274177 × 67280421310721

_F_7 = 2128 + 1 = 340282366920938463463374607431768211457 = 59649589127497217 × 5704689200685129054721

Om 2_n_ + 1 er eit primtal og n > 0, kan det visast at n må vera ein toerpotens. (Om n = ab der 1 < a, b < n og b er eit oddetal, er 2_n_ + 1 ≡ (2_a_)b + 1 ≡ (−1)b + 1 ≡ 0 (mod 2_a_ + 1).) Alle primtal av forma 2_n_ + 1 er med andre ord eit fermattal og vert kalla fermatprimtal. Dei einaste kjente fermatprimtala er _F_0,...,_F_4. For faktorising av fermattal sjå[1]

Fermattala kan uttrykkast med fyljande rekursjonar

F n = ( F n − 1 − 1 ) 2 + 1 {\displaystyle F_{n}=(F_{n-1}-1)^{2}+1\,} {\displaystyle F_{n}=(F_{n-1}-1)^{2}+1\,}

F n = F n − 1 + 2 2 n − 1 F 0 ⋯ F n − 2 {\displaystyle F_{n}=F_{n-1}+2^{2^{n-1}}F_{0}\cdots F_{n-2}} {\displaystyle 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 {\displaystyle F_{n}=F_{n-1}^{2}-2(F_{n-2}-1)^{2}} {\displaystyle F_{n}=F_{n-1}^{2}-2(F_{n-2}-1)^{2}}

F n = F 0 ⋯ F n − 1 + 2 {\displaystyle F_{n}=F_{0}\cdots F_{n-1}+2} {\displaystyle F_{n}=F_{0}\cdots F_{n-1}+2}

for n ≥ 2. Desse rekursjonane kan alle provast med matematisk induksjon. Frå den siste rekursjonen kan vi utleia Goldbach sitt teorem, som seier at ingen koprime fermattal har ein felles faktor. For å visa dette går vi ut frå at 0 ≤ i < _j_ og at _F_ _i_ og _F_ _j_ har ein felles faktor _a_ > 1. Da dividerer a både produktet

F 0 ⋯ F j − 1 {\displaystyle F_{0}\cdots F_{j-1}} {\displaystyle F_{0}\cdots F_{j-1}}

og F j, slik at a dividerer differensen deira 2. Ettersom a > 1 fører dette til at a = 2. Men dette er ei sjølvmotseiing, ettersom begge fermattala må vera oddetal. Ein logisk konsekvens av dette kan vi konstruere eit prov for at det finst uendeleg mange primtal: for kvar F n, velg ein prime faktor p n. Sekvensen {p n} er da ein uendeleg sekvens av distinkte primtal.

Her er fleire grunnleggande eigenskapar til fermattala:

D ( n , b ) = ⌊ log b ⁡ ( 2 2 n + 1 ) + 1 ⌋ ≈ ⌊ 2 n log b ⁡ 2 + 1 ⌋ {\displaystyle D(n,b)=\lfloor \log _{b}\left(2^{2^{n}}+1\right)+1\rfloor \approx \lfloor 2^{n}\,\log _{b}2+1\rfloor } {\displaystyle D(n,b)=\lfloor \log _{b}\left(2^{2^{n}}+1\right)+1\rfloor \approx \lfloor 2^{n}\,\log _{b}2+1\rfloor } (Sjå golvfunksjonen)

Pierre de Fermat, som var den fyrste som studerte tal av forma F 5 = 2 2 n + 1 {\displaystyle F_{5}=2^{2^{n}}+1} {\displaystyle F_{5}=2^{2^{n}}+1}, la merke til at alle fermattala til og med _F_4 var primtal. Ut frå denne observasjonen trekte han den forhasta konklusjonen at alle fermattala er primtal. Men i 1732 viste Leonhard Euler at

F 5 = 2 2 5 + 1 = 2 32 + 1 = 4294967297 = 641 ⋅ 6700417 {\displaystyle F_{5}=2^{2^{5}}+1=2^{32}+1=4294967297=641\cdot 6700417\;} {\displaystyle F_{5}=2^{2^{5}}+1=2^{32}+1=4294967297=641\cdot 6700417\;}

Euler hadde difor prova at alle faktorane til F n må vera av forma k_2_n+1 + 1. For n = 5 fører dett til at dei einaste moglege faktorane er av forma 64_k_ + 1. Etter dette tok det ikkje så lenge før Euler hadde funne faktoren 641 = 10×64 + 1.

Det er ei vanleg oppfatning at Fermat viste om kva Euler hadde kome fram til, så det kan verka rart at han ikkje nytta seg av dette resultatet for å finna andre faktorar. Ein grunn kan vera at Fermat hadde gjort ein reknefeil, men at han var så sikker på resultatet han hadde kome fram til at han ikkje kontrollerte det godt nok.

Ingen andre prime fermattal av forma F n, med n > 4, er kjente. Følgjande problem er framleis uløyste:

Det følgjande heuristiske argument tyder på at talet på prim fermattal er endeleg. I fylje primtalsteoremet er «sannsynet» for at eit tal n er eit primtal ikkje meir enn A/ln(n), der A er ein konstant. Forventningsverdien for at eit fermattal er eit primtal er difor ikkje høgare enn

A ∑ n = 0 ∞ 1 ln ⁡ F n = A ln ⁡ 2 ∑ n = 0 ∞ 1 log 2 ⁡ ( 2 2 n + 1 ) < A ln ⁡ 2 ∑ n = 0 ∞ 2 − n = 2 A ln ⁡ 2 {\displaystyle A\sum _{n=0}^{\infty }{\frac {1}{\ln F_{n}}}={\frac {A}{\ln 2}}\sum _{n=0}^{\infty }{\frac {1}{\log _{2}(2^{2^{n}}+1)}}<{\frac {A}{\ln 2}}\sum _{n=0}^{\infty }2^{-n}={\frac {2A}{\ln 2}}} {\displaystyle A\sum _{n=0}^{\infty }{\frac {1}{\ln F_{n}}}={\frac {A}{\ln 2}}\sum _{n=0}^{\infty }{\frac {1}{\log _{2}(2^{2^{n}}+1)}}<{\frac {A}{\ln 2}}\sum _{n=0}^{\infty }2^{-n}={\frac {2A}{\ln 2}}}

Det er viktig å ha klårt for seg at det ikkje finst noko eigentleg prov på denne relasjonen. For det fyrste er det lagt til grunn at fermattala oppfører seg tilfeldig, sjølv om det er kjent at faktorane til fermattala har noko spesielle eigenskapar. Sjølv om det er ei vanleg oppfatning at talet på prime fermattal er endeleg, finst det nokre spesialistar som ikkje er samde i dette.[2]

Når dette vert skrive (2004) er det kjent at F n er faktoriserbare for 5 ≤ n ≤ 32, men fullstendige faktoriseringar av F n er berre er kjent for 0 ≤ n ≤ 11. Det største kjente faktoriserbare fermattalet er _F_2478782 og primfaktoren 3×22478785 + 1 vart oppdaga av John Cosgrave og Proth-Gallot gruppa hans, den 10. oktober 2003. Ein enda meir hugkveikjande bruk av det heuristiske argumentet ovanfor, men med same atterhald, er at sannsynet for at det finst nye primfermattal som er større enn _F_32 er i storleiksorden ein til ein milliard.

Det finst mange ekvivalente føresetnaden for at eit fermattal F n skal vera prim:

a ( N − 1 ) / 2 ≡ − 1 mod N {\displaystyle a^{(N-1)/2}\equiv -1\mod N} {\displaystyle a^{(N-1)/2}\equiv -1\mod N}

så er N eit primtal. Om det derimot ikkje finst ein slik kongruens, stemmer ikkje konjeksjonen over og om i tillegg

( a N ) = − 1 {\displaystyle \left({\frac {a}{N}}\right)=-1} {\displaystyle \left({\frac {a}{N}}\right)=-1} (sjå jacobisymbol)

så er N faktoriserbar. Om N = F n > 3, så er Jacobisymbolet over alltid lik −1 for a = 3, og da er denne spesielle forma av teoremet til Proth kjent som testen til Pépin. Sjølv om Pépin sin test og Proth sitt teorem har vorte realiserte i programvare for å prova at mange fermattal er faktoriserbare, så har ingen av testane resultert i ein spesifikk ikkje-trivial faktor. I røynda er ingen spesielle primfaktorar kjente for n = 14, 20, 22 og 24.

F n = ( 2 2 n − 1 ) 2 + 1 2 {\displaystyle F_{n}=\left(2^{2^{n-1}}\right)^{2}+1^{2}} {\displaystyle F_{n}=\left(2^{2^{n-1}}\right)^{2}+1^{2}}

Når F n = x 2 + y 2 {\displaystyle F_{n}=x^{2}+y^{2}} {\displaystyle F_{n}=x^{2}+y^{2}} ikkje er av forma vist over er

gcd ( x + 2 2 n − 1 y , F n ) {\displaystyle \gcd(x+2^{2^{n-1}}y,F_{n})} {\displaystyle \gcd(x+2^{2^{n-1}}y,F_{n})}

ein ekte faktor.

Døme 1: _F_5 = 62264² + 20449², så

gcd ( 62264 + 2 2 4 20449 , F 5 ) = 641 {\displaystyle \gcd(62264\,+\,2^{2^{4}}\,20449,\,F_{5})=641} {\displaystyle \gcd(62264\,+\,2^{2^{4}}\,20449,\,F_{5})=641},

er ein ekte faktor.

Døme 2: _F_6 = 4046803256² + 1438793759², så

gcd ( 4046803256 + 2 2 5 1438793759 , F 6 ) = 274177 {\displaystyle \gcd(4046803256\,+\,2^{2^{5}}\,1438793759,\,F_{6})=274177} {\displaystyle \gcd(4046803256\,+\,2^{2^{5}}\,1438793759,\,F_{6})=274177}

er ein ekte faktor.

På grunn av at dei fermattala som enda ikkje er faktorisert er svært store er det vanskelege å faktorisera dei eller å prova at dei er primtal. Pépin sin test, som kan utførast ved hjelp av moderne datamaskiner, er naudsynt og tilstrekkeleg for å prova at et fermattal er prime. Den elliptiske kurvemetoden er ein snøgg metode for å finna små primdivisorar. I prosjektet GIMPS, til dømes, leitar ein etter primdivisorar til fermattal ved hjelp av den eliptiske kurvemetoden. Prosjektet FermatSearch,[3] som nyttar distribuert arkitektur parallellprosessering, har òg lukkast med å finna nokre faktorar av fermattal. Yves Gallot har realisert ein test basert på Proth sitt teorem, i form av eit Windows-program.[4] I 1878 prova Lucas[5] at alle faktorane til eit fermattal F n {\displaystyle F_{n}} {\displaystyle F_{n}} er av forma 2 n + 2 k + 1 {\displaystyle 2^{n+2}k+1} {\displaystyle 2^{n+2}k+1}, der k er eit positivt heiltal.

Fermat sitt vesle teorem nyttar fermattal for å generera uendeleg mange pseudoprimtal.

Om n er eit positivt heiltal, har vi at

a n − b n = ( a − b ) ∑ k = 0 n − 1 a k b n − 1 − k {\displaystyle a^{n}-b^{n}=(a-b)\sum _{k=0}^{n-1}a^{k}b^{n-1-k}} {\displaystyle a^{n}-b^{n}=(a-b)\sum _{k=0}^{n-1}a^{k}b^{n-1-k}}.

Prov

( a − b ) ∑ k = 0 n − 1 a k b n − 1 − k {\displaystyle (a-b)\sum _{k=0}^{n-1}a^{k}b^{n-1-k}} {\displaystyle (a-b)\sum _{k=0}^{n-1}a^{k}b^{n-1-k}}

= ∑ k = 0 n − 1 a k + 1 b n − 1 − k − ∑ k = 0 n − 1 a k b n − k {\displaystyle =\sum _{k=0}^{n-1}a^{k+1}b^{n-1-k}-\sum _{k=0}^{n-1}a^{k}b^{n-k}} {\displaystyle =\sum _{k=0}^{n-1}a^{k+1}b^{n-1-k}-\sum _{k=0}^{n-1}a^{k}b^{n-k}}

= a n + ∑ k = 1 n − 1 a k b n − k − ∑ k = 1 n − 1 a k b n − k − b n {\displaystyle =a^{n}+\sum _{k=1}^{n-1}a^{k}b^{n-k}-\sum _{k=1}^{n-1}a^{k}b^{n-k}-b^{n}} {\displaystyle =a^{n}+\sum _{k=1}^{n-1}a^{k}b^{n-k}-\sum _{k=1}^{n-1}a^{k}b^{n-k}-b^{n}}

= a n − b n {\displaystyle =a^{n}-b^{n}} {\displaystyle =a^{n}-b^{n}}.

Om 2 n + 1 {\displaystyle 2^{n}+1} {\displaystyle 2^{n}+1} er eit primtal, så er n {\displaystyle n} {\displaystyle n} ein toerpotens.

Prov:

Ut frå at

a n − b n = ( a − b ) ∑ k = 0 n − 1 a k b n − 1 − k {\displaystyle a^{n}-b^{n}=(a-b)\sum _{k=0}^{n-1}a^{k}b^{n-1-k}} {\displaystyle a^{n}-b^{n}=(a-b)\sum _{k=0}^{n-1}a^{k}b^{n-1-k}}.

om n {\displaystyle n} {\displaystyle n} er ein 2'er-potens, eller n = a b {\displaystyle n=ab} {\displaystyle n=ab}, der 1 < a , b < n {\displaystyle 1<a,b<n} {\displaystyle 1<a,b<n} og b {\displaystyle b} {\displaystyle b} er eit oddetal, har vi at

2 a b + 1 = ( 2 a + 1 ) ∑ k = 0 b − 1 ( 2 a ) k ( − 1 ) b − 1 − k {\displaystyle 2^{ab}+1=(2^{a}+1)\sum _{k=0}^{b-1}(2^{a})^{k}(-1)^{b-1-k}} {\displaystyle 2^{ab}+1=(2^{a}+1)\sum _{k=0}^{b-1}(2^{a})^{k}(-1)^{b-1-k}}.

Difor ville 2 a + 1 {\displaystyle 2^{a}+1} {\displaystyle 2^{a}+1} dividera 2 n + 1 {\displaystyle 2^{n}+1} {\displaystyle 2^{n}+1}, eller så er ikkje 2 n + 1 {\displaystyle 2^{n}+1} {\displaystyle 2^{n}+1} eit primtal.

Eit n_-sidig regulært polygon kan konstruerast med passar og linjeal om og berre om n er både ein toerpotens og eit produkt av ein toerpotens og distinkte primfermattal. Med andre ord, berre om n er av forma n = 2_k _p_1_p_2...p s, der k er eit ikkje-negativt heiltal og p i er distinkte primfermattal. Sjå konstruerbare polygon.

Eit positivt heiltal n er av forma over om og berre om φ(n) er ein toerpotens, der φ(n) er Euler sin totientfunktsjon.

  1. ↑ Keller, W., Prime Factors k ⋅ 2 n + 1 {\displaystyle k\cdot 2_{n}+1} {\displaystyle k\cdot 2{n}+1} of Fermat Numbers F m {\displaystyle F_{m}} {\displaystyle F_{m}} Arkivert 2016-02-10 ved Wayback Machine. (Lenka 24/8 2007)
  2. ↑ Arkivert 2006-10-02 ved Wayback Machine.
  3. ↑ http://www.science-at-home.de/fermat.php
  4. ↑ exe-fila (Proth.exe) kan lastast ned frå The Prime Pages.
  5. ↑ Křížek, Michal, Luca, Florian, Somer, Lawrence, 17 Lectures on Fermat Numbers: From Number Theory to Geometry, Springer, CMS Books 9, ISBN 0-387-95332-9 (Denne boka har ei lang liste med referansar.)