Nombro de Fermat
En matematiko nombro de Fermat estas pozitiva entjero de formo
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 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 F0 ... F4.
Bazaj propraĵoj
[redakti | redakti fonton]La nombroj de Fermat kontentigas jenajn rekursiecajn rilatojn
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 Fi kaj Fj havas komunan faktoron a>1. Tiam a dividas na ambaŭ
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
- 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
[redakti | redakti fonton]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
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. [2] 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
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 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 F32 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 k<2m. Se estas entjero a tia ke
tiam N estas primo. Male, se la pli supra kongrueco ne veras, kaj aldone
- (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 Fn > 3 estas primo se kaj nur se ĝi povas esti skribita unike kiel sumo de du nenulaj kvadratoj:
- Kiam ne estas de formo montrita pli supre, pozitiva faktoro estas:
- Ekzemplo 1: F5 = 622642 + 204492, tiel faktoro estas .
- Ekzemplo 2: F6 = 40468032562 + 14387937592, tiel faktoro estas .
Faktorado de nombroj de Fermat
[redakti | redakti fonton]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
[redakti | redakti fonton]Lemo: Se n estas pozitiva entjero,
pruvo:
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<n, 1<s≤n kaj s estas nepara.
Per la antaŭvenanta lemo, por pozitiva entjero m,
kie estas "pare dividas". Anstataŭigante a=2r, b=-1 kaj m=s,
kaj tial
Ĉ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)
- .
Teoremo de Édouard Lucas: Ĉiu prima dividanto p de Fn = estas de formo k2n+2+1 por n pli granda ol 1.
Interrilato al konstrueblaj plurlateroj
[redakti | redakti fonton]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
[redakti | redakti fonton]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. [4]
Estu P(Fn) la plej granda prima faktoro de nombro de Fermat Fn. Tiam,
- .
(Grytczuk, Luca kaj Wojtowicz. 2001)
Ĝeneraligita nombroj de Fermat
[redakti | redakti fonton]Nombroj de formo , 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 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
[redakti | redakti fonton]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ŭ
[redakti | redakti fonton]- Primo de Mersenne
- Teoremo de Lucas
- Teoremo de Proth
- Pseŭdoprimo
- Primeco-testo
- Konstruebla nombro
- Nombro de Sierpinski
- Vico de Sylvester
Referencoj
[redakti | redakti fonton]- ↑ Primaj Faktoroj de nombroj de Fermat. Arkivita el la originalo je 2016-02-10. Alirita 2008-03-17 .
- ↑ Arkivita kopio. Arkivita el la originalo je 2013-12-24. Alirita 2008-03-17 .
- ↑ Arkivita kopio. Arkivita el la originalo je 2006-10-02. Alirita 2008-03-17 .
- ↑ [1]
Eksteraj ligiloj
[redakti | redakti fonton]- 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]