Carmichael-számok

A Wikipédiából, a szabad enciklopédiából
Jump to navigation Jump to search

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[szerkeszté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 olyan összetett számok, melyekre moduláris aritmetika szerint ugyanez a tulajdonság igaz. 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[szerkesztés]

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[szerkesztés]

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[szerkesztés]

Prímtényezős felbontások[szerkesztés]

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[szerkesztés]

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[szerkesztés]

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[szerkesztés]

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[szerkesztés]

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[szerkesztés]

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[szerkesztés]

  1. a b c Richard Pinch, "The Carmichael numbers up to 1021", 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é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.
  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.  
  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.  
  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.  
  7. a b 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 14.). „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.  
  10. a b 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.  
  12. Pomerance, C. (1981). „On the distribution of pseudoprimes”. Math. Comp. 37, 587–593. o. DOI:10.1090/s0025-5718-1981-0628717-0.  
  13. Everett W. Howe. "Higher-order Carmichael numbers." Mathematics of Computation 69 (2000), pp. 1711–1719.

További információk[szerkesztés]