Brontekst bekijken van Carmichael-getal

Een '''Carmichael-getal''' is een [[samengesteld getal]] <math>n</math>, dat voor alle getallen <math>b</math>, met <math>1 < b < n</math>, die met <math>n</math> [[relatief priem]] zijn, aan de volgende [[Congruentie (rekenkunde)|congruentie]] voldoet:
: <math>b^{n-1} \equiv 1 \mod{n}</math>.
Ze zijn naar de Amerikaanse wiskundige Robert Carmichael genoemd.

De [[kleine stelling van Fermat]] stelt dat alle [[priemgetal]]len de bovenstaande eigenschap hebben. In deze zin zijn Carmichael-getallen vergelijkbaar met priemgetallen, zij worden Fermat-pseudopriemgetallen genoemd. De Carmichael-getallen worden ook wel absolute Fermat-getallen genoemd.

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 [[Carl Pomerance|Pomerance]] bewezen in 1994 dat er oneindig veel Carmichael-getallen zijn.<ref>{{en}} {{aut|WR Alford, A Granville, C Pomerance}}in [[Annals of Mathematics]]. There are Infinitely Many Carmichael Numbers, 1994. vol 139, blz 703–722.</ref> Naarmate de getallen groter worden, worden Carmichael-getallen zeer zeldzaam. Er zijn bijvoorbeeld {{nowrap|1.401.644}} Carmichael-getallen tussen 1 en 10<sup>18</sup>, dat is ongeveer één op de 700&nbsp;miljard getallen.<ref>{{en}} {{aut|R Pinch}}, [https://arxiv.org/abs/math/0604376 The Carmichael numbers up to 10<sup>18</sup>] in 2006 en eerder [https://arxiv.org/abs/math.NT/0504119 The Carmichael numbers up to 10<sup>17</sup>] in 2005 en [https://arxiv.org/abs/math.NT/9803082 The Carmichael numbers up to 10<sup>16</sup>] in 1998. [https://web.archive.org/web/20230423174647/https://arxiv.org/abs/math/0604376 Gearchiveerd] op 23 april 2023.</ref>

De Carmichael-getallen zijn de [[Knödel-getal]]len <math>K_1</math>.

Het criterium van Korselt geeft een anders geformuleerde definitie van Carmichael-getallen.

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

561 kan door 3, 11, 17, 33, 51 en 187 worden gedeeld. De congruentie geldt voor deze getallen niet: {{nowrap|3<sup>560</sup> ≡ 375 mod 561}}, {{nowrap|11<sup>560</sup> ≡ 154 mod 561}}, {{nowrap|17<sup>560</sup> ≡ 34 mod 561}} enzovoort, maar voor alle andere getallen wel.

== Literatuur ==
* {{en}} {{aut|G Löh}} en {{aut|W Niebuhr}} in [[Mathematics of Computation]], [http://www.ams.org/mcom/1996-65-214/S0025-5718-96-00692-8/S0025-5718-96-00692-8.pdf A new algorithm for constructing large Carmichael numbers], 1996. {{pdf}}
* {{fr}} {{aut|Korselt}} in L'intermédiaire des mathématiciens. Problème chinois, 1899. vol 6, blz 142–143.
* {{en}} {{aut|RD Carmichael}} in American Mathematical Monthly. On composite numbers P which satisfy the Fermat congruence {{math|a<sup>P-1</sup> ≡ 1 mod P}}. 1912, vol 19, blz 22–27.

== Verwijzingen en voetnoten ==
* {{Link OEIS|id=A002997}}
* {{de}} [[Wikibooks]]. [https://de.wikibooks.org/wiki/Pseudoprimzahlen:_Tabelle_Carmichael-Zahlen Pseudoprimzahlen: Tabelle Carmichael-Zahlen].
* {{en}} [[MathWorld]]. [http://mathworld.wolfram.com/CarmichaelNumber.html Carmichael Number]

{{Appendix|Voetnoten}}

[[Categorie:Getaltheorie]]
[[Categorie:Rij van gehele getallen]]