Fermattal

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$ ,

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

F₀ = 2¹ + 1 = 3

F₁ = 2² + 1 = 5

F₂ = 2⁴ + 1 = 17

F₃ = 2⁸ + 1 = 257

F₄ = 2¹⁶ + 1 = 65537

F₅ = 2³² + 1 = 4294967297 = 641 × 6700417

F₆ = 2⁶⁴ + 1 = 18446744073709551617 = 274177 × 67280421310721

F₇ = 2¹²⁸ + 1 = 340282366920938463463374607431768211457 = 59649589127497217 × 5704689200685129054721

Om 2ⁿ + 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ⁿ + 1 ≡ (2^a)^b + 1 ≡ (−1)^b + 1 ≡ 0 (mod 2^a + 1).) Alle primtal av forma 2ⁿ + 1 er med andre ord eit Fermattal og vert kalla Fermatprimtal. Dei einaste kjente fermatprimtala er F₀,...,F₄. For faktorising av fermattal sjå Prime Factors of Fermat Numbers

Innhaldsliste

1 Grunnleggande eigenskapar
2 Prim fermattal
3 Faktorisering av Fermattal
4 Fermat sitt vesle theorem og pseudoprimtal
5 Andre teorem om prim fermattal
6 Relasjonar til konstruktibele polygon
7 Praktisk bruk av fermattal
8 Referanse
9 Sjå òg
10 Eksterne lenkjer
11 Kjelde

[endre] Grunnleggande eigenskapar

Fermattala kan uttrykkast med fyljande rekursjonar

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

$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$

for n ≥ 2. Desse rekursjonane kan alle provast med matematisk induksjon. Frå den siste rekursjonan 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} \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:

Om n ≥ 2, er F_n ≡ 17 eller 41 (mod 72). (Sjå modulær aritmetikk)
Om n ≥ 2, er F_n ≡ 17, 37, 57, eller 97 (mod 100).
Talet på siffer D(n,b) når F_n vert uttrykt med base b er

$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)

Med unnatak av F₁ = 2 + 3 kan ingen fermattal uttrykkast som ein sum av to primtal.
Ingen prime fermattal kan uttrykkast som differansen mellom to p-potensar, der p er eit ulike primtal.

[endre] Prim fermattal

Pierre de Fermat, som var den fyrste som studerte tal av forma $F_{5} = 2^{2^n} + 1$ , la merke til at alle Fermattala til og med F₄ 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 \cdot 6700417 \;$

Euler hadde difor prova at alle faktorane til F_n må vera av forma k2ⁿ⁺¹ + 1. For n = 5 fører dett til at dei einaste mulige faktorane er av forma 64k + 1. Etter dette tok det ikkje så lenge før Euler hadde funne factoren 641 = 10×64 + 1.

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

Ingnen andre prime fermattal av forma F_n, med n > 4, er kjente. Fyljande problem er framleis uløyste:

Er F_n faktoriserbar for alle n > 4?
Er det uendelig mange prime fermattal?
Er det uendelig mange faktoriserbare fermattal?

Det følgjande heuristiske argument tyder på at talet på prim fermattal er endeleg. I fylje primtalsteoremet er "sannsynligheita" 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 \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 kjendt at faktorane til farmattala har noko spesielle eigenskapar. Sjølv om det er ei vanleg oppfattning at talet på prime fermattal er endeleg, finst det nokre spesialistar som ikkje er samde i dette [1]

Når dette vert skrive (2004) er det kjendt at F_n er faktoriserbare for 5 ≤ n ≤ 32, men fullstendige faktoriseringar av F_n er berre er kjendt for 0 ≤ n ≤ 11. Det største kjendte faktoriserbare fermattalet er F_2478782 og primefaktoren 3×2^2478785 + 1 vart oppdaga av John Cosgrave og Proth-Gallot gruppa hans, den 10 oktober 2003. Ein enda meir hugkveikjande bruk av det hauristiske argumentet ovanfor, men med same atterhald, er at sannsynligheita for at det finst nye prim fermattal som er større enn F₃₂ er i storleiksorden ein til ein milliard.

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

Teoremet til Proth -- (1878) Lat N = k2^m + 1, med k eit oddetal < 2^m. Om det finst eit heiltal a slik at

$a^{(N-1)/2} \equiv -1 \mod N$

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

$\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 kjendt som testen til Pépin. Sjølv om Pépin sin test og Proth sitt theorem har vorte realiserte i mjukvare for å prova at mange fermattal er faktoriserbare, så har ingen av testane resultert i ein spesifikk ikkjetrivial faktor. I røynda er ingen spesielle primefaktorar kjente for n = 14, 20, 22, og 24.

Lat n ≥ 3 vera eit positivt ulike heiltal. Da er n eit prime fermattal om og berre om alle a er relativt prime med n, a er ei primitiv rot mod n om og berre om a er ei kvadratisk ikkjeresidu mod n.
Fermattalet F_n > 3 er prime om og berre om det kan skrivast eintydig som ein sum av to kvadrat som ikkje er null:

$F_{n}=\left(2^{2^{n-1}}\right)^{2}+1^{2}$

Når

F n = x 2 + y 2

ikkje er av forma vist over er

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

ein ekte faktor.

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

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

er ein ekte faktor.

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

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

er ein ekte faktor.

[endre] Faktorisering av Fermattal

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, 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; exe-fila (Proth.exe) kan lastast ned frå The Prime Pages. I 1878 prova Lucas at alle faktorane til eit farmattal $F n$ er av forma $2 n + 2 k + 1$ , der k er eit positivt heiltal.

[endre] Fermat sitt vesle theorem og pseudoprimtal

Fermat sitt vesle theorem nyttar fernattal for å generera uendeleg mange pseudoprimtal.

[endre] Andre teorem om prim fermattal

Om n er eit positivt heiltal, har vi at

$a^n-b^n=(a-b)\sum_{k=0}^{n-1} a^kb^{n-1-k}$ .

Prov

$(a-b)\sum_{k=0}^{n-1}a^kb^{n-1-k}$

$=\sum_{k=0}^{n-1}a^{k+1}b^{n-1-k}-\sum_{k=0}^{n-1}a^kb^{n-k}$

$=a^n+\sum_{k=1}^{n-1}a^kb^{n-k}-\sum_{k=1}^{n-1}a^kb^{n-k}-b^n$

= a n - b n

Om $2 n + 1$ er eit primtal, så er $n$ ein 2'er-potens.

Prov:

Ut frå at

$a^n-b^n=(a-b)\sum_{k=0}^{n-1} a^kb^{n-1-k}$ .

om $n$ er ein 2'er-potens, eller $n = a b$ , der $1 < a, b < n$ og $b$ er eit oddetal, har vi at

$2^{ab}+1=(2^a+1)\sum_{k=0}^{b-1} (2^a)^k(-1)^{b-1-k}$ .

Difor ville $2 a + 1$ dividera $2 n + 1$ , eller så er ikkje $2 n + 1$ eit primtal.

[endre] Relasjonar til konstruktibele polygon

Eit n-sidig regulært polygon kan konstruerast med passar og linjeal om og berre om n er både ein 2'er-potens og eit produkt av ein 2'er-potens og distinkte prime fermattal. Med andre ord, berre om n er av forma n = 2^kp₁p₂...p_s, der k er eit ikkjenegativt heiltal og p_i er distinkte prim fermattal. Sjå konstruerbare polygon.

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

[endre] Praktisk bruk av fermattal

Som modulus i talteoretiske transformer
I tilfelldig tal-genratorar
Innan kryptografi

[endre] Referanse

17 Lectures on Fermat Numbers: From Number Theory to Geometry, Michal Křížek, Florian Luca, Lawrence Somer, Springer, CMS Books 9, ISBN 0-387-95332-9 (Denne boka har ei lang liste med referansar.)

[endre] Sjå òg

Mersennetal
Lucas sitt teorem
Proth sitt teorem
Pseudoprimtal
Primtest
Konstruerbare tal
Sierpinskital

[endre] Eksterne lenkjer

[endre] Kjelde

Engelsk Wikipedia

Henta frå «http://nn.wikipedia.org../../../f/e/r/Fermattal.html»

Kategoriar: Matematikk | Tal | Fermattal | Talteori | Euclidisk plangeometri

We provide Linux to the World