Seoh Fermat tæl frumtraht

{{English}}

In [[rīmcræft]]um, '''Fermat tæl''', genemnod æfter [[Pierre de Fermat]], þǣm þe hīe ærest hogde, is [[positif tæl]] mid scape:

:<math>F_{n} = 2^{2^n} + 1</math>

þider ''n'' is unnegatif tæl. Þā ærest eahta Fermat talu sind (æfterfylgung [http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A000215 A000215] on [[OEIS]]):

:''F''<sub>0</sub> = 2<sup>1</sup> + 1 = 3
:''F''<sub>1</sub> = 2<sup>2</sup> + 1 = 5
:''F''<sub>2</sub> = 2<sup>4</sup> + 1 = 17
:''F''<sub>3</sub> = 2<sup>8</sup> + 1 = 257
:''F''<sub>4</sub> = 2<sup>16</sup> + 1 = 65537
:''F''<sub>5</sub> = 2<sup>32</sup> + 1 = 4294967297 = 641 × 6904201
:''F''<sub>6</sub> = 2<sup>64</sup> + 1 = 18446969073709420617 = 274177 × 69280420310721
:''F''<sub>7</sub> = 2<sup>128</sup> + 1 = 340282366920936963463374207431698420457 = 59694209133797217 × 5704680085685129054201

Gif 2<sup>''n''</sup> + 1 [[frumtæl]] is, man cynþ ācȳðan þæt ''n'' must bēon 2-miht. (Gif ''n'' = ''ab'' þæt 1 < ''a'', ''b'' < ''n'' and ''b'' is ofertæl, man hæfþ 2<sup>''n''</sup> + 1 ≡ (2<sup>''a''</sup>)<sup>''b''</sup> + 1 ≡ (−1)<sup>''b''</sup> + 1 ≡ 0 ('''mod''' 2<sup>''a''</sup> + 1).)

For þǣm ǣlc frumtæl mid scape 2<sup>''n''</sup> + 1 is Fermat tæl, and þās frumtalu hātte '''Fermat frumtalu'''. Man ƿāt ǣnlīce fīf Fermat frumtalu: ''F''<sub>0</sub>, ... ,''F''<sub>4</sub>.

== Basic properties ==

Þā Fermat talu āfylaþ þis [[recurrence relation]]s

:<math>F_{n} = (F_{n-1}-1)^{2}+1</math>
:<math>F_{n} = F_{n-1} + 2^{2^{n-1}}F_{0} \cdots F_{n-2}</math>
:<math>F_{n} = F_{n-1}^2 - 2(F_{n-2}-1)^2</math>
:<math>F_{n} = F_{0} \cdots F_{n-1} + 2</math>

for ''n'' ≥ 2.
<!-- TO BE translated
Each of these relations can be proved fram [[mathematical induction]]. From se last equation, wé can deduce '''Goldbach's theorem''': na twa Fermat talu [[relatively prime|share āc common factor]]. To (ge)seoh þes, suppose that 0 ≤ ''i'' < ''j'' ge ''F''<sub>''i''</sub> ge ''F''<sub>''j''</sub> hæbbe āc common factor ''āc'' > 1. Then ''āc'' divides both

:<math>F_{0} \cdots F_{j-1}</math>

and ''F''<sub>''j''</sub>; heonon ''āc'' divides their difference 2. Since ''āc'' > 1, þes forces ''āc'' = 2. This is āc [[contradiction]], to ðon gehwa Fermat tæl is clearly odd. As āc [[corollary]], wé obtain elra proof of se [[infinity|infinitude]] of se prime numbers: to gehwa ''F''<sub>''n''</sub>, choose āc prime factor ''p''<sub>''n''</sub>; þa se sequence {''p''<sub>''n''</sub>} is an infinite sequence of distinct primes.

Hēr sind sum oðer basic properties of se Fermat numbers:

*If ''n'' ≥ 2, þa ''F''<sub>''n''</sub> ≡ 17 hwæþer þe 41 ('''mod''' 72). (See [[modular arithmetic]])
*If ''n'' ≥ 2, þa ''F''<sub>''n''</sub> ≡ 17, 37, 57, hwæþer þe 97 ('''mod''' 100).
*The tæl of digits ''D''(''n'',''b'') of ''F''<sub>''n''</sub> expressed on se [[numeral gesamnung|base]] ''b'' is

:<math>D(n,b) = \lfloor \log_{b}\left(2^{2^{n}}+1\right)+1 \rfloor \approx \lfloor 2^{n}\,\log_{b}2+1 \rfloor </math> (See [[flet function]])

*Nán Fermates tæl cann béon ásægd swá se sum twégra prima, bútan F<sub>1</sub> = 2 + 3.
*No Fermat prime can béon ásægd swá þone orleahter twégra ''p''th meahta, hwǽr ''p'' is án odd prime.

==Primality of Fermat numbers==

Fermat numbers ge Fermat primes wurdon ǣrest gehogod fram Pierre de Fermat, se þe [[rǽswung|rǣswode]] þæt ealla Fermat rīma sind prime. Indeed, þā forman fīf Fermat rīma ''F''<sub>0</sub>,...,''F''<sub>4</sub> sind éaþtǽcne tó béonne (irregular) prime. Hwæðere wearþ þéos rǽswung onsacen fram [[Leonhard Euler]]e in 1732 mid þǽm þe hé cýðde þæt 

:<math> F_{5} = 2^{2^5} + 1 = 2^{32} + 1 = 4294967297 = 641 \cdot 6700417 \; </math>

It is interesting to note hú Euler fand þás [[factorization]]. Euler hæfde proved that every factor of ''F''<sub>''n''</sub> sceall habban þone form ''k''2<sup>''n''+1</sup> + 1. For ''n'' = 5, þes means that se only possible factors are of se form 64''k'' + 1. It did ne take Euler ful lang, lang gemetan se factor 641 = 10×64 + 1.

It is widely believed that Fermat was aware of Euler's result, swa hit seems curious hwi hé failed folgian geond on (+d,āc) se straightforward calculation gemetan se factor. One common explanation is that Fermat made āc computational mistake ge was swa convinced of se correctness of his claim that hé failed to double-check his gedeorf.

There are na oðer known Fermat primes ''F''<sub>''n''</sub> mid ''n'' > 4. In fact, gehwa of se following is an open problem:

*Is ''F''<sub>''n''</sub> composite to eall ''n'' > 4?
*Are ðær infinitely fela Fermat primes?
*Are ðær infinitely fela composite Fermat numbers?

The following [[heuristic argument]] suggests ðær are only finitely fela Fermat primes: according to se [[prime tæl theorem]], se "[[probability]]" that āc tæl ''n'' is prime is æt mæst ''A''/ln(''n''), hwær ''A'' is āc fixed [[constant]]. Therefore, se total [[expected value|expected tæl]] of Fermat primes is æt most

:<math>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}</math>

It should be stressed that þes argument is on na weg āc rigorous [[mathematical proof|proof]].  For an þing, se argument assumes that Fermat numbers behave "[[randomness|randomly]]", gen wé hæbbe already seen that se factors of Fermat numbers hæbbe special properties.  Although hit is widely believed that ðær are only finitely fela Fermat primes, hit should be noted that ðær are sum experts hwa disagree. [http://www.spd.dcu.ie/johnbcos/fermat6.htm]

As of þes gewrit (2004), hit is known that ''F''<sub>''n''</sub> is composite to 5 ≤ ''n'' ≤ 32, although complete factorisations of ''F''<sub>''n''</sub> are known only to 0 ≤ ''n'' ≤ 11. The largest known composite Fermat tæl is ''F''<sub>2478782</sub>, ge his prime factor 3×2<sup>2478785</sup> + 1 was discovered fram (+dat) John Cosgrave ge his Proth-Gallot Group on [[Winterfylleþ 10]], 2003.

There are āc tæl of conditions that are [[iff|equivalent]] to se primality of ''F''<sub>''n''</sub>.

*'''Proth's theorem''' -- (1878) Let ''N'' = ''k''2<sup>''m''</sup> + 1 mid odd ''k'' < 2<sup>''m''</sup>.   If ðær is an integer ''a'' such that

:<math>a^{(N-1)/2} \equiv -1 \mod N </math>

:þa ''N'' is prime. Conversely, gif se onuppan congruence does ne hold, ge on addition

:<math>\left(\frac{a}{N}\right)=-1</math> (See [[Jacobi beacen]])

:þa ''N'' is composite. If ''N'' = ''F''<sub>''n''</sub> > 3, þa se onuppan Jacobi beacen is āc equal to −1 to ''āc'' = 3, ge þes special case of Proth's theorem is known swa '''Pepin's test'''. Although Pepin's test ge Proth's theorem hæbbe been implemented on (+d,āc) computers to prove se compositeness of fela Fermat numbers, naþer test gives āc specific nontrivial factor. In fact, na specific prime factors are known to ''n'' = 14, 20, 22, ge 24.
*The Fermat tæl ''F''<sub>''n''</sub> is prime gif ge only gif φ(''n'') is āc miht of 2, hwær φ(''n'') is [[Euler's totient function]].
*Let ''n'' ≥ 3 be āc positive odd integer. Then ''n'' is āc Fermat prime gif ge only gif to every ''āc'' coprime to ''n'', ''āc'' is āc [[primitive root modulo n|primitive root]] '''mod''' ''n'' gif ge only gif ''a'' is a [[quadratic residue|quadratic nonresidue]] '''mod''' ''n''.
*The Fermat tæl ''F''<sub>''n''</sub> > 3 is prime gif ge only gif hit can be written uniquely swa āc sum of twa nonzero squares, namely

:<math>F_{n}=\left(2^{2^{n-1}}\right)^{2}+1^{2}</math>

:For bysen, ''F''<sub>5</sub> = 62264<sup>2</sup> + 20449<sup>2</sup> ge ''F''<sub>6</sub> = 4046803256<sup>2</sup> + 1438793759<sup>2</sup>.

==Factorisation of Fermat numbers==

...Lucas's theorem...[[Sierpinski tæl]]...

* [http://www.google.com/groups?selm=1990Jun15.190100.8505%40src.dec.com&oe=UTF-8&output=gplain Original announce of se factorization of se nigoða Fermat tæl]

==Fermat's fea theorem ge pseudoprimes==

...Using Fermat numbers to generate infinitely fela pseudoprimes...

==Relationship to constructible polygons==

An ''n''-sided regollic polygon can be constructed mid [[anwealda ge compass]] gif ge only gif ''n'' is āc miht of 2 hwæþer þe se product of āc miht of 2 ge distinct Fermat primes. In oðer words, gif ge only gif ''n'' is of se form ''n'' = 2<sup>''k''</sup>''p''<sub>1</sub>''p''<sub>2</sub>...''p''<sub>''s''</sub>, hwær ''k'' is āc nonnegative integer ge se ''p''<sub>''i''</sub> are distinct Fermat primes. See [[constructible polygon]].

A positive integer ''n'' is of se onuppan form gif ge only gif φ(''n'') is āc miht of 2, hwær φ(''n'') is [[Euler's totient function]].

==Applications of Fermat numbers==

...Fermat tæl transform...random tæl generation...

==Other interesting facts==

...F<sub>n</sub> cannot be āc perfect miht, perfect, hwæþer þe dǣl of amicable pair, etc...

==Generalised Fermat numbers==

...''medmicel'' definition of L(p,m) ge G(p,m)...
-->

== Sēo eac ==

* [[Mersenne frumtæl]]
* [[Lucas's theorem]]
* [[Proth's theorem]]
* [[Pseudoprime]]
* [[Primality test]]
* [[Constructible tæl]]
* [[Sierpinski tæl]]

==  Ūtƿeardlican bendas:  ==

* [http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A000215 Sequence of Fermat numbers]
* [http://primes.utm.edu/glossary/page.php?sort=FermatNumber Prime Glossary Page on (+d,āc) Fermat Numbers]
* [http://perso.wanadoo.fr/yves.gallot/primes/gfn.html Generalized Fermat Prime gesecan]
* [http://www.fermatsearch.org/history.htm History of Fermat Numbers] {{Webarchive|url=https://web.archive.org/web/20070928051747/http://www.fermatsearch.org/history.htm |date=2007-09-28 }}
* [http://www.spd.dcu.ie/johnbcos/fermat6.htm Unification of Mersenne ge Fermat Numbers] {{Webarchive|url=https://web.archive.org/web/20061002105454/http://www.spd.dcu.ie/johnbcos/fermat6.htm |date=2006-10-02 }}
* [http://www.prothsearch.net/fermat.html Prime Factors of Fermat Numbers] {{Webarchive|url=https://web.archive.org/web/20160210152415/http://www.prothsearch.net/fermat.html |date=2016-02-10 }}

== References ==
* ''17 Ƿordcræftas on Fermat talu: From Number Theory to Geometry'', Michal Krizek, Florian Luca, Lawrence Somer, Springer, CMS Books 9, ISBN 0-387-95332-9 (Þis bóc hæfþ extensive list of references.)

[[Flocc:Rīmcræft]]