Carmichael-számok
A számelmélet területén egy Carmichael-szám olyan összetett szám, amire teljesül a moduláris aritmetikai kongruenciareláció:
- ,
méghozzá minden -hez relatív prím egészre. Nevüket Robert Carmichaelről kapták. A Carmichael-számok a Knödel-számok K1 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 1021 között mindössze 20 138 200 Carmichael-szám van (kb. 1 : 5·1013 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 pozitív egész összetett szám akkor és csak akkor Carmichael-szám, ha négyzetmentes, és minden prímosztójára igaz, hogy .
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 kifejezés szerint páros oszt páratlant, ami ellentmondás. (A Carmichael-számok páratlan mivolta következik abból is, hogy 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, négyzetmentes, továbbá .
A következő hat Carmichael-szám (A002997 sorozat az OEIS-ben):
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 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·10329 − 59827428149)·(14784·10329 − 68374203599)·(20328·10329 − 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 -re legalább Carmichael-szám létezik 1 és 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 darab prímtényezővel a (A006931 sorozat az OEIS-ben) sorolja:
k | |
---|---|
3 | |
4 | |
5 | |
6 | |
7 | |
8 | |
9 |
Az első Carmichael-számok 4 prímtényezővel (A074379 sorozat az OEIS-ben):
i | |
---|---|
1 | |
2 | |
3 | |
4 | |
5 | |
6 | |
7 | |
8 | |
9 | |
10 |
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 az -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]
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | |
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:
ahol konstans.
Erdős Pál 1956-ban javította a korlátot:[10]
ahol konstans. Erdős heurisztikus érvelése szerint ez a felső korlát közel lehet a 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 -re n növekvő értékeinél:
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
2005-ben ezt a korlátot Harman tovább javította[11]
- -re,
majd kicsivel 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 Carmichael-szám létezik. Pomerance 1981-ben[12] megjavította Erdős heurisztikus érvelését a következőre:
- .
Az eddig kiszámított adatok (például a Pinch[1] által 1021-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 -ban lévő nemnulla prímideál esetében bármely -ben lévő -ra, ahol a idál normája. (Ez a kis Fermat-tétel általánosítása, ami szerint minden m egészre, ha p prímszám.) Legyen egy -ban lévő nemnulla ideál Carmichael-ideál, ha nem prímideál és minden all -ban lévő -ra, ahol az ideál normája. Ha K éppen , akkor az ideál főideál, és ha a a pozitív generátora, akkor az 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 Carmichael-ideáljainak leírása: bármely p prímszámra, ami K-ben teljesen felbomlik, a főideál Carmichael-ideál. Mivel bármely számtestben végtelen sok prímszám bomlik fel teljesen, ezért -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 = 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 pn n-edik hatványra emelő függvény az egész számokat modulo n tartalmazó Zn gyűrűn értelmezve Zn-be éppen az identitásfüggvényt adja. Az identitás az egyetlen Zn-algebrai endomorfizmus Zn-en, tehát a definíció újrafogalmazható úgy, hogy pn legyen Zn algebra-endomorfizmusa. Ahogy korábban is, a pn akkor elégíti ki a feltételt, ha n prímszám.
Az n-edik hatványra emelő pn függvény definiálható bármely A Zn-algebrában. Egy tétel szerint n akkor és csak akkor prím, ha minden ilyen pn 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 pn endomorfizmus minden olyan Zn-algebrán, ami m elemből generálható mint Zn-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 1021", 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égyzetmentes, de nem ciklikus, két prímtényezőjére, -re és -re igaz, hogy . De ha teljesíti a Korselt-kritériumokat, akkor , és az „osztója” reláció tranzitivitása miatt . De osztója -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. augusztus 8.). „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.
- ↑ 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 ”. 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
- Tables of Carmichael numbers below 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