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

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.^[2]^[3] 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^[4] 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^[5] (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^[6] 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.^[7]

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

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

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):^[1]

$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:^[10]

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,^[7] hogy elegendően nagy X esetében

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

2005-ben ezt a korlátot Harman tovább javította^[11]

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^[10] szerint kellően nagy X-re $X^{1-o(1)}$ Carmichael-szám létezik. Pomerance 1981-ben^[12] 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^[1] á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.^[13]

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

↑ ^a ^b ^c Richard Pinch, "The Carmichael numbers up to 10²¹", May 2007.
↑ Carmichael Multiples of Odd Cyclic Numbers "Any divisor of a Carmichael number kmust be an odd cyclic number"
↑ A bizonyítás nagy vonalakban: ha $n$ négyzetmentes, de nem ciklikus, $n$ két prímtényezőjére, $p_{i}$ -re és $p_{j}$ -re igaz, hogy $p_{i}\mid p_{j}-1$ . De ha $n$ teljesíti a Korselt-kritériumokat, akkor $p_{j}-1\mid n-1$ , és az „osztója” reláció tranzitivitása miatt $p_{i}\mid n-1$ . De $p_{i}$ osztója $n$ -nek is, ami ellentmondás.
↑ R. D. Carmichael (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.
↑ V. Šimerka (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.
↑ Chernick, J. (1939). „On Fermat's simple theorem”. Bull. Amer. Math. Soc. 45, 269–274. o. DOI:10.1090/S0002-9904-1939-06953-X.
↑ ^a ^b W. R. Alford (1994). „There are Infinitely Many Carmichael Numbers”. Annals of Mathematics 139, 703–722. o. DOI:10.2307/2118576.
↑ Steven Hayman, Andrew Shallue: Constructing a ten billion factor Carmichael number Poster auf der ANTS X-Konferenz, San Diego, Juli 2012
↑ Wright, Thomas (2016. november 29.). „Factors of Carmichael numbers and a weak k-tuples conjecture”. Journal of the Australian Mathematical Society 100 (3), 421-429. o, Kiadó: Australian Mathematical Publishing Association Inc.. DOI:10.1017/S1446788715000427. (Hozzáférés: 2016. augusztus 13.)
↑ ^a ^b Erdős, P. (1956). „On pseudoprimes and Carmichael numbers”. Publ. Math. Debrecen 4, 201–206. o.
↑ Glyn Harman (2005). „On the number of Carmichael numbers up to x”. Bulletin of the London Mathematical Society 37, 641–650. o. DOI:10.1112/S0024609305004686.
↑ Pomerance, C. (1981). „On the distribution of pseudoprimes”. Math. Comp. 37, 587–593. o. DOI:10.1090/s0025-5718-1981-0628717-0. JSTOR 2007448.
↑ Everett W. Howe. "Higher-order Carmichael numbers." Mathematics of Computation 69 (2000), pp. 1711–1719.

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

[Pinch2007-1] Richard Pinch, "The Carmichael numbers up to 10²¹", May 2007.

[2] Carmichael Multiples of Odd Cyclic Numbers "Any divisor of a Carmichael number kmust be an odd cyclic number"

[3] A bizonyítás nagy vonalakban: ha $n$ négyzetmentes, de nem ciklikus, $n$ két prímtényezőjére, $p_{i}$ -re és $p_{j}$ -re igaz, hogy $p_{i}\mid p_{j}-1$ . De ha $n$ teljesíti a Korselt-kritériumokat, akkor $p_{j}-1\mid n-1$ , és az „osztója” reláció tranzitivitása miatt $p_{i}\mid n-1$ . De $p_{i}$ osztója $n$ -nek is, ami ellentmondás.

[Carmichael1910-4] R. D. Carmichael (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.

[Simerka1885-5] V. Šimerka (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.

[Chernick1939-6] Chernick, J. (1939). „On Fermat's simple theorem”. Bull. Amer. Math. Soc. 45, 269–274. o. DOI:10.1090/S0002-9904-1939-06953-X.

[Alford1994-7] W. R. Alford (1994). „There are Infinitely Many Carmichael Numbers”. Annals of Mathematics 139, 703–722. o. DOI:10.2307/2118576.

[8] Steven Hayman, Andrew Shallue: Constructing a ten billion factor Carmichael number Poster auf der ANTS X-Konferenz, San Diego, Juli 2012

[9] Wright, Thomas (2016. november 29.). „Factors of Carmichael numbers and a weak k-tuples conjecture”. Journal of the Australian Mathematical Society 100 (3), 421-429. o, Kiadó: Australian Mathematical Publishing Association Inc.. DOI:10.1017/S1446788715000427. (Hozzáférés: 2016. augusztus 13.)

[Erdős1956-10] Erdős, P. (1956). „On pseudoprimes and Carmichael numbers”. Publ. Math. Debrecen 4, 201–206. o.

[11] Glyn Harman (2005). „On the number of Carmichael numbers up to x”. Bulletin of the London Mathematical Society 37, 641–650. o. DOI:10.1112/S0024609305004686.

[Pomerance1981-12] Pomerance, C. (1981). „On the distribution of pseudoprimes”. Math. Comp. 37, 587–593. o. DOI:10.1090/s0025-5718-1981-0628717-0. JSTOR 2007448.

[13] Everett W. Howe. "Higher-order Carmichael numbers." Mathematics of Computation 69 (2000), pp. 1711–1719.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]