Nombro de Carmichael

El Vikipedio, la libera enciklopedio
Saltu al: navigado, serĉo
Estas ankaŭ teoremo de Carmichael pri fibonaĉi-nombroj.

En nombroteorio, nombro de Carmichaelabsoluta pseŭdoprimo de Fermat estas komponigita pozitiva entjero n kiu kontentigas la kongrueco b^{n-1}~\equiv 1 \pmod{n} por ĉiu entjero b kiu estas interprimo al n (vidu en modula aritmetiko).

La nombroj estas nomitaj pro Robert Daniel Carmichael. La nombroj de Carmichael estas nombroj de Knödel K1.

Ĝenerala priskribo[redakti | redakti fonton]

Malgranda teoremo de Fermat diras ke se p estas primo kaj a estas interprimo al p, 1≤a<p, tiam ap-1-1 estas dividebla per p. Se nombro x estas ne primo, a estas interprimo al x, 1≤a<x kaj x dividas na ax-1-1, tiam x estas pseŭdoprimo al bazo a. Nombro x kiu estas pseŭdoprimo por ĉiuj valoroj de a kiuj estas interprimoj al x estas nombro de Carmichael.

Malgranda teoremo de Fermat diras ke ĉiuj primoj havas certan propraĵon. En ĉi tiu senco nombroj de Carmichael estas similaj al primoj.

Nombroj de Carmichael estas gravaj ĉar ili povas ĉirkaŭiri la primecan provon de Fermat, ĉiuj nombroj estas por ili ĉiam neatestantoj de Fermat. Pro tio ke nombroj de Carmichael ekzistas, ĉi tiu primeca provo ne povas esti fidita por pruvi la primecon de nombro, kvankam ĝi povas ankoraŭ esti uzata por pruvi ke nombro estas komponigita.

Ankaŭ, se nombroj iĝi pli grandajn, nombroj de Carmichael iĝi tre maloftajn. Ekzemple, estas 1401644 nombroj de Carmichael inter 1 kaj 1018 (proksimume unu el 700·109 nombroj.)[1]

Alternativa kaj ekvivalenta difino de nombro de Carmichael estas donita per teoremo de Korselt.

Teoremo (Korselt 1899): Pozitiva komponigita entjero n estas nombro de Carmichael se kaj nur se n estas kvadrato-libera, kaj por ĉiuj primaj divizoroj p de n, veras ke (p - 1) | (n - 1) (la skribmaniero a | b indikas ke a dividas na b).

El ĉi tiu teoremo sekvas ke ĉiuj nombroj de Carmichael estas neparaj.

Korselt estis la unua kiu observis ĉi tiujn propraĵojn, sed li ne povis trovi ekzemplon. En 1910 Carmichael trovis la unuan kaj plej malgrandan ĉi tian nombron, 561.

Tio ke 561 estas nombro de Carmichael povas vidiĝi de teoremo de Korselt. Ja, 561 = 3 ∙ 11 ∙ 17 estas kvadratolibera kaj 2 | 560, 10 | 560 kaj 16 | 560.

La unuaj kelkaj nombroj de Carmichael estas:

561 = 3 ∙ 11 ∙ 17   (2 | 560, 10 | 560, 16 | 560)
1105 = 5 ∙ 13 ∙ 17   (4 | 1104, 12 | 1104, 16 | 1104)
1729 = 7 ∙ 13 ∙ 19   (6 | 1728, 12 | 1728, 18 | 1728)
2465 = 5 ∙ 17 ∙ 29   (4 | 2464, 16 | 2464, 28 | 2464)
2821 = 7 ∙ 13 ∙ 31   (6 | 2820, 12 | 2820, 30 | 2820)
6601 = 7 ∙ 23 ∙ 41   (6 | 6600, 22 | 6600, 40 | 6600)
8911 = 7 ∙ 19 ∙ 67   (6 | 8910, 18 | 8910, 66 | 8910)

J. Chernick pruvis teoremon en 1939 kiu povas esti uzita por konstrui subaron de nombroj de Carmichael. Nombro (6k + 1)(12k + 1)(18k + 1) estas nombro de Carmichael se ĉiuj ĝiaj tri faktoroj estas primoj.

Löh kaj Niebuhr en 1992 trovis iujn el ĉi tiuj gigantaj nombroj de Carmichael inkluzivante unuon kun 1101518 faktoroj kaj pli ol 16 milionoj ciferoj.

Propraĵoj[redakti | redakti fonton]

Nombro de Carmichael havas almenaŭ 3 primajn faktorojn. La unuaj nombroj de Carmichael kun k primaj faktoroj estas:

k
3 561 = 3 ∙ 11 ∙ 17
4 41041 = 7 ∙ 11 ∙ 13 ∙ 41
5 825265 = 5 ∙ 7 ∙ 17 ∙ 19 ∙ 73
6 321197185 = 5 ∙ 19 ∙ 23 ∙ 29 ∙ 37 ∙ 137
7 5394826801 = 7 ∙ 13 ∙ 17 ∙ 23 ∙ 31 ∙ 67 ∙ 73
8 232250619601 = 7 ∙ 11 ∙ 13 ∙ 17 ∙ 31 ∙ 37 ∙ 73 ∙ 163
9 9746347772161 = 7 ∙ 11 ∙ 13 ∙ 17 ∙ 19 ∙ 31 ∙ 37 ∙ 41 ∙ 641

La unuaj nombroj de Carmichael kun 4 primaj faktoroj estas:

i
1 41041 = 7 ∙ 11 ∙ 13 ∙ 41
2 62745 = 3 ∙ 5 ∙ 47 ∙ 89
3 63973 = 7 ∙ 13 ∙ 19 ∙ 37
4 75361 = 11 ∙ 13 ∙ 17 ∙ 31
5 101101 = 7 ∙ 11 ∙ 13 ∙ 101
6 126217 = 7 ∙ 13 ∙ 19 ∙ 73
7 172081 = 7 ∙ 13 ∙ 31 ∙ 61
8 188461 = 7 ∙ 13 ∙ 19 ∙ 109
9 278545 = 5 ∙ 17 ∙ 29 ∙ 113
10 340561 = 13 ∙ 17 ∙ 23 ∙ 67

La dua nombro de Carmichael (1105) povas esti esprimita kiel sumo de du kvadratoj en pli multaj manieroj ol ĉiu pli malgranda nombro. La tria nombro de Carmichael (1729) estas la nombro de Hardy-Ramanujan: la plej malgranda nombro kiu povas esti esprimita kiel sumo de du kuboj en du malsamaj manieroj.

Distribuo[redakti | redakti fonton]

Estu C(X) kvanto de nombroj de Carmichael malpli grandaj ol aŭ egalaj al X.

La tabelo donas distribuon de nombroj de Carmichael supren ĝis potencoj de 10 (de Pinch 2006):

n 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
C(10n) 1 7 16 43 105 255 646 1547 3605 8241 19279 44706 105212 246683 585355 1401644 3381806 8220777

Erdős pruvis en lia 1956 papero ke

C(X) < X \exp{\frac{-k \log{X} \log{\log{\log{X}}}}{\log{\log{X}}}}

por iu konstanto k.

La tabelo pli sube donas aproksimaĵojn por ĉi tiu konstanto:

n k por C(10n)
4 2,19547
6 1,97946
8 1,90495
10 1,86870
12 1,86377
14 1,86293
16 1,86406
18 1,86522
20 1,86598

En la alia direkto, Paŭlo Erdős heŭristike argumentis ke devas ekzisti malfinie multaj nombroj de Carmichael. En 1994 estis montrite de W. R. (Red) Alford, Andrew Granville kaj Carl Pomerance ke reale ekzistas malfinie multaj nombroj de Carmichael. Aparte, ili montris ke

C(X) > X(2/7)

por sufiĉe granda X [2]. Glyn Harman pruvis ke

C(X) > X0.332

denove por sufiĉe granda X.[3] Ĉi tiu aŭtoro sinsekve plibonigis la eksponenton al proksime kaj super 1/3. Paŭlo Erdős ankaŭ donis heŭristikon sugestantan ke lia supera baro devas esti proksima al la vera kurzo de kreskado de C(X).


Referencoj[redakti | redakti fonton]

  1. Richard Pinch, "La nombroj de Carmichael supren ĝis 1018", aprilo de 2006 (surbaze de lia pli frua laboro [1][2][3]).
  2. W. R. (Red) Alford, Andrew Granville kaj Carl Pomerance. "Estas malfinie multaj nombroj de Carmichael" Analoj de matematiko 139 (1994) 703-722.
  3. Glyn Harman. "On the number of Carmichael numbers up to X." - "Pri la kvanto de nombroj de Carmichael supren ĝis X." Bull. Lond. Math. Soc. 37 (2005) 641-650.

Eksteraj ligiloj[redakti | redakti fonton]