Nombro de Fermat

En matematiko nombro de Fermat estas pozitiva entjero de formo

${\displaystyle 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:

F0	=	21	+	1	=	3
F1	=	22	+	1	=	5
F2	=	24	+	1	=	17
F3	=	28	+	1	=	257
F4	=	216	+	1	=	65,537
F5	=	232	+	1	=	4,294,967,297
					=	641 × 6,700,417
F6	=	264	+	1	=	18,446,744,073,709,551,617
					=	274,177 × 67,280,421,310,721
F7	=	2128	+	1	=	340,282,366,920,938,463,463,374,607,431,768,211,457
					=	59,649,589,127,497,217 × 5,704,689,200,685,129,054,721
F8	=	2256	+	1	=	115,792,089,237,316,195,423,570,985,008,687,907,853,269,984,665,640,564,039,457,584,007,913,129,639,937
					=	1,238,926,361,552,897 × 93,461,639,715,357,977,769,163,558,199,606,896,584,051,237,541,638,188,580,280,321

Kiel en 2007, nur la unuaj 12 nombroj de Fermat estas plene faktoritaj. ^[1]

Se 2ⁿ+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 2ⁿ + 1 ≡ (2^a)^b + 1 ≡ (−1)^b + 1 ≡ 0 (mod 2^a + 1)). En aliaj vortoj, ĉiu primo de la formo 2ⁿ + 1 estas nombro de Fermat, kaj ĉi tiaj primoj estas nomataj kiel primoj de Fermat. La nuraj sciataj primoj de Fermat estas F₀ ... F₄.

Bazaj propraĵoj

La nombroj de Fermat kontentigas jenajn rekursiecajn rilatojn

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

${\displaystyle F_{n}=F_{n-1}+2^{2^{n-1}}F_{0}\cdots F_{n-2}}$

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

${\displaystyle 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≤i<j kaj F_i kaj F_j havas komunan faktoron a>1. Tiam a dividas na ambaŭ

${\displaystyle F_{0}\cdots F_{j-1}}$

kaj F_j; 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 F_n, elektu priman faktoron p_n; tiam la vico {p_n} estas malfinia vico de diversaj primoj.

Pluaj propraĵoj:

• La kvanto de ciferoj D(n,b) de F_n esprimita en la bazo b estas

${\displaystyle 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 F₁ = 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 F₀,...,F₄ estas primoj. Tamen, ĉi tiu konjekto estis nuligita de Leonhard Euler kiu en 1732 montris ke

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

Eŭlero pruvis ke ĉiu eventuala faktoro de F_n devas havi formon k2ⁿ⁺¹+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 F_n kun n > 4. Tamen, tre malmulto estas sciata pri nombroj de Fermat kun granda n. ^[2] Fakte, ĉiu el jena listo estas malfermita problemo:

• Ĉu estas F_n 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

${\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}}.}$

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. ^[3]

Kiel en 2006, estas sciate ke F_n estas komponita por 5≤n≤32, kvankam plenaj faktoradoj de F_n 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 F_2478782, kaj ĝia prima faktoro 3×2^2478785 + 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₃₂ estas de ordo de unu al 10⁹.

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

• Teoremo de Proth - (1878) Estu N=k2^m+1 kun nepara k<2^m. Se estas entjero a tia ke

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

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

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

tiam N estas komponita. Se N=F_n>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:

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

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

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

Ekzemplo 1: F₅ = 62264² + 20449², tiel faktoro estas ${\displaystyle {pgkd}(62264\,+\,2^{2^{4}}\,20449,\,F_{5})=641}$.

Ekzemplo 2: F₆ = 4046803256² + 1438793759², tiel faktoro estas ${\displaystyle {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 F_n estas de formo 2ⁿ⁺²k+1, kie k estas pozitiva entjero.

Aliaj teoremoj pri nombroj de Fermat

Lemo: Se n estas pozitiva entjero,

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

pruvo:

${\displaystyle (a-b)\sum _{k=0}^{n-1}a^{k}b^{n-1-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 =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}-b^{n}}$

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

pruvo:

Por n=0, 2⁰+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<n, 1<s≤n kaj s estas nepara.

Per la antaŭvenanta lemo, por pozitiva entjero m,

${\displaystyle (a-b)\mid (a^{m}-b^{m})}$

kie ${\displaystyle \mid }$ estas "pare dividas". Anstataŭigante a=2^r, b=-1 kaj m=s,

${\displaystyle (2^{r}+1)\mid (2^{rs}+1),}$

kaj tial

${\displaystyle (2^{r}+1)\mid (2^{n}+1).}$

Ĉar 2^r+1>1, 2ⁿ+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)

${\displaystyle {\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 F_n = ${\displaystyle 2^{2^{\overset {n}{}}}+1}$ estas de formo k2ⁿ⁺²+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= 2^kp₁p₂...p_s, kie k estas nenegativa entjero kaj la p_i 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 nⁿ+1 estas primo, do ekzistas entjero m tia ke n=2^2m. La ekvacio nⁿ+1=F_(2^m+m) veras tiam. ^[4]

Estu P(F_n) la plej granda prima faktoro de nombro de Fermat F_n. Tiam,

${\displaystyle P(F_{n})\geq 2^{m+2}(4m+9)+1}$.

(Grytczuk, Luca kaj Wojtowicz. 2001)

Ĝeneraligita nombroj de Fermat

Nombroj de formo ${\displaystyle 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 ${\displaystyle a^{2^{\overset {n}{}}}+1}$ kiel F_n(a). En ĉi tiu skribmaniero, ekzemple, la nombro 100000001 povas esti skribita kiel F₃(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 F_n(a) kun n>4 estas F₅(30)=30³²+1.

Pli ellabori teorio povas esti uzita por antaŭdiri la kvanton de bazoj por kiu F_n(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

1. Primaj Faktoroj de nombroj de Fermat. Arkivita el la originalo je 2016-02-10. Alirita 2008-03-17 .
2. Arkivita kopio. Arkivita el la originalo je 2013-12-24. Alirita 2008-03-17 .
3. Arkivita kopio. Arkivita el la originalo je 2006-10-02. Alirita 2008-03-17 .

Eksteraj ligiloj

• A000215 en OEIS - vico de nombroj de Fermat.
• Eric W. Weisstein, Nombro de Fermat en MathWorld.
• 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 Arkivigite je 2006-10-02 per la retarkivo Wayback Machine de John Cosgrave
• Primaj Faktoroj de nombroj de Fermat Arkivigite je 2016-02-10 per la retarkivo Wayback Machine de Wilfrid Keller
• Serĉi de ĝeneraligitaj primo de Fermat de Yves Gallot
• Originala anonco de faktorado de la naŭa nombro de Fermat^{[rompita ligilo]}