Carmichael-Zahl

Eine natürliche Zahl heißt Carmichael-Zahl, benannt nach dem Mathematiker Robert Daniel Carmichael, wenn sie eine fermatsche Pseudoprimzahl bezüglich aller zu ihr teilerfremden Basen ist. Carmichael-Zahlen spielen eine Rolle bei der Analyse von Primzahltests.

Jede Carmichael-Zahl ist quadratfrei und das Produkt mindestens dreier Primzahlen. Die kleinste Carmichael-Zahl ist die Zahl 561 = 3·11·17. Im Jahr 1994 bewiesen Carl Pomerance, W. R. Alford und Andrew Granville die Existenz unendlich vieler Carmichael-Zahlen.[1]

Inhaltsverzeichnis

Einleitung

Es ist einfach, eine Carmichael-Zahl zu erkennen, wenn man ihre Primfaktorzerlegung kennt. Dies ist dem Satz von Korselt zu verdanken (siehe weiter unten). Es ist auch relativ einfach, Carmichael-Zahlen zu erzeugen, zumal Algorithmen wie der nach J. Chernick existieren. Problematisch ist es aber – gerade bei großen Zahlen – zu erkennen, ob es sich bei einer Zahl um eine Carmichael-Zahl handelt. Diese Schwierigkeit haben die Carmichael-Zahlen mit den Primzahlen gemeinsam, denn entweder man führt eine Faktorisierung durch, oder man wendet den kleinen fermatschen Satz auf die Zahl an, wobei man für die Basen, die nicht auf eine Primalität weisen und die bei Primzahlen nicht vorkommen, auf Teilbarkeit testen muss.

Definition

Definition
Eine zusammengesetzte natürliche Zahl n heißt Carmichael-Zahl, falls für alle zu n teilerfremden Zahlen a die folgende Kongruenz erfüllt ist:

 a^{n-1} \equiv 1 \mod n .


Beispiel
Wie erwähnt, ist 561 = 3·11·17 die kleinste Carmichael-Zahl. Für alle Basen a, die keinen Primfaktor mit 561 gemeinsam haben, gilt nämlich a560 ≡ 1 mod 561.

561 ist durch 3, 11, 17, 33, 51 und 187 teilbar. Für diese Teiler gilt die Kongruenz jedoch nicht: 3560 ≡ 375 mod 561, 11560 ≡ 154 mod 561, 17560 ≡ 34 mod 561, usw.

Satz von Korselt

Bereits im Jahr 1899 bewies Alwin Reinhold Korselt folgenden Satz:

Eine natürliche Zahl n ist genau dann eine Carmichael-Zahl, wenn sie quadratfrei ist und für alle ihre Primteiler p gilt, dass p - 1 die Zahl n - 1 teilt.

Verschärfung
Aufgrund der Identität n-1 = n/p - 1 + (p-1)·n/p gilt für jeden Primteiler p einer natürlichen Zahl n:

n-1n/p - 1 mod p-1.

Somit lässt sich der zweite Teil von Korselts Satz auch formulieren als: Eine Zahl n ist genau dann eine Carmichael-Zahl, wenn für jeden ihrer Primteiler gilt: p-1 teilt n/p - 1.

Carmichael hat dann 1910 mit 561 die erste Zahl gefunden, die den Eigenschaften des Theorems von Korselt entspricht.

Die Folge der Carmichael-Zahlen

Carmichael-Zahlen haben mindestens drei Primfaktoren. Wie in der Einleitung erwähnt weiß man seit 1994, dass es unendlich viele Carmichael-Zahlen gibt. Die Folge der Carmichael-Zahlen beginnt so:

561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, … (Folge A002997 in OEIS)

Die kleinste Carmichael-Zahl mit 4 Primfaktoren ist 41041 = 7·11·13·41.

Erzeugung von Carmichael-Zahlen

Methode von Chernick

J. Chernick fand 1939 ein relativ einfaches System, um Carmichael-Zahlen zu konstruieren:

Falls die drei Zahlen 6m + 1, 12m + 1 und 18m + 1 Primzahlen sind, so ist ihr Produkt (6m + 1)(12m + 1)(18m + 1) eine Carmichael-Zahl.[2]

Beispielsweise hat 1729 = 7·13·19 diese Struktur. Interessant ist, dass die Carmichael-Zahl 172081 = 31·61·91 die Bedingung „fast erfüllt“: 91 ist nicht prim, aber fermatsche Pseudoprimzahl zur Basis 3.

Methode von Michon

Gérard P. Michon fand eine ähnliche Methode, um Carmichael-Zahlen zu konstruieren:

Wenn m ≡ 326 mod 616 und die drei Zahlen 7m + 1, 8m + 1 und 11m + 1 Primzahlen sind, so ist ihr Produkt (7m+1)·(8m+1)·(11m+1) eine Carmichael-Zahl.

m muss dann durch 3 teilbar sein, da sonst einer der drei Faktoren durch 3 teilbar ist.
Beispiel: für m = 24966 sind die drei Zahlen 174763, 199729 und 274627 prim und ihr Produkt ist eine Carmichael-Zahl.
Eine mit dieser Methode erzeugte Carmichael-Zahl mit 1000 Stellen ist

(12936*10329 - 59827428149)·(14784*10329 - 68374203599)·(20328*10329 - 94014529949).

Asymptotische Anzahl

Paul Erdös vermutete bereits 1956, dass es unendlich viele Carmichael-Zahlen gibt, und dass für ihre Anzahl C(x) unterhalb einer Schranke x kein Exponent a < 1 existiert mit C(x) < xa bei beliebig großem x.[3]

Der Beweis von Alford/Granville/Pomerance liefert die untere Abschätzung der Anzahlfunktion C(x) > x2 / 7 für alle hinreichend großen x. Dieses Ergebnis wurde im Jahr 2005 verbessert zu C(x) > x0.33 für hinreichend große x.[4] Rechnungen bis x = 1015 legen ein Wachstum mit der unteren Abschätzung x1 / 3 nahe, so dass Daniel Shanks überzeugt war, x1 / 2 sei eine sehr sichere obere Abschätzung für die Anzahlfunktion. Er ließ sich jedoch durch Diskussion mit den genannten Autoren davon überzeugen, dass die Vermutung von Erdös der wahren Asymptotik entsprechen könnte. Im Jahre 2002 publizierten Granville und Pomerance eine Analyse der Verteilung der Carmichael-Zahlen, die das Argument von Erdös unterstützt.[5]

Quellen

  1. W. R. Alford, A. Granville, C. Pomerance: There are Infinitely Many Carmichael Numbers, Ann. Math. 139, 703-722, 1994.
  2. Zum (einfachen) Beweis siehe Eric W. Weisstein: "Carmichael number" (→ Weblinks).
  3. Siehe Crandall, Pomerance: Prime Numbers, S. 122
  4. Glyn Harman: On the number of Carmichael numbers up to x, Bull. London Math. Soc. 37, 641–650, 2005.
  5. A. Granville, C. Pomerance: Two contradictory conjectures concerning Carmichael numbers, Math. Comp. 71, 883–908, 2002, online

Literatur

Siehe auch

Weblinks


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Lucas-Carmichael-Zahl — Eine Lucas Carmichael Zahl ist eine zusammengesetzte, natürliche Zahl, die eine ähnliche Bedingung wie eine Carmichael Zahl erfüllt. Inhaltsverzeichnis 1 Definition 2 Beispiel 3 Die kleinsten Lucas Carmichael Zahlen 4 …   Deutsch Wikipedia

  • Carmichael — ist der Familienname folgender Personen: Albert A. Carmichael (1895–1952), US amerikanischer Rechtsanwalt, Politiker Alexander Carmichael (1832 1912), schottischer Autor und Volkskundler Archibald Hill Carmichael (1864–1947), US amerikanischer… …   Deutsch Wikipedia

  • Carmichael-Funktion — Die Carmichael Funktion aus dem Bereich der Mathematik ist eine zahlentheoretische Funktion, die zu jeder natürlichen Zahl n, das kleinste m = λ(n) bestimmt, so dass: für jedes a gilt, das teilerfremd zu n ist. In gruppentheoretischer Sprache ist …   Deutsch Wikipedia

  • Giuga-Zahl — Die Giuga Zahlen sind nach dem Mathematiker Giuseppe Giuga benannte natürliche Zahlen mit speziellen Eigenschaften. Sie sind im Zusammenhang mit einer von ihm vermuteten Charakterisierung der Primzahlen von Bedeutung. Verwandt zu den Giuga Zahlen …   Deutsch Wikipedia

  • Robert D. Carmichael — Robert Daniel Carmichael (* 1. März 1879 in Goodwater, Alabama, USA; † 1967) war ein US amerikanischer Mathematiker. Leben Carmichael gilt als begabter und vielseitiger Mathematiker. Der Satz von Carmichael stammt aus dem Jahr 1910. Parallel… …   Deutsch Wikipedia

  • Fröhliche Zahl — Eine fröhliche Zahl ist eine natürliche Zahl, die als Ausgangswert für eine bestimmte Iterationsvorschrift nach endlich vielen Iterationsschritten zu dem Zahlenwert 1 führt, ähnlich dem Collatz Problem. Inhaltsverzeichnis 1 Definition 2 Beispiele …   Deutsch Wikipedia

  • Satz von Carmichael — Der Satz von Carmichael (nach Robert Daniel Carmichael, 1910) ist eine Aussage über eine spezielle Klasse von einfach zu programmierenden Zufallszahlengeneratoren und liefert Kriterien, die dabei helfen, Generatoren von möglichst guter Qualität… …   Deutsch Wikipedia

  • Besondere Zahlen — sind zum einen Zahlen, die im Sinne der Zahlentheorie eine oder mehrere auffällige Eigenschaften besitzen. Außerdem haben viele Zahlen eine besondere Bedeutung in der Mathematik und/oder in Bezug auf die reale Welt. Diese letzteren Zahlen werden… …   Deutsch Wikipedia

  • Carmichaelzahl — Eine Carmichael Zahl, benannt nach dem Mathematiker Robert Daniel Carmichael, ist eine spezielle eulersche Pseudoprimzahl, für die gilt: Eine Carmichael Zahl n ist pseudoprim zu allen Basen, die keine gemeinsamen Primfaktoren mit n haben. Jede… …   Deutsch Wikipedia

  • Korselts Theorem — Eine Carmichael Zahl, benannt nach dem Mathematiker Robert Daniel Carmichael, ist eine spezielle eulersche Pseudoprimzahl, für die gilt: Eine Carmichael Zahl n ist pseudoprim zu allen Basen, die keine gemeinsamen Primfaktoren mit n haben. Jede… …   Deutsch Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.