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 (\mod 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 Sablon:Szám 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 ∣ 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 ∣ 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 ∣ 560, 10 ∣ 560, 16 ∣ 560$ .

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

1105 = 5 \cdot 13 \cdot 17 (4 ∣ 1104; 12 ∣ 1104; 16 ∣ 1104)

1729 = 7 \cdot 13 \cdot 19 (6 ∣ 1728; 12 ∣ 1728; 18 ∣ 1728)

2465 = 5 \cdot 17 \cdot 29 (4 ∣ 2464; 16 ∣ 2464; 28 ∣ 2464)

2821 = 7 \cdot 13 \cdot 31 (6 ∣ 2820; 12 ∣ 2820; 30 ∣ 2820)

6601 = 7 \cdot 23 \cdot 41 (6 ∣ 6600; 22 ∣ 6600; 40 ∣ 6600)

8911 = 7 \cdot 19 \cdot 67 (6 ∣ 8910; 18 ∣ 8910; 66 ∣ 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 $(6 k + 1) (12 k + 1) (18 k + 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, Sablon:Szám 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, \dots$ darab prímtényezővel a Sablon:OEIS 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 Sablon:OEIS:

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

$n$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
$C (1 0^{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 (- k_{1} {(\log X \log \log X)}^{\frac{1}{2}})

ahol $k_{1}$ konstans.

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

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

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 = 1 0^{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 $𝒪_{K}$ -ban lévő $𝔭$ nemnulla prímideál esetében $α^{N (𝔭)} \equiv α (mod 𝔭)$ bármely $𝒪_{K}$ -ben lévő $α$ -ra, ahol $N (𝔭)$ a $𝔭$ idál normája. (Ez a kis Fermat-tétel általánosítása, ami szerint $m^{p} \equiv m (mod p)$ minden m egészre, ha p prímszám.) Legyen egy $𝒪_{K}$ -ban lévő $𝔞$ nemnulla ideál Carmichael-ideál, ha nem prímideál és $α^{N (𝔞)} \equiv α (mod 𝔞)$ minden all $𝒪_{K}$ -ban lévő $α$ -ra, ahol $N (𝔞)$ 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 $𝔞 = (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 $𝒪_{K}$ Carmichael-ideáljainak leírása: bármely p prímszámra, ami K-ben teljesen felbomlik, a $p 𝒪_{K}$ főideál Carmichael-ideál. Mivel bármely számtestben végtelen sok prímszám bomlik fel teljesen, ezért $𝒪_{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 (\sum_{x = 1}^{n - 1} x^{n - 1}, n) = 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 Sablon:Szám.

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

Sablon:Reflist

További információk

Sablon:Természetes számok

↑ ^1,0 ^1,1 ^1,2 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} ∣ p_{j} - 1$ . De ha $n$ teljesíti a Korselt-kritériumokat, akkor $p_{j} - 1 ∣ n - 1$ , és az „osztója” reláció tranzitivitása miatt $p_{i} ∣ n - 1$ . De $p_{i}$ osztója $n$ -nek is, ami ellentmondás.
↑ Sablon:Cite journal
↑ Sablon:Cite journal
↑ Sablon:Cite journal
↑ ^7,0 ^7,1 Sablon:Cite journal
↑ Steven Hayman, Andrew Shallue: Constructing a ten billion factor Carmichael number Poster auf der ANTS X-Konferenz, San Diego, Juli 2012
↑ Sablon:Cite journal
↑ ^10,0 ^10,1 Sablon:Cite journal
↑ Sablon:Cite journal
↑ Sablon:Cite journal
↑ Everett W. Howe. "Higher-order Carmichael numbers." Mathematics of Computation 69 (2000), pp. 1711–1719.

[Pinch2007-1] 1,0 ^1,1 ^1,2 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} ∣ p_{j} - 1$ . De ha $n$ teljesíti a Korselt-kritériumokat, akkor $p_{j} - 1 ∣ n - 1$ , és az „osztója” reláció tranzitivitása miatt $p_{i} ∣ n - 1$ . De $p_{i}$ osztója $n$ -nek is, ami ellentmondás.

[Carmichael1910-4] Sablon:Cite journal

[Simerka1885-5] Sablon:Cite journal

[Chernick1939-6] Sablon:Cite journal

[Alford1994-7] 7,0 ^7,1 Sablon:Cite journal

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

[9] Sablon:Cite journal

[Erdős1956-10] 10,0 ^10,1 Sablon:Cite journal

[11] Sablon:Cite journal

[Pomerance1981-12] Sablon:Cite journal

[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]

Carmichael-számok

Tartalomjegyzék

Áttekintés

Korselt kritériuma

Felfedezésük

Tulajdonságaik

Prímtényezős felbontások

Eloszlásuk

Általánosítások

Magasabbrendű Carmichael-számok

Másodrendű Carmichael-szám

Tulajdonságaik

Jegyzetek

További információk

Navigációs menü

Carmichael-számok

Áttekintés

Korselt kritériuma

Felfedezésük

Tulajdonságaik

Prímtényezős felbontások

Eloszlásuk

Általánosítások

Magasabbrendű Carmichael-számok

Másodrendű Carmichael-szám

Tulajdonságaik

Jegyzetek

További információk

Navigációs menü

Keresés