Carmichael-getal

Een Carmichael-getal is een samengesteld getal $n$ , dat voor alle getallen $b$ , met $1<b<n$ , die met $n$ relatief priem zijn, aan de volgende congruentie voldoet:

b^{n-1}\equiv 1\mod {n}

.

Ze zijn naar de Amerikaanse wiskundige Robert Carmichael genoemd. Alle priemgetallen voldoen volgens de kleine stelling van Fermat aan deze congruentie. Carmichael-getallen kunnen dus met priemgetallen worden vergeleken. Carmichael-getallen zijn belangrijk omdat ze aan de priemtest van Fermat voldoen, terwijl zij geen werkelijke priemgetallen zijn. Aangezien er carmichael-getallen bestaan, geeft deze priemgetaltest dus geen zekerheid dat een bepaald getal een priemgetal is. De priemtest van Fermat kan nog wel worden gebruikt om te bewijzen dat een getal een samengesteld getal is. Het kleinste carmichael-getal is 561. Alford, Granville en Pomerance bewezen in 1994 dat er oneindig veel carmichael-getallen zijn.^[1] Naarmate de getallen groter worden, worden carmichael-getallen zeldzaam. Er zijn bijvoorbeeld 1.401.644 carmichael-getallen tussen 1 en 10¹⁸, dat is ongeveer één op de 700 miljard getallen.^[2]

De carmichael-getallen zijn de Knödel-getallen $K_{1}$ . Het criterium van Korselt geeft een anders geformuleerde definitie van carmichael-getallen.^[3]

Voorbeeld

Neem $n=561=3\cdot 11\cdot 17$ , het kleinste Carmichael-getal. Dit getal voldoet aan de definitie dat voor alle $b$ , die onderling ondeelbaar met $n$ zijn dat $b^{n-1}\equiv 1\mod n$ .

561 kan door 3, 11, 17, 33, 51 en 187 worden gedeeld. De congruentie geldt voor deze getallen niet: 3⁵⁶⁰ ≡ 375 mod 561, 11⁵⁶⁰ ≡ 154 mod 561, 17⁵⁶⁰ ≡ 34 mod 561 enzovoort, maar voor alle andere getallen wel.

Literatuur

G Löh en W Niebuhr. A new algorithm for constructing large Carmichael numbers, 1996. gearchiveerd, in Mathematics of Computation
(fr) Korselt. Problème chinois, 1899. in L'intermédiaire des mathématiciens vol 6, blz 142–143
RD Carmichael. On composite numbers P which satisfy the Fermat congruence a^P-1 ≡ 1 mod P, 1912. in American Mathematical Monthly vol 19, blz 22–27

voetnoten

↑ WR Alford, A Granville en C Pomerance. There are Infinitely Many Carmichael Numbers, 1994. in Annals of Mathematics vol 139, blz 703–722
↑ R Pinch, The Carmichael numbers up to 10¹⁸ in 2006 en eerder The Carmichael numbers up to 10¹⁷ in 2005 en The Carmichael numbers up to 10¹⁶ in 1998. Gearchiveerd op 23 april 2023.
↑ K Conrad. Carmichael numbers and Korselt’s criterion.

websites

rij A002997 in OEIS
(de) Wikibooks. Pseudoprimzahlen: Tabelle Carmichael-Zahlen.
MathWorld. Carmichael Number

[1] WR Alford, A Granville en C Pomerance. There are Infinitely Many Carmichael Numbers, 1994. in Annals of Mathematics vol 139, blz 703–722

[2] R Pinch, The Carmichael numbers up to 10¹⁸ in 2006 en eerder The Carmichael numbers up to 10¹⁷ in 2005 en The Carmichael numbers up to 10¹⁶ in 1998. Gearchiveerd op 23 april 2023.

[3] K Conrad. Carmichael numbers and Korselt’s criterion.

[1]

[2]

[3]