Carmichaelova števila so v teoriji števil sestavljena pozitivna cela števila n za katera velja kongruenca:
za vsa cela števila a, ki so n tuja (glej modularna aritmetika). Imenujejo se po ameriškem matematiku Robertu Danielu Carmichaelu, ki jih je med prvimi raziskoval. Carmichaelova števila so Knödlova števila K1. Fermatov mali izrek pravi, da imajo vsa praštevila to zadnjo značilnost. V tem pogledu so Carmichaelova števila podobna praštevilom. Takšna števila se imenujejo Fermatova psevdopraštevila. Carmichaelova števila se včasih imenujejo absolutna Fermatova psevdopraštevila.
Carmichaelova števila so pomemben razred števil, ker lahko preslepijo Fermatov preskus praštevilskosti, ker so navidezno praštevila. Ker Carmichaelova števila obstajajo, se na ta preskus praštevilskosti ni moč zanesti, čeprav se lahko uporablja za ugotavljanje sestavljenosti števil.
Ko vrednost števil narašča, so Carmichaelova števila vse redkejša. Med 1 in 1018 je na primer 1.401.644 Carmichaelovih števil (približno eno na vsako 700 milijardto število.)[1] Zaradi tega so preskusi praštevilskosti na podlagi Fermatovega malega izreka bolj tvegani v primerjavi z drugimi, kot je na primer Solovay-Strassenov preskus praštevilskosti.
S Korseltovim izrekom iz 1899 se lahko poda drugo in enakovredno definicijo Carmichaelovih števil. Izrek pravi, da je pozitivno celo število n Carmichaelovo število tedaj in le tedaj, kadar za n, ki ni deljiv s kvadratom in ni praštevilo, in za vse njegove delitelje p velja p - 1 deli n - 1, kar se zapiše kot p - 1 | n - 1. To kaže, da so Carmichaelova števila vedno liha.
Korselt je bil prvi, ki je opazil te značilnosti, vendar ni našel nobenega primera. Leta 1910 je Carmichael našel prva in najmanjše takšno število 561. Zaradi tega se števila imenujejo po njem.
Da je 561 Carcmihaelovo število, se lahko preveri kar s Korseltovim izrekom. 561 = 3 · 11 · 17 ni deljivo s kvadratom in 2 | 560, 10 | 560 ter 16 | 560.
Prva Carmichaelova števila so (OEIS A002997):
| n
|
|
|
| 1 |
561 = 3 · 11 · 17
|
(2 | 560, 10 | 560, 16 | 560)
|
| 2 |
1105 = 5 · 13 · 17
|
(4 | 1104, 12 | 1104, 16 | 1104)
|
| 3 |
1729 = 7 · 13 · 19
|
(6 | 1728, 12 | 1728, 18 | 1728)
|
| 4 |
2465 = 5 · 17 · 29
|
(4 | 2464, 16 | 2464, 28 | 2464)
|
| 5 |
2821 = 7 · 13 · 31
|
(6 | 2820, 12 | 2820, 30 | 2820)
|
| 6 |
6601 = 7 · 23 · 41
|
(6 | 6600, 22 | 6600, 40 | 6600)
|
| 7 |
8911 = 7 · 19 · 67
|
(6 | 8910, 18 | 8910, 66 | 8910)
|
J. Chernik je leta 1939 dokazal izrek, s katerim se lahko skonstruira podmnožico Carmichaelovih števil. Število oblike (6k + 1)(12k + 1)(18k + 1) je Carmichaelovo, če so vsi njegovi trije faktorji praštevila.
Paul Erdős je hevristično domneval, da obstaja neskončno mnogo Carmichaelovih števil. Leta 1994 so William Alford, Andrew Granville in Carl Pomerance pokazali, da res obstaja neskončno mnogo Carmichaelovih števil. Posebej so pokazali, da za dovolj velik n obstaja vsaj n2/7 Carmichaelovih števil med 1 in n.[2] Richard G. E. Pinch je podal in tudi dokazal zgornjo mejo za C(n), število Carmichaelovih števil manjše od n.
Značilnosti
Carmichaelova števila imajo vsaj tri prave delitelje. Prva Carmichaelova števila n s k = 3, 4, 5, ... faktorji so
(OEIS A006931):
| k
|
n
|
| 3 |
561 = 3 · 11 · 17
|
| 4
|
41041 = 7 · 11 · 13 · 41
|
| 5
|
825265 = 5 · 7 · 17 · 19 · 73
|
| 6
|
321197185 = 5 · 19 · 23 · 29 · 37 · 137
|
| 7
|
5394826801 = 7 · 13 · 17 · 23 · 31 · 67 · 73
|
| 8
|
232250619601 = 7 · 11 · 13 · 17 · 31 · 37 · 73 · 163
|
| 9
|
9746347772161 = 7 · 11 · 13 · 17 · 19 · 31 · 37 · 41 · 641
|
Möbiusova funkcija μ(n) teh števil izmenično zavzema vrednosti -1 in 1. 41041 je tako prvo Carmichaelovo število za katerega velja μ(n) = 1. Prva Carmichaelova števila z natančno 4 faktorji so (OEIS A074379):
| n
|
|
| 1
|
41041 = 7 · 11 · 13 · 41
|
| 2
|
62745 = 3 · 5 · 47 · 89
|
| 3
|
63973 = 7 · 13 · 19 · 37
|
| 4
|
75361 = 11 · 13 · 17 · 31
|
| 5
|
101101 = 7 · 11 · 13 · 101
|
| 6
|
126217 = 7 · 13 · 19 · 73
|
| 7
|
172081 = 7 · 13 · 31 · 61
|
| 8
|
188461 = 7 · 13 · 19 · 109
|
| 9
|
278545 = 5 · 17 · 29 · 113
|
| 10
|
340561 = 13 · 17 · 23 · 67
|
Sklici
Viri
