Nombro de Fermat

El Vikipedio, la libera enciklopedio
Saltu al: navigado, serĉo

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:

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 faktorigitaj. [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

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 de ĉi tiuj rilatoj povas esti pruvita per matematika indukto. De la lasta ekvacio, sekvas la teoremo de Goldbach: du nombroj de Fermat estas interprimoj (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ŭ

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

 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. [2] Fakte, ĉiu el jena listo estas malfermita problemo:

  • Ĉu estas Fn komponigita por ĉiuj n>4?
  • Ĉu estas malfinie multaj primoj de Fermat? (Ferdinand Eisenstein 1844)
  • Ĉu estas malfinie multaj komponigitaj 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)} < \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 Fn estas komponigita por 5≤n≤32, kvankam plenaj faktorigoj de Fn estas sciata nur por 0≤n≤11, kaj ne estas sciataj faktoroj por n en {14, 20, 22, 24}. La plej granda sciata komponigita 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.

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 komponigita. 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 sciata kiel provo de Pépin. Kvankam provo de Pépin kaj teoremo de Proth estas realigitaj sur komputiloj por pruvi la komponigitecon de multaj nombroj de Fermat, neniu provo 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 interprima al 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:
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: F5 = 622642 + 204492, tiel faktoro estas {pgkd}(62264\, +\, 2^{2^4}\, 20449,\, F_{5}) = 641.
Ekzemplo 2: F6 = 40468032562 + 14387937592, tiel faktoro estas {pgkd}(4046803256\, +\, 2^{2^5}\, 1438793759,\, F_{6}) = 274177.

Faktorigo de nombroj de Fermat[redakti | redakti fonton]

Pro la amplekso de nombroj de Fermat, estas malfacile faktorigi aŭ pruvi primecon de ili. Provo de Pépin estas necesa kaj sufiĉa provo 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,

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. (Ĉi tio estas kial iuj opinias ka 2 estas sesa 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,

(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[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 de amikeblaj 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,

P(F_n )\ge 2^{m+2}(4m+9)+1.

(Grytczuk, Luca kaj Wojtowicz. 2001)

Ĝeneraligita nombroj de Fermat[redakti | redakti fonton]

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[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]

Referencoj[redakti | redakti fonton]

  1. Primaj Faktoroj de nombroj de Fermat
  2. [1]
  3. [2]
  4. [3]

Eksteraj ligiloj[redakti | redakti fonton]