Nombro de Fermat

En matematiko **nombro de Fermat** estas pozitiva entjero de formo

:F_{n} = 2^{2^{ \overset{n} {}}} + 1

kie *n* estas nenegativa entjero. La nombroj estas nomitaj pro Pierre de Fermat, kiu verkis pri la primeco de tiaj nombroj.
La unuaj 9 nombroj de Fermat estas:

Kiel en 2007, nur la unuaj 12 nombroj de Fermat estas plene faktoritaj. 

Se *2n+1* estas primo, kaj *n>0*, *n* devas esti nenegativa entjera potenco de 2. (Se *n=ab* kie *1≤a, b≤n* kaj *b* estas nepara, tiam *2n + 1 ≡ (2a)b + 1 ≡ (−1)b + 1 ≡ 0 (**mod** 2a + 1)*). En aliaj vortoj, ĉiu primo de la formo *2n + 1* estas nombro de Fermat, kaj ĉi tiaj primoj estas nomataj kiel **primoj de Fermat**. La nuraj sciataj primoj de Fermat estas *F*0 ... *F*4.

## Bazaj propraĵoj 
La nombroj de Fermat kontentigas jenajn rekursiecajn rilatojn

: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

por *n≥2*. Ĉiu el ĉi tiuj rilatoj povas esti pruvita per matematika indukto. El la lasta ekvacio sekvas la **teoremo de Goldbach**: du nombroj de Fermat estas reciproke primaj (ne havas komunan faktoron). Por vidi ĉi tion, supozu ke *0≤ii* kaj *Fj* havas komunan faktoron *a>1*. Tiam *a* dividas na ambaŭ

:F_{0} \cdots F_{j-1}

kaj *Fj*; de ĉi tie *a* dividas ilian diferencon 2. Pro tio ke *a>1*, *a=2*. Ĉi tiu estas kontraŭdiro, ĉar ĉiu nombro de Fermat estas klare nepara. Tiel oni ricevas pruvon de la senfineco de la primoj: por ĉiu *Fn, elektu priman faktoron *pn*; tiam la vico *{pn}* estas malfinia vico de diversaj primoj.

Pluaj propraĵoj:

* La kvanto de ciferoj *D(n,b)* de *Fn* esprimita en la bazo *b* estas

:D(n,b) = \lfloor \log_{b}\left(2^{2^{\overset{n}{}}}+1\right)+1 \rfloor \approx \lfloor 2^{n}\,\log_{b}2+1 \rfloor 

* Nombro de Fermat ne povas esti esprimita kiel sumo de du primoj, escepte de *F1 = 2 + 3*.
* Primo de Fermat ne povas esti esprimita kiel diferenco de du *p*-aj potencoj, kie *p* estas nepara primo.

* Sumo de la inversoj de ĉiuj nombroj de Fermat estas neracionala nombro. (Solomon W. Golomb, 1963)

## Primeco de nombroj de Fermat 
Nombroj de Fermat kaj primoj de Fermat estis unue studitaj de Pierre de Fermat, kiu konjektis ke ĉiuj nombroj de Fermat estas primoj. Ja, la unuaj kvin nombroj de Fermat *F0,...,F4* estas primoj. Tamen, ĉi tiu konjekto estis nuligita de Leonhard Euler kiu en 1732 montris ke

: F_{5} = 2^{2^5} + 1 = 2^{32} + 1 = 4294967297 = 641 \cdot 6700417. \; 

Eŭlero pruvis ke ĉiu eventuala faktoro de *Fn* devas havi formon *k2n+1+1*. Por *n=5*, ĉi tio signifas ke la nuraj eblaj faktoroj estas de formo *64k+1*. Eŭlero trovis la faktoron 641 = 10×64 + 1.

Estas larĝe kredite ke Fermat sciis de rezulton de Eŭlero, tiel aspektas kurioze kial li ne sekvis tra la simpla kalkulo por trovi la faktoron. Unu komuna ekspliko estas ke Fermat faris komputan eraron kaj estis tiel konvinkita en praveco de sia pretendo.

Ne estas aliaj sciataj primoj de Fermat *Fn* kun *n* > 4. Tamen, tre malmulto estas sciata pri nombroj de Fermat kun granda *n*.  Fakte, ĉiu el jena listo estas malfermita problemo:

* Ĉu estas *Fn* komponita por ĉiuj *n>4*?
* Ĉu estas malfinie multaj primoj de Fermat? (Ferdinand Eisenstein 1844)
* Ĉu estas malfinie multaj komponitaj nombroj de Fermat?

Jena heŭristika argumento sugestas ke estas nur finie multaj primoj de Fermat: laŭ la prima teoremo, la "probablo" ke nombro *n* estas primo estas maksimume *A/ln(n)*, kie *A* estas fiksita konstanto. Pro tio, la tuteca atendata valoro de kvanto de primoj de Fermat estas maksimume

:: 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)} 

Tamen ĉi tiu argumento estas neniel rigora pruvo. La argumento alprenas ke nombroj de Fermat kondutas *hazarde*, sed oni jam vidis ke la faktoroj de nombroj de Fermat havas specialajn propraĵojn. Kvankam ĝi estas larĝe kredite ke estas nur finie multaj primoj de Fermat, estas iuj kompetentuloj kiuj malkonsentas. 

Kiel en 2006, estas sciate ke *Fn* estas komponita por *5≤n≤32*, kvankam plenaj faktoradoj de *Fn estas sciata nur por *0≤n≤11*, kaj ne estas sciataj faktoroj por *n* en {14, 20, 22, 24}. La plej granda konata komponita nombro de Fermat estas *F2478782*, kaj ĝia prima faktoro 3×22478785 + 1 estis esplorita de John B. Cosgrave kaj lia Proth-Gallot Grupo en la 10-a de oktobro 2003.
Eĉ pli spekulativa apliko de la heŭristika argumento pli supre donita ekzistas - ke la *probablo* ke estas iu nova primo de Fermat preter *F*32 estas de ordo de unu al 109.

Estas iuj kondiĉoj kiuj estas ekvivalentaj al primeco de *Fn*.

* **Teoremo de Proth** - (1878) Estu *N=k2m+1* kun nepara *km*. Se estas entjero *a* tia ke

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

tiam *N* estas primo. Male, se la pli supra kongrueco ne veras, kaj aldone

: \left(\frac{a}{N}\right)=-1 (vidu en jakobia simbolo)

tiam *N* estas komponita. Se *N=Fn>3*, tiam la pli supra Jakobia simbolo estas ĉiam egala al −1 por *a =3*, kaj ĉi tiu speciala okazo de la teoremo estas konata kiel testo de Pépin. Kvankam la testo de Pépin kaj la teoremo de Proth estas realigitaj sur komputiloj por pruvi la komponitecon de multaj nombroj de Fermat, neniu testo donas specifan netrivialan faktoron. Fakte, ne estas konataj specifaj primaj faktoroj por *n* = 14, 20, 22 kaj 24.
* Estu *n≥3* pozitiva nepara entjero. Tiam *n* estas primo de Fermat se kaj nur se por ĉiu *a* reciproke prima kun *n*, *a* estas primitiva radiko **mod** *n* se kaj nur se *a* estas kvadrata nerestaĵo **mod** *n*.
* La nombro de Fermat *F**n* > 3 estas primo se kaj nur se ĝi povas esti skribita unike kiel sumo de du nenulaj kvadratoj:

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

:Kiam F_{n} = x^2 + y^2 ne estas de formo montrita pli supre, pozitiva faktoro estas:

:: {pgkd}(x + 2^{2^{n-1}} y, F_{n})

:Ekzemplo 1: *F*5 = 622642 + 204492, tiel faktoro estas {pgkd}(62264\, +\, 2^{2^4}\, 20449,\, F_{5}) = 641.

:Ekzemplo 2: *F*6 = 40468032562 + 14387937592, tiel faktoro estas {pgkd}(4046803256\, +\, 2^{2^5}\, 1438793759,\, F_{6}) = 274177.

## Faktorado de nombroj de Fermat 
Pro la amplekso de nombroj de Fermat, estas malfacile faktori aŭ pruvi primecon de ili. Testo de Pépin estas necesa kaj sufiĉa testo por primeco de nombroj de Fermat, kiu povas esti realigita per modernaj komputiloj. La elipsa kurba maniero estas rapida maniero por trovi malgrandajn primajn divizoroj de nombroj. Distribuita komputada projekto *Fermatsearch* sukcese trovitas iujn faktorojn de nombroj de Fermat. *proth.exe* de Yves Gallot estas uzita por trovi faktorojn de grandaj nombroj de Fermat. Edouard Lucas pruvis en 1878 ke ĉiu faktoro de nombro de Fermat *Fn estas de formo *2n+2k+1*, kie *k* estas pozitiva entjero.

## Aliaj teoremoj pri nombroj de Fermat 
*'Lemo: Se *n* estas pozitiva entjero, '*

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

*pruvo:*

:(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

*'Teoremo: Se *2n+1* estas primo, tiam *n* estas nulo aŭ potenco  de 2.'*

*pruvo:*

Por *n=0*, 20+1 estas primo 2. (Tial iuj opinias, ke ankaŭ la nombro 2 estas primo de Fermat.)

Se *n* estas pozitiva entjero sed ne povo de 2, tiam *n=rs* kie
*1≤r(a-b) \mid (a^m-b^m)

kie  \mid  estas "pare dividas". Anstataŭigante *a=2r*, *b=-1* kaj *m=s*,

: (2^r+1) \mid (2^{rs}+1), 
kaj tial
: (2^r+1) \mid (2^n+1). 

Ĉar *2r+1>1*, *2n+1* estas ne primo kiam *n* estas pozitiva entjero kiu ne estas povo de 2.

En la aliaj vortoj, se *n* havas neparan divizoron *m* do laŭ teoremo de Bézout (1730-1783)
:\frac{2^n+1}{2^m+1}=1-2^m+2^{2m}-\cdots+2^{n-m}.

**Teoremo de Édouard Lucas**: Ĉiu prima dividanto *p* de *Fn* =  2^{2^{\overset{n}{}}}+1 estas de formo *k2n+2+1* por *n* pli granda ol 1.

## Interrilato al konstrueblaj plurlateroj 
*n*-flankita regula plurlatero estas konstruebla per cirkelo kaj liniilo se kaj nur se *n* estas povo de 2 aŭ produto de povo de 2 kaj diversaj primoj de Fermat. En aliaj vortoj, se kaj nur se *n* estas de formo *n= 2kp1p2...ps*, kie *k* estas nenegativa entjero kaj la *pi* estas diversaj primoj de Fermat.

Pozitiva entjero *n* estas de la formo pli supre donita se kaj nur se *φ(n)* estas povo de 2, kie *φ(n)* estas eŭlera φ funkcio.

## Aliaj faktoj 
Nombro de Fermat ne povas esti perfekta nombro aŭ parto de paro da amikaj nombroj.(Luca 2000)

La serio de inversoj de ĉiuj primaj divizoroj de nombroj de Fermat estas konverĝa. (Krizek, Luca, Somer 2002)

Se *nn+1* estas primo, do ekzistas entjero *m* tia ke *n=22m*. La ekvacio
*nn+1=F(2m+m)*
veras tiam. 

Estu *P(Fn)* la plej granda prima faktoro de nombro de Fermat *Fn*. Tiam,
:P(F_n )\ge 2^{m+2}(4m+9)+1.
(Grytczuk, Luca kaj Wojtowicz. 2001)

## Ĝeneraligita nombroj de Fermat 
Nombroj de formo a^{2^{ \overset{n} {}}} + b^{2^{ \overset{n} {}}}, kie *a>1* estas nomataj kiel **ĝeneraligitaj nombroj de Fermat**. Analoge al ordinaraj nombroj de Fermat, estas komune skribi ĝeneraligitajn nombrojn de Fermat de formo a^{2^{ \overset{n} {}}} + 1 kiel *Fn(a)*. En ĉi tiu skribmaniero, ekzemple, la nombro 100000001 povas esti skribita kiel *F3(10)*

Nepara primo *p* estas ĝeneraligita nombro de Fermat se kaj nur se *p* estas kongrua al 1 (mod 4).

### Ĝeneraligitaj primoj de Fermat 
Pro la komforteco de pruvado de ilia primeco, ĝeneraligitaj primoj de Fermat estas aktualaj en esploroj en nombroteorio. Multaj de la plej granda sciata primoj hodiaŭ estas ĝeneraligitaj primoj de Fermat.

Ĝeneraligita nombro de Fermat povas esti primo nur por para *a*, ĉar se *a* estas nepara tiam ĉiu ĝeneraligita nombro de Fermat estas esti dividebla per 2. Analoge la heŭristika argumento por la finia kvanto de primoj inter la bazo-2 nombroj de Fermat, estas atendite ke estas esti nur finie multaj ĝeneraligitaj primoj de Fermat por ĉiu para bazo. La plej malgranda primo *Fn(a)* kun *n>4* estas *F5(30)=3032+1*.

Pli ellabori teorio povas esti uzita por antaŭdiri la kvanton de bazoj por kiu *Fn(a)* estas primo por fiksita *n*. La kvanto de ĝeneraligitaj primoj de Fermat povas esti malglate atendita kiel duono de *n'' pligrandigita per 1.

## Vidu ankaŭ 
* Primo de Mersenne
* Teoremo de Lucas
* Teoremo de Proth
* Pseŭdoprimo
* Primeco-testo
* Konstruebla nombro
* Nombro de Sierpinski
* Vico de Sylvester

## Referencoj 
## Eksteraj ligiloj 
*  - vico de nombroj de Fermat.
* 
* La prima glosaro: nombro de Fermat je la primaj paĝoj de Chrita Caldwell.
* Historio de nombroj de Fermat de Luigi Morelli
* Samspecigo de nombroj de Mersenne kaj Fermat   de John Cosgrave
* Primaj Faktoroj de nombroj de Fermat  de Wilfrid Keller
* Serĉi de ĝeneraligitaj primo de Fermat de Yves Gallot
* Originala anonco de faktorado de la naŭa nombro de Fermat

Kategorio:Nombroteorio
Kategorio:Nesolvitaj problemoj en matematiko
Kategorio:Grandaj nombroj