Carmichael-számok

A számelmélet területén egy Carmichael-szám olyan $n$ összetett szám, amire teljesül a moduláris aritmetikai kongruenciareláció:

$b^{n-1}\equiv 1{\pmod {n}}$,

méghozzá minden $n$-hez relatív prím $1<b<n$ egészre. Nevüket Robert Carmichaelről kapták. A Carmichael-számok a Knödel-számok K₁ részhalmazát képezik.

Áttekintés

A kis Fermat-tétel kimondja, hogy ha p prímszám, akkor bármely b egész számra a b ^p − b szám p többszöröse. A Carmichael-számok az ilyen tulajdonságú összetett számok. A Carmichael-számokat Fermat-álprímeknek vagy abszolút Fermat-álprímeknek is nevezik. A Carmichael-számok jelentősége abban rejlik, hogy összetett számok, mégis átmennek a Fermat-prímteszten. A Carmichael-számok létezése miatt a Fermat-prímteszt önmagában nem alkalmas egy szám prímségének egyértelmű eldöntésére, bár arra igen, hogy egy szám összetett szám voltát igazolja. Ez a kis Fermat-tételen alapuló prímteszteket kockázatosabbá teszi a biztosabb teszteknél, amilyen a Solovay–Strassen-prímteszt vagy bármely erős álprím-teszt. Mindenesetre minél nagyobb számokról van szó, a Carmichael-számok annál ritkábban helyezkednek el közöttük. Például 1 és 10²¹ között mindössze 20 138 200 Carmichael-szám van (kb. 1 : 5·10¹³ az arány).

Korselt kritériuma

A Carmichael-számok egy alternatív és az eredetivel egyenértékű megfogalmazása Korselt kritériumán alapszik.

Tétel (A. Korselt 1899): Egy $n$ pozitív egész összetett szám akkor és csak akkor Carmichael-szám, ha $n$ négyzetmentes, és $n$ minden $p$ prímosztójára igaz, hogy $p-1\mid n-1$.

A tételből következik, hogy minden Carmichael-szám páratlan, hiszen bármely négyzetmentes páros összetett számnak (melynek tehát csak egyszeres prímtényezője a 2) van legalább egy páratlan prímtényezője, ezért a $p-1\mid n-1$ kifejezés szerint páros oszt páratlant, ami ellentmondás. (A Carmichael-számok páratlan mivolta következik abból is, hogy $-1$ Fermat-tanúja bármely páros összetett számnak.) A kritériumból következik az is, hogy a Carmichael-számok ciklikusak. Az eddigiekből az is következik, hogy egyik Carmichael-számnak sincsen pontosan két prímtényezője (nem félprímek).

Felfedezésük

Korselt volt az első, aki megállapította a Carmichael-számok alapvető tulajdonságait, de anélkül, hogy egyetlen példa is ismert lett volna előtte. 1910-ben Carmichael találta meg az első, egyben legkisebb ilyen számot, az 561-et, innen a „Carmichael-szám” elnevezés.

Az, hogy az 561 Carmichael-szám, jól látható a Korselt-féle kritérium alapján. Valóban, $561=3\cdot 11\cdot 17$ négyzetmentes, továbbá $2\mid 560,\quad 10\mid 560,\quad 16\mid 560$.

A következő hat Carmichael-szám (A002997 sorozat az OEIS-ben):

$1105=5\cdot 13\cdot 17\qquad (4\mid 1104;\quad 12\mid 1104;\quad 16\mid 1104)$

$1729=7\cdot 13\cdot 19\qquad (6\mid 1728;\quad 12\mid 1728;\quad 18\mid 1728)$

$2465=5\cdot 17\cdot 29\qquad (4\mid 2464;\quad 16\mid 2464;\quad 28\mid 2464)$

$2821=7\cdot 13\cdot 31\qquad (6\mid 2820;\quad 12\mid 2820;\quad 30\mid 2820)$

$6601=7\cdot 23\cdot 41\qquad (6\mid 6600;\quad 22\mid 6600;\quad 40\mid 6600)$

$8911=7\cdot 19\cdot 67\qquad (6\mid 8910;\quad 18\mid 8910;\quad 66\mid 8910).$

Az első hét Carmichael-számot, 561-től 8911-ig valójában a cseh matematikus, Václav Šimerka találta meg 1885-ben (ezzel Carmichael mellett Korseltet is megelőzve, bár Šimerka nem fedezett fel a Korselt-kritériumhoz hasonlót). Munkája azonban feledésbe merült.

J. Chernick 1939-ben igazolt egy tételt, aminek segítségével a Carmichael-számok egy részhalmaza előállítható. A $(6k+1)(12k+1)(18k+1)$ alakú számok Carmichael-számok abban az esetben, ha a szorzat mindhárom tényezője prímszám. Nyitott kérdés, hogy ez a képlet végtelen sok Carmichael-számot előállít-e, bár ez a Dickson-sejtésből következne.

Gérard P. Michon hasonló módszert alkotott Carmichael-számok konstruálására:

Ha m ≡ 326 mod 616 és a 7m + 1, 8m + 1 és 11m + 1 számok mind prímszámok, akkor a (7m+1)·(8m+1)·(11m+1) szorzat Carmichael-szám. Az m-nek hárommal oszthatónak kell lennie, különben a három szám közül valamelyik 3-mal osztható lesz.

Példa: m = 24966-ra mindhárom szám prím: 174763, 199729, 274627 – szorzatuk ezért Carmichael-szám.
Michon módszerével egy 1000 jegyű Carmichael-szám előállítása:

(12936·10³²⁹ − 59827428149)·(14784·10³²⁹ − 68374203599)·(20328·10³²⁹ − 94014529949).

Erdős Pál heurisztikusan a végtelen sok Carmichael-szám létezése mellett érvelt. 1994-ben W. R. (Red) Alford, Andrew Granville és Carl Pomerance igazolták, hogy valóban végtelen sok Carmichael-szám létezik. Egész pontosan megmutatták, hogy elegendően nagy $n$-re legalább $n^{2/7}$ Carmichael-szám létezik 1 és $n$ között.

Löh és Niebuhr 1992-ben néhány igen nagyméretű Carmichael-számot állítottak elő, köztük egy több mint 16 millió jegyűt, 1 101 518 prímtényezővel.

Erdős Pál csoportelméleti megfontolásai és modern számítógépes algoritmusok segítségével 2012 júliusában előállítottak egy több mint 10 milliárd prímtényezővel rendelkező és több mint 300 milliárd jegyű Carmichael-számot.

Tulajdonságaik

Prímtényezős felbontások

A Carmichael-számoknak legalább három pozitív prímtényezőjük van. Léteznek olyan R számok, melyekhez végtelen sok éppen R prímtényezővel rendelkező Carmichael-szám tartozik; sőt, végtelen sok ilyen R szám létezik.

Az első Carmichael-számokat $k=3,4,5,\ldots$ darab prímtényezővel a (A006931 sorozat az OEIS-ben) sorolja:

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

Az első Carmichael-számok 4 prímtényezővel (A074379 sorozat az OEIS-ben):

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

A második Carmichael-szám (1105) többféleképpen fejezhető ki két szám négyzetének összegeként, mint bármely nála kisebb szám. A harmadik Carmichael-szám (1729) pedig a legkisebb szám, ami kétféleképpen írható fel két pozitív köbszám összegeként.

Eloszlásuk

Jelölje $C(X)$ az $X$-nél nem nagyobb Carmichael-számok számát. A Carmichael-számok eloszlása 10 hatványai szerint (A055553 sorozat az OEIS-ben):

$n$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
$C(10^{n})$	0	0	1	7	16	43	105	255	646	1547	3605	8241	19279	44706	105212	246683

1953-ban Knödel igazolta a következő felső korlátot:

$C(X)<X\exp \left({-k_{1}\left(\log X\log \log X\right)^{\frac {1}{2}}}\right)$

ahol $k_{1}$ konstans.

Erdős Pál 1956-ban javította a korlátot:

$C(X)<X\exp \left({\frac {-k_{2}\log X\log \log \log X}{\log \log X}}\right)$

ahol $k_{2}$ konstans. Erdős heurisztikus érvelése szerint ez a felső korlát közel lehet a $C(X)$ valódi növekedési rátájához. A következő táblázat megadja az Erdős-féle korlátban szereplő k konstans hozzávetőleges minimális értékeit $X=10^{n}$-re n növekvő értékeinél:

$n$	4	6	8	10	12	14	16	18	20	21
k	2,19547	1,97946	1,90495	1,86870	1,86377	1,86293	1,86406	1,86522	1,86598	1,86619

A másik irányban Alford, Granville és Pomerance 1994-ben igazolták, hogy elegendően nagy X esetében

$C(X)>X^{\frac {2}{7}}.$

2005-ben ezt a korlátot Harman tovább javította

$C(X)>X^{0,332}$-re,

majd kicsivel $1/3$ fölé.

A Carmichael-számok aszimptotikus eloszlásával több sejtés foglalkozik. Erdős 1956-os sejtése szerint kellően nagy X-re $X^{1-o(1)}$ Carmichael-szám létezik. Pomerance 1981-ben megjavította Erdős heurisztikus érvelését a következőre:

$X^{1-{\frac {\{1+o(1)\}\log \log \log X}{\log \log X}}}$.

Az eddig kiszámított adatok (például a Pinch által 10²¹-ig végzett számítások) még nem mutatják a sejtések érvényességét.

Általánosítások

A Carmichael-szám mögött álló elgondolás általánosítható egy K számtest Carmichael-ideáljaként. Bármely ${\mathcal {O}}_{K}$-ban lévő ${\mathfrak {p}}$ nemnulla prímideál esetében $\alpha ^{{\rm {N}}({\mathfrak {p}})}\equiv \alpha ({\bmod {\mathfrak {p}}})$ bármely ${\mathcal {O}}_{K}$-ben lévő $\alpha$-ra, ahol ${\rm {N}}({\mathfrak {p}})$ a ${\mathfrak {p}}$ idál normája. (Ez a kis Fermat-tétel általánosítása, ami szerint $m^{p}\equiv m({\bmod {p}})$ minden m egészre, ha p prímszám.) Legyen egy ${\mathcal {O}}_{K}$-ban lévő ${\mathfrak {a}}$ nemnulla ideál Carmichael-ideál, ha nem prímideál és $\alpha ^{{\rm {N}}({\mathfrak {a}})}\equiv \alpha ({\bmod {\mathfrak {a}}})$ minden all ${\mathcal {O}}_{K}$-ban lévő $\alpha$-ra, ahol ${\rm {N}}({\mathfrak {a}})$ az ${\mathfrak {a}}$ ideál normája. Ha K éppen $\mathbf {Q}$, akkor az ${\mathfrak {a}}$ ideál főideál, és ha a a pozitív generátora, akkor az ${\mathfrak {a}}=(a)$ ideál pontosan akkor Carmichael-féle, amikor a a szokott értelemben vett Carmichael-szám.

Ha K nagyobb, mint a racionális számok halmaza, könnyű az ${\mathcal {O}}_{K}$ Carmichael-ideáljainak leírása: bármely p prímszámra, ami K-ben teljesen felbomlik, a $p{\mathcal {O}}_{K}$ főideál Carmichael-ideál. Mivel bármely számtestben végtelen sok prímszám bomlik fel teljesen, ezért ${\mathcal {O}}_{K}$-ban végtelen sok Carmichael-ideál létezik. Például ha p olyan prímszám, hogy p≡1 (mod 4), akkor a Z[i] Gauss-egészek körében (p) Carmichael-ideál.

A prímek és a Carmichael-számok is teljesítik a következő egyenlőséget:

$\gcd \left(\sum _{x=1}^{n-1}x^{n-1},n\right)=1$ (gcd = lnko)

Magasabbrendű Carmichael-számok

A Carmichael-számok az absztrakt algebra koncepcióinak segítségével más módon is általánosíthatók.

Egy n összetett szám pontosan akkor Carmichael-szám, ha a p_n n-edik hatványra emelő függvény az egész számokat modulo n tartalmazó Z_n gyűrűn értelmezve Z_n-be éppen az identitásfüggvényt adja. Az identitás az egyetlen Z_n-algebrai endomorfizmus Z_n-en, tehát a definíció újrafogalmazható úgy, hogy p_n legyen Z_n algebra-endomorfizmusa. Ahogy korábban is, a p_n akkor elégíti ki a feltételt, ha n prímszám.

Az n-edik hatványra emelő p_n függvény definiálható bármely A Z_n-algebrában. Egy tétel szerint n akkor és csak akkor prím, ha minden ilyen p_n függvény algebra-endomorfizmus.

Ezzel a két feltétellel lehet megalkotni az m-edrendű Carmichael-szám fogalmát; bármely pozitív egész m számra olyan n összetett szám, melyre p_n endomorfizmus minden olyan Z_n-algebrán, ami m elemből generálható mint Z_n-modulus. Az 1 rendű Carmichael-számok egyszerűen a közönséges Carmichael-számok.

Másodrendű Carmichael-szám

Howe szerint a 17 · 31 · 41 · 43 · 89 · 97 · 167 · 331 egy másodrendű Carmichael-szám. A szorzat értéke 443 372 888 629 441.

Tulajdonságaik

A Korselt-féle kritérium kiterjeszthető a magasabb rendű Carmichael-számokra, ahogy azt Howe megmutatta.

Ugyanebben a tanulmányában szerepel egy heurisztikus érvelés arra nézve, hogy bármely m-re végtelen sok m-edrendű Carmichael-szám létezik. Ennek ellenére egyetlen 3-ad vagy magasabb rendű Carmichael-szám sem ismeretes.

Jegyzetek

• Carmichael, R. D. (1910). „Note on a new number theory function”. Bulletin of the American Mathematical Society 16 (5), 232–238. o. DOI:10.1090/s0002-9904-1910-01892-9.  
• Carmichael, R. D. (1912). „On composite numbers P which satisfy the Fermat congruence $a^{P-1}\equiv 1{\bmod {P}}$”. American Mathematical Monthly 19 (2), 22–27. o. DOI:10.2307/2972687.  
• Chernick, J. (1939). „On Fermat's simple theorem”. Bull. Amer. Math. Soc. 45, 269–274. o. DOI:10.1090/S0002-9904-1939-06953-X.  
• Korselt, A. R. (1899). „Problème chinois”. L'Intermédiaire des Mathématiciens 6, 142–143. o.  
• Löh, G.; Niebuhr, W. (1996). „A new algorithm for constructing large Carmichael numbers”. Math. Comp. 65, 823–836. o. DOI:10.1090/S0025-5718-96-00692-8.  
• Ribenboim, P.. The Book of Prime Number Records. Springer (1989). ISBN 978-0-387-97042-4 
• Šimerka, V. (1885). „Zbytky z arithmetické posloupnosti (On the remainders of an arithmetic progression)”. Časopis pro pěstování matematiky a fysiky 14 (5), 221–225. o.  

További információk

• Alice és Bob - 23. rész: Alice és Bob prímszámok után nyomoz
• Alice és Bob - 24. rész: Alice és Bob komolyabb fegyverekhez nyúl
• Alice és Bob - 26. rész: Alice és Bob átlépi a célvonalat
• Encyclopedia of Mathematics: Carmichael number
• Table of Carmichael numbers
• Carmichael numbers up to $10^{12}$
• Tables of Carmichael numbers below $10^{18}$ Archiválva 2016. április 21-i dátummal a Wayback Machine-ben
• MathPages: "The Dullness of 1729"
• Weisstein, Eric W.: Carmichael Number (angol nyelven). Wolfram MathWorld
• Final Answers Modular Arithmetic