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 ovat nimetty amerikkalaisen matemaatikon Robert Carmichaelin mukaan.

[muokkaa] Jakauma

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

Carmichaelin lukuja on äärettömästi, nimittäin

$C(x) > x^{\frac {2}{7}}$ kaikille tarpeeksi suurille luvuille x.

Tämän alarajan Carmichaelin lukujen määrälle löysivät matemaatikot William Alford, Andrew Granville ja Carl Pomerance vuonna 1994.

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:

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

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

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