Alle Primitivwurzeln modulo n

Er prüft zunächst, ob der Modulus zu einer Familie mit Primitivwurzeln gehört, berechnet dann Eulers Phi-Funktion, findet einen Generator und leitet alle weiteren ab. Die Antwort enthält Modulus, Phi-Wert, Anzahl und vollständige Wurzelliste. Werte unter zwei und Moduln ohne Primitivwurzel führen zu einer klaren Fehlermeldung. Dieselbe deterministische Arithmetik unterstützt schnelle Prüfungen sowie reproduzierbare API-Automatisierung für $0.002 je erfolgreicher Anfrage.

Was die vollständige Liste der Primitivwurzeln bedeutet

Eine Primitivwurzel modulo n ist ein Rest, dessen aufeinanderfolgende Potenzen jede invertierbare Restklasse modulo n erzeugen. Entscheidend ist „jede“: Eine Zahl kann zu n teilerfremd sein und dennoch nur eine echte Untergruppe durchlaufen. Eine Einheit zu sein ist daher notwendig, aber nicht hinreichend. Diese Fähigkeit gibt alle positiven Vertreter zwischen 1 und n minus 1 zurück, deren multiplikative Ordnung genau phi(n) ist. Beim Modulus 14 hat die Einheitengruppe beispielsweise sechs Elemente, während die vollständige Generatormenge zwei Reste enthält. Die Antwort nennt n, Eulers Phi-Wert, die Anzahl der Primitivwurzeln und das numerisch sortierte Array primitive_roots. Die Anzahl dient als Kontrolle: Existieren Primitivwurzeln, so gibt es phi(phi(n)) davon. Der Sonderfall 2 besitzt korrekt die einzige Wurzel 1. Ein Modulus ohne Generator der gesamten Einheitengruppe wird ausdrücklich abgelehnt; eine leere Liste würde fälschlich verschleiern, dass die Gruppe nicht zyklisch ist.

Wie Existenz und einzelne Generatoren geprüft werden

Primitivwurzeln existieren nicht für jeden Modulus. Der Klassifikationssatz besagt, dass die multiplikative Gruppe modulo n genau dann zyklisch ist, wenn n gleich 2, 4, einer ungeraden Primzahlpotenz oder dem Doppelten einer ungeraden Primzahlpotenz ist. Der Rechner faktorisiert n und prüft diese Strukturbedingung vor der Suche. Für einen zulässigen Modulus berechnet er phi(n), faktorisiert die Gruppenordnung und testet mögliche Einheiten mit modularer Exponentiation. Ein Kandidat g besitzt genau dann die volle Ordnung phi(n), wenn für jeden verschiedenen Primteiler q von phi(n) der Wert g hoch phi(n) geteilt durch q nicht kongruent zu 1 modulo n ist. Nach dem Fund eines solchen g sind sämtliche Primitivwurzeln Potenzen g hoch k, wobei k zu phi(n) teilerfremd ist. Die Implementierung zählt diese Exponenten auf, berechnet exakte Reste und sortiert das Ergebnis. Zufall, externe Tabellen, Netzwerk und aktuelle Zeit werden nicht verwendet; gleiche Eingaben ergeben stets denselben Zahleninhalt.

Einsatz des Ergebnisses in Mathematik und Software

Vollständige Generatorlisten helfen, wenn eine Aufgabe mehr als die kleinste Primitivwurzel verlangt. Lernende können die ausgegebenen Reste mit selbst erstellten Potenztabellen vergleichen und nachvollziehen, warum die Generatoranzahl phi(phi(n)) beträgt. Lehrkräfte können Lösungsschlüssel mit allen gültigen Antworten erstellen. Softwareentwickler können Testdaten für Routinen zur multiplikativen Ordnung erzeugen, Aufzählungscode prüfen oder anhand einer separaten Anwendungsregel zwischen mehreren Generatoren wählen. Auch Fehlerfälle sind lehrreich: Die Moduln 8 und 15 zeigen, dass viele zusammengesetzte Zahlen trotz zahlreicher invertierbarer Reste keine zyklische Einheitengruppe besitzen. Die Eingabe ist auf 10,000 begrenzt, weil die verlangte Ausgabe vollständig ist und viele Wurzeln enthalten kann; dadurch bleiben Darstellung, API-Größe und Laufzeit vorhersehbar. Geben Sie n als ganze Zahl oder einfache dezimale Zeichenfolge an. Erfolgreiche Anfragen kosten $0.002; nicht unterstützte oder fehlerhafte Eingaben werden eindeutig bezeichnet.