Carmichael-getal

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

In de getaltheorie, een deelgebied van de wiskunde, is een Carmichael-getal een samengestelde positief geheel getal n dat voldoet aan de congruentie

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

voor alle gehele getallen b die relatief priem zijn met n (zie modulair rekenen). Ze zijn genoemd naar Robert Carmichael. De Carmichael- getallen zijn de Knödel-getallen K1.

Overzicht[bewerken]

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

Carmichael-getallen zijn belangrijk omdat ze slagen voor de priemtest van Fermat, terwijl zij geen werkelijke priemgetallen zijn. Aangezien Carmichael-getallen bestaan, kan men dus niet op deze priemgetaltest vertrouwen dat een bepaald getal een priemgetal is, hoewel deze priemgetaltest nog steeds kan worden gebruikt om te bewijzen dat een getal een samengesteld getal is.

Het kleinste Carmichael-getal is 561 (= 3 · 11 · 17). Er zijn oneindig veel Carmichael-getallen; Alford, Granville en Pomerance bewezen dat in 1994.[1] Naarmate de getallen groter worden, worden Carmichael-getallen zeer zeldzaam. Er zijn bijvoorbeeld 1.401.644 Carmichael-getallen tussen 1 en 1018 (ongeveer een op de 700 miljard getallen.)[2]. Dit maakt priemgetallentests op basis van de kleine stelling van Fermat enigszins riskant in vergelijking met anderen priemgetallentests als de Solovay-Strassen-priemgetaltest.

Een alternatieve en gelijkwaardige definitie van Carmichael-getallen wordt gegeven door het criterium van Korselt.

Referenties[bewerken]

  • (en) Löh, Günter en Niebuhr, Wolfgang, (1996). A new algorithm for constructing large Carmichael numbers(pdf)
  • (fr) Korselt, (1899). Problème chinois. L'intermédiaire des mathématiciens, 6, 142–143.
  • (en) Carmichael, R. D., (1912) On composite numbers P which satisfy the Fermat congruence a^{P-1}\equiv 1\bmod P. Am. Math. Month. 19 22–27.

Voetnoten[bewerken]

  1. W. R. Alford, A. Granville, C. Pomerance: "There are Infinitely Many Carmichael Numbers". Ann. Math. 139, 703–722 (1994).
  2. (en) Richard Pinch, "De Carmichael-getallen tot 10 18", april 2006 (op basis van zijn eerdere werk [1] zie hier 1 zie hier 2).

Externe links[bewerken]