Primitivwurzel-Rechner — Finden Sie die kleinste Primitivwurzel modulo n
Unser Primitivwurzel-Rechner findet die kleinste Primitivwurzel modulo n — eine Ganzzahl g, deren Potenzen g¹, g², g³, ... durch jede Einheit modulo n zyklieren, bevor sie sich wiederholen. Er prüft zunächst, ob überhaupt eine Primitivwurzel existiert (sie existieren nur für n = 1, 2, 4, pᵏ oder 2pᵏ für eine ungerade Primzahl p), und sucht dann mit der Eulerschen Phi-Funktion und ihrer Primfaktorzerlegung, um jeden Kandidaten effizient zu testen.
Kurzantwort
Eine Primitivwurzel g mod n erzeugt jede Einheit modulo n durch ihre Potenzen. Geben Sie unten n ein, um die kleinste zu finden, mit einer automatischen Prüfung, ob überhaupt eine Primitivwurzel existiert.
So verwenden Sie Primitivwurzel-Rechner — Finden Sie einen Generator mod n
- 1
Geben Sie eine positive ganze Zahl n ein (bis zu 1.000.000).
- 2
Klicken Sie auf 'Berechnen', um die kleinste Primitivwurzel modulo n zu finden, falls eine existiert.
- 3
Sehen Sie sich φ(n) und die bei der Überprüfung verwendeten Primfaktoren von φ(n) an.
Warum Primitivwurzel-Rechner — Finden Sie einen Generator mod n verwenden?
Eine Primitivwurzel modulo n ist ein Generator der Gruppe der zu n teilerfremden Ganzzahlen unter Multiplikation: Ihre aufeinanderfolgenden Potenzen erzeugen jede Einheit modulo n genau einmal, bevor sie in genau φ(n) Schritten zu 1 zurückkehren. Nicht jedes n hat eine — Primitivwurzeln existieren nur für n = 1, 2, 4, eine ungerade Primpotenz pᵏ oder das Doppelte einer ungeraden Primpotenz 2pᵏ, ein klassisches Ergebnis der Zahlentheorie. Dieser Rechner prüft diese Bedingung zuerst und verifiziert dann effizient jeden Kandidaten g, indem er g^(φ(n)/q) mod n für jeden Primfaktor q von φ(n) testet — g ist genau dann eine Primitivwurzel, wenn keiner dieser Tests gleich 1 ist.
Häufig gestellte Fragen
Ähnliche Tools
Eulersche Phi-Funktion Rechner — φ(n) Online
Berechnen Sie die Eulersche Phi-Funktion φ(n) — die Anzahl der zu n teilerfremden Ganzzahlen von 1 bis n — über Primfaktorzerlegung. Kostenloser Rechner mit vollständiger Faktorisierung.
Modularer Exponentiations-Rechner — Schnelles bᵉ mod m Online
Berechnen Sie bᵉ mod m für beliebig große Exponenten mit schneller Quadrieren-und-Multiplizieren-Exponentiation. Kostenloser Rechner mit BigInt-Präzision, essentiell für Kryptografie.
Modulares Multiplikatives Inverses — Löse ax ≡ 1 (mod m) Online
Finden Sie das modulare multiplikative Inverse von a modulo m mit dem erweiterten euklidischen Algorithmus. Kostenloser Rechner mit BigInt-Präzision und Existenzprüfung.
Gruppentheorie-Ordnungs-Rechner — Elementordnung in ℤₙ Online
Finde die Ordnung eines Elements in (ℤₙ, +) oder (ℤ/nℤ)ˣ, mit einer Teilbarkeitsprüfung nach dem Satz von Lagrange als Schritt gezeigt. Kostenloser Rechner, sofortige Ergebnisse.