Carmichaelin luku

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

$a^{n-1}\equiv 1{\pmod {n}}\,$

jokaisella kokonaisluvulla a, kun a:n ja n:n suurin yhteinen tekijä on 1. Toisin sanoen Carmichaelin luvut ovat sellaisia kokonaislukuja, jotka ovat näennäisalkulukuja jokaisen kannan suhteen. Siitä seuraa se, että Carmichaelin lukua ei voi todeta yhdistetyksi luvuksi Fermat'n pienen lauseen avulla. Carmichaelin luvut on nimetty amerikkalaisen matemaatikon Robert Carmichaelin mukaan. Carmichaelin luvut ovat Knödelin luvut K₁.

Kymmenen pienintä Carmichaelin lukua ovat 561, 1 105, 1 729, 2 465, 2 821, 6 601, 8 911, 10 585, 15 841 ja 29 341.^[1]

Jakauma

Seuraavassa C(x) tarkoittaa lukua x pienempien Carmichaelin lukujen määrää.

Carmichaelin lukuja on äärettömästi, tämän todistivat ensimmäisenä matemaatikot William Alford, Andrew Granville ja Carl Pomerance vuonna 1994. He todistivat Carmichaelin lukujen määrälle seuraavan alarajan kaikille tarpeeksi suurille luvuille x ja kaikille $\epsilon >0$

$C(x)\geq x^{(\beta -\epsilon )}$ , missä $\beta =(1-(2{\sqrt {e}})^{-1}){\frac {5}{12}}=0,290306...>{\frac {2}{7}}$ eli $C(x)>x^{\frac {2}{7}}$ .

Vuonna 2005 Glyn Harman todisti vahvemman tuloksen $C(x)>x^{0,332}$ .

Paul Erdős todisti vuonna 1956 seuraavan ylärajan Carmichaelin lukujen määrälle: jollekin vakiolle k

C(x)<x\exp {\frac {-k\ln x\ln \ln \ln x}{\ln \ln x}}

Carmichaelin luvut ovat melko harvinaisia. Seuraavassa taulukossa on C(x):n arvo muutamille kymmenpotensseille:

n	C(10ⁿ)
3	1
4	7
5	16
6	43
7	105
8	255
9	646
10	1547
11	3605
12	8241
13	19279
14	44706
15	105212
16	246683
17	585355
18	1401644
19	3381806
20	8220777

Carmichaelin lukujen ominaisuuksia

Jokainen Carmichaelin luku on neliövapaa.

Pariton, neliövapaa yhdistetty luku n on Carmichaelin luku, jos ja vain jos n jakaa Bernoullin luvun $B_{n-1}$ nimittäjän.

Carmichaelin luvuilla on ainakin kolme alkutekijää.

Muotoa (6k + 1)(12k + 1)(18k + 1) olevat luvut ovat Carmichaelin lukuja, jos (6k + 1), (12k + 1) ja (18k + 1) ovat kaikki alkulukuja. Pienimmät sellaiset Carmichaelin luvut esiintyvät k:n arvoilla k = 1, 6, 35, 45, 51, 55, 56, 100, 121... (A046025 OEIS:ssä) ja ovat 1729, 294409, 56052361, 118901521... (A033502 OEIS:ssä).

Lähteet

Rosen, Kenneth H.: Elementary Number Theory and Its Applications, s. 155–156. Reading, Massachusetts: Addison-Wesley, 1984. ISBN 0-201-06561-4. (englanniksi)

Viitteet

Aiheesta muualla

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

[1]

Search