Anzahl der Primitivwurzeln modulo n

Dieser Rechner prüft, ob ein Modul Primitivwurzeln besitzt, und gibt gegebenenfalls deren exakte Anzahl zurück. Das Ergebnis ist die Eulersche Phi-Funktion der Eulerschen Phi-Funktion des Moduls, geschrieben als phi(phi(n)). Der Rechner berücksichtigt die vollständige Familie zulässiger Module und setzt nicht voraus, dass die Eingabe eine Primzahl ist. Gehört das Modul zu einer Klasse ohne Primitivwurzeln, erhalten Sie eine klare Eingabefehlermeldung statt einer irreführenden Null.

Was die Anzahl bedeutet

Eine Primitivwurzel modulo n ist eine Restklasse, deren aufeinanderfolgende Potenzen sämtliche invertierbaren Restklassen modulo n erzeugen. In der Gruppentheorie ist sie ein Erzeuger der multiplikativen Gruppe der ganzen Zahlen modulo n. Dieses Werkzeug beantwortet eine genaue Frage: Wie viele verschiedene Restklassen erzeugen diese Gruppe?

Es listet die Erzeuger nicht auf und sucht auch nicht nach dem kleinsten. Existiert eine Primitivwurzel, dann ist die multiplikative Gruppe zyklisch und besitzt phi(n) Elemente. Eine zyklische Gruppe der Ordnung phi(n) hat genau phi(phi(n)) Erzeuger; diesen Wert gibt der Rechner zurück.

Modulo 18 bilden die invertierbaren Reste beispielsweise eine zyklische Gruppe der Ordnung 6. Da phi(6) gleich 2 ist, gibt es zwei Primitivwurzeln. Die Anzahl bezieht sich auf Restklassen modulo n und nicht auf beliebige ganzzahlige Vertreter: Werte, die sich um ein Vielfaches von n unterscheiden, beschreiben dieselbe Wurzel.

Daher eignet sich das Ergebnis für Beweise, Aufgaben und Algorithmen, bei denen die Größe der Erzeugermenge wichtiger ist als die einzelnen Elemente.

Welche Module Primitivwurzeln besitzen

Nicht jedes positive Modul besitzt Primitivwurzeln. Nach der vollständigen Klassifikation existieren sie genau dann, wenn n gleich 2, 4, einer ungeraden Primzahlpotenz p^k oder dem Doppelten einer ungeraden Primzahlpotenz 2p^k ist. Der Rechner faktorisiert das eingegebene Modul und wendet diesen Satz an, bevor er zählt.

Das ist entscheidend, weil die ungeprüfte Auswertung von phi(phi(n)) für ein unzulässiges Modul eine positive Zahl liefert, obwohl keine Erzeuger vorhanden sind. So gilt phi(8) gleich 4 und phi(4) gleich 2, doch modulo 8 gibt es keine Primitivwurzel; das Ergebnis 2 wäre mathematisch falsch. Deshalb weist diese Funktion ein solches Modul ausdrücklich zurück.

Primzahlmodule größer als zwei sind als Sonderfall p^1 enthalten. Auch zusammengesetzte Beispiele wie 9, 14, 18 und 25 sind zulässig, während 8, 12, 15 und 20 es nicht sind. Klassifikation und Zählformel bleiben getrennt, damit die Ausgabe stets eine tatsächlich vorhandene Menge von Primitivwurzeln beschreibt.

Ergebnis verwenden und richtig deuten

Geben Sie eine ganze Zahl n zwischen 2 und 1,000,000,000,000 ein. Die Eingabe muss eine numerische Ganzzahl sein, keine Dezimalzeichenfolge, kein Bruch, keine wissenschaftliche Näherung, kein negativer Wert und keine unsichere JavaScript-Ganzzahl. Die Obergrenze hält die Faktorisierung endlich und planbar und deckt dennoch viele praktische sowie schulische Berechnungen ab.

Intern ermittelt der Algorithmus die Primzahlpotenzstruktur durch deterministische Probedivision, prüft den Existenzsatz, berechnet phi(n) aus den verschiedenen Primfaktoren und anschließend phi(phi(n)). Er verwendet weder Netzwerkzugriffe noch Zufallssuche; gleiche Eingaben liefern daher immer gleiche Ausgaben.