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  Carmichael-szám van (kb. 1 : 5·1013 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  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. 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,  négyzetmentes, továbbá .

A következő hat Carmichael-szám :

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  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.

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,  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  darab prímtényezővel a  sorolja:

Az első Carmichael-számok 4 prímtényezővel :

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 :

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

ahol  konstans.

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

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:

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

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

majd kicsivel  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  Carmichael-szám létezik. Pomerance 1981-ben megjavította Erdős heurisztikus érvelését a következőre:

.

Az eddig kiszámított adatok (például a Pinch á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 .

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

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  
MathPages: "The Dullness of 1729"

Final Answers Modular Arithmetic

Nevezetes számsorozatok
Álprímek
Moduláris aritmetika
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ésközött mindössze Carmichael-szám van ( kb . : 5·1013 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 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 avan 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 . 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.ben Carmichael találta meg az első , egyben legkisebb ilyen számot , azet , innen a „ Carmichael-szám” elnevezés . Az , hogy azCarmichael-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 \ : Az első hét Carmichael-számot, tőlig valójában a cseh matematikus , Václav Šimerka találta megben ( 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. Chernickben 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 ≡modés a + +és +számok mind prímszámok , akkor a+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 valamelyikmal osztható lesz . Példa : m =ra mindhárom szám prím:– szorzatuk ezért Carmichael-szám . Michon módszerével egyjegyű Carmichael-szám előállítása : ( 12936·10329 −( 14784·10329 −( 20328·10329 − Erdős Pál heurisztikusan a végtelen sok Carmichael-szám létezése mellett érvelt.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és között . Löh és Niebuhrben néhány igen nagyméretű Carmichael-számot állítottak elő , köztük egy több mintmillió jegyűt , prímtényezővel . Erdős Pál csoportelméleti megfontolásai és modern számítógépes algoritmusok segítségéveljúliusában előállítottak egy több mintmilliárd prímtényezővel rendelkező és több mintmilliá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 darab prímtényezővel a sorolja : Az első Carmichael-számokprímtényezővel \ : A második Carmichael-számtö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ámpedig 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ásahatványai szerint \ : 1953-ban Knödel igazolta a következő felső korlátot : ahol konstans . Erdős Pálban javította a korlátot : 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 : A másik irányban Alford , Granville és Pomeranceben igazolták , hogy elegendően nagy X esetében 2005-ben ezt a korlátot Harman tovább javította -re , majd kicsivel fölé . A Carmichael-számok aszimptotikus eloszlásával több sejtés foglalkozik . Erdősos sejtése szerint kellően nagy X-re Carmichael-szám létezik . Pomeranceben megjavította Erdős heurisztikus érvelését a következőre : . Az eddig kiszámított adatok ( például a Pinch általig 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 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 . Azrendű Carmichael-számok egyszerűen a közönséges Carmichael-számok . Másodrendű Carmichael-szám Howe szerint a · · · · · ·· egy másodrendű Carmichael-szám . A szorzat értéke \ . 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 egyetlenad vagy magasabb rendű Carmichael-szám sem ismeretes . Jegyzetek További információk Alice és Bob - rész : Alice és Bob prímszámok után nyomoz Alice és Bob - rész : Alice és Bob komolyabb fegyverekhez nyúl Alice és Bob - 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 MathPages : " The Dullness of Final Answers Modular Arithmetic Nevezetes számsorozatok Álprímek Moduláris aritmetika