Carmichaelovo število
Iz Wikipedije, proste enciklopedije
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 modulska aritmetika). Imenujejo se po ameriškem matematiku Robertu Danielu Carmichaelu, ki jih je med prvimi raziskoval. Carmichaelova števila so Knödelova števila K1. Fermatov mali izrek pravi, da imajo vsa praštevila to zadnjo lastnost. 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. Me 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 lahko podamo drugo in enakovredno določitev 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 zapišemo kot p - 1 | n - 1. To nam kaže, da so Carmichaelova števila vedno liha.
Korselt je bil prvi, ki je opazil te lastnosti, 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, lahko preverimo 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 lahko skonstruiramo 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.
[uredi] Lastnosti
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 |
[uredi] Opombe
[uredi] Viri
- Pinch, Richard (april 2006). The Carmichael numbers up to 1018. “(na podlagi zgodnejšega dela [1][2][3]).”
- Alford, William; Granville, Andrew in Pomerance, Carl (1994). »There are Infinitely Many Carmichael Numbers« (PDF). Annals of Mathematics 139: str. 703-722.
