Carmichaelin luku

Wikipedia

Tätä artikkelia tai artikkelin osaa on pyydetty parannettavaksi.
Voit auttaa Wikipediaa parantamalla artikkelia. Lisää tietoa saattaa olla keskustelusivulla.

Carmichaelin luvuksi kutsutaan lukuteoriassa sellaista yhdistettyä lukua n, joka toteuttaa ehdon

a^{n-1}\equiv 1\quad (mod\quad n)

jokaisella kokonaisluvulla a, kun a:n ja n:n suurin yhteinen tekijä on 1, toisin sanoen kun a ei ole jaollinen luvulla n.

Fermat'n pienen lauseen mukaan ainakin kaikki alkuluvut toteuttavat tämän ehdon. Jos siis jollakin luvulla n löydetään jokin sellainen luku a, että ehto ei toteudu, niin luvun n on oltava yhdistetty luku. On kuitenkin olemassa myös sellaisia yhdistettyjä lukuja, jotka toteuttavat ehdon kaikilla luvuilla a. Näitä lukuja siis sanotaan Carmichaelin luvuiksi. [1]

Lukua 100 000 pienemmät Carmichaelin luvut ovat 561, 1105, 1729, 2465, 2821, 6601, 8911, 10 585, 15 841, 29 341, 41 041, 46 657, 52 633, 62 745, 63 973 ja 75 361.

Pienet Carmichaelin luvut ovat harvinaisia. Esimerkiksi lukua 2,5 · 1010 pienempiä on vain 2163, ja lukua 1016 pienempiä 246 683. Pitkään olikin avoimena ongelma, onko Carmichaelin lukuja olemassa vain äärellinen määrä. Vuonna 1994 matemaatikot William Alford, Andrew Granville ja Carl Pomerance onnistuivat vihdoin todistamaan, että Carmichaelin lukuja on äärettömän paljon. [2]

Carmichaelin luvut ovat nimetty amerikkalaisen matemaatikon, Robert Carmichaelin mukaan.

[muokkaa] Lähteet:

[1] Carmichael, R. D.: On composite numbers P which satisfy the Fermat congruence a^{P-1}\equiv 1\quad (mod\quad P). Am. Math. Month. 19, 1912, sivut 22–27.

[2] Alford, Granville ja Pomerance: There are infinitely many Carmichael numbers, Ann. of Math. 140(3), 1994, sivut 703–722.

Helppotajuinen johdatus Alfordin ja kumppaneiden todistukseen on Matti K. Sinisalo: Carmichaelin lukujen konstruktioista, Esitelmä lukuteorian päivillä 1995 (PDF).