Carmichaelovo število
Iz Wikipedije, proste enciklopedije
Pozitivno celo število n se imenuje Carmichaelovo število tedaj in le tedaj, če je n sestavljeno število in, če za vsa cela števila a, ki so n tuja, velja an - 1 je kongruentno 1 po modulu n (glej modulska aritmetika). 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 psevdopraštevila.
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.
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) |
Leta 1994 so William Alford, Andrew Granville in Carl Pomerance pokazali, da obstaja neskončno mnogo Carmichaelovih števil. 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:
| 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 |
