# Eulersche φ-Funktion-Rechner

Berechnet Eulers φ-Funktion — wie viele Zahlen in [1, n] teilerfremd zu n sind. Faktorisiert n per Probedivision und wertet exakt φ(n) = n · Π(1 − 1/p) aus (n ≤ 10¹²), optional mit den ersten 60 teilerfremden Zahlen und dem Euler-Theorem a^φ(n) ≡ 1 (mod n). Klassiker: φ(36) = 12 (36 = 2² × 3²); für Primzahlen gilt φ(n) = n − 1, z. B. φ(97) = 96.

> Kanonische Seite: https://elysiatools.com/de/tools/euler-totient-function

- **Kategorie:** Math & Numbers

- **Schlagwörter:** eulersche φ-funktion, teilerfremd, primfaktorzerlegung, euler-theorem, zahlentheorie

## Überblick

Der Eulersche φ-Funktion-Rechner berechnet die Anzahl aller ganzen Zahlen im Intervall [1, n], die teilerfremd zu n sind. Mittels Probedivision zerlegt das Tool Zahlen bis 10¹² in ihre Primfaktoren, berechnet den exakten Wert nach der Eulerschen Produktformel und liefert auf Wunsch eine Liste der ersten teilerfremden Zahlen sowie den passenden Ausdruck für den Satz von Euler.

## Eingaben

- **Zahl n** (text): Positive integer, 1 ≤ n ≤ 10¹² (trial-division factorization bound).
- **Detailgrad** (select)

## Wann verwenden

- Berechnung der Ordnung von multiplikativen Gruppen oder Exponenten in RSA-Kryptosystemen.
- Lösen zahlentheoretischer Übungsaufgaben und modulares Rechnen mittels Satz von Euler.
- Schnelle Überprüfung von Teilerfremdheit und Primfaktorzerlegungen ganzer Zahlen bis 10¹².

## Funktionsweise

- Geben Sie eine positive ganze Zahl n bis maximal 10¹² in das Eingabefeld ein.
- Wählen Sie den gewünschten Detailgrad: reine Berechnung von φ(n) oder zusätzliche Auflistung der ersten bis zu 60 teilerfremden Zahlen.
- Das Werkzeug ermittelt die Primfaktorzerlegung von n per Probedivision und wertet die Produktformel φ(n) = n · Π(1 − 1/p) aus.
- Die Ausgabe zeigt die Primfaktoren, die Schritt-für-Schritt-Formel, das Endergebnis sowie das zugehörige Euler-Theorem a^φ(n) ≡ 1 (mod n).

## Anwendungsfälle

- Bestimmung der Einheitenanzahl im Restklassenring Z/nZ für Algebra- und Zahlentheorievorlesungen.
- Schlüsselgenerierung und Modulberechnung in asymmetrischen Verschlüsselungsverfahren wie RSA.
- Identifikation von teilerfremden Elementen zur Bestimmung von Generatoren in zyklischen Gruppen.

## Häufig gestellte Fragen

### Was besagt die Eulersche φ-Funktion?

Sie gibt an, wie viele positive ganze Zahlen kleiner oder gleich n keinen gemeinsamen Teiler mit n außer 1 haben.

### Warum gilt für Primzahlen immer φ(p) = p − 1?

Da eine Primzahl p nur durch 1 und sich selbst teilbar ist, sind alle p − 1 kleineren Zahlen automatisch teilerfremd zu p.

### Welche Obergrenze gilt für die Eingabe von n?

Das Tool verarbeitet positive ganze Zahlen im Bereich von 1 bis 10¹² (eine Billion).

### Wie viele teilerfremde Zahlen werden in der Detailansicht aufgelistet?

Im Listenmodus werden maximal die ersten 60 teilerfremden Zahlen explizit ausgegeben.

### Wie lautet der Satz von Euler?

Für zwei teilerfremde Zahlen a und n gilt die modulare Kongruenz a^φ(n) ≡ 1 (mod n).

## Ähnliche Tools

- [Carmichael-Funktion-λ(n)-Rechner](https://elysiatools.com/de/tools/carmichael-function): Berechnet die Carmichael-Funktion λ(n) — den Exponenten der multiplikativen Gruppe (Z/nZ)*, also das kleinste k mit a^k ≡ 1 (mod n) für jedes zu n teilerfremde a. Aufgebaut aus der Primfaktorzerlegung (λ(2)=1, λ(4)=2, λ(2^k)=2^(k−2) für k ≥ 3, λ(p^k)=φ(p^k) bei ungeraden Potenzen, dann kgV), zusammen mit φ(n), der Existenz einer Primitivwurzel und dem Korselt-Kriterium zur Erkennung von Carmichael-Zahlen. Klassiker: λ(561) = 80 (561 ist die kleinste Carmichael-Zahl) und λ(8) = 2 < φ(8) = 4.
- [Chinesischer Restsatz (Kongruenzsystem)](https://elysiatools.com/de/tools/chinese-remainder-theorem): Löst das System x ≡ rᵢ (mod mᵢ) (2–20 Kongruenzen) mit dem verallgemeinerten chinesischen Restsatz durch paarweise Verschmelzung: Bei paarweise teilerfremden Moduln ist der kombinierte Modul das Produkt, bei nicht teilerfremden, aber verträglichen das kgV; ein unverträgliches System wird klar als unlösbar gemeldet. Jede Kongruenz wird gegen die Endlösung verifiziert. Klassiker: x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7) → x = 23 (mod 105).
- [Permutations-/Kombinations-/Teilmengen-Generator (mit Wiederholungen)](https://elysiatools.com/de/tools/combinatorial-generation): Erzeugt Permutationen, Kombinationen und Teilmengen einer Multimenge, automatisch dedupliziert und in lexikographischer Ordnung: Permutationen über next_permutation mit exakter Anzahl n!/Π(mᵢ!); Kombinationen als alle verschiedenen k-Teilmengen der Multimenge, gezählt als Koeffizient von x^k in Π(1+x+…+x^mᵢ) (C(n,k) bei lauter verschiedenen Elementen); Teilmengen mit Anzahl Π(mᵢ+1) (2ⁿ bei lauter verschiedenen), inklusive leerer Menge. Bis zu 12 Elemente, Anzeige auf 200 Einträge begrenzt, die Anzahl ist stets exakt; im Kombinationsmodus gilt 1 ≤ k ≤ n. Klassiker: Permutationen von \[A, A, B\] → 3!/2! = 3 (AAB, ABA, BAA); Teilmengen von \[A, A, B\] → (2+1)(1+1) = 6.
- [Nullsummenspiel-Löser (Sattelpunkt / lineare Programmierung)](https://elysiatools.com/de/tools/game-theory-zero-sum): Löst Nullsummenspiele 2–6 × 2–6 (die Auszahlungsmatrix gehört zum Zeilenspieler, dem Maximierer; der Spaltenspieler zahlt): zuerst der Sattelpunkttest (gleicht das Maximin der Zeilenminima dem Minimax der Spaltenmaxima, existiert ein Gleichgewicht in reinen Strategien und alle Sattelzellen werden aufgelistet); andernfalls wird die Matrix verschoben, sodass alle Einträge ≥ 1 sind, und ein einphasiger Simplex (Schlupfbasis, Bland-Regel) löst max Σz u. d. N. Bz ≤ 1: das Primal liefert die gemischte Strategie q des Spaltenspielers, und die dualen Schattenpreise sind exakt die Lösung y des Zeilenspielers; der Wert wird zurückverschoben, x, q und v werden numerisch verifiziert (xᵀA ≥ v, Aq ≤ v) samt Minimax-Gleichheit. Klassiker: Münzwurf \[\[1,-1\],\[-1,1\]\] → Wert 0 mit 0.5/0.5-Mischungen.
- [Inverse-Laplace-Transformationsrechner (Partialbrüche)](https://elysiatools.com/de/tools/inverse-laplace-calculator): Berechnet die inverse Laplace-Transformierte von F(s) = N(s)/D(s) (echt gebrochen, Nennergrad ≤ 6): Wurzeln des Nenners, nach Vielfachheit und konjugierten Paaren gruppiert, Partialbruchzerlegung per linearem Koeffizientensystem und gliedweise Rücktransformation mit den Standardpaaren (A/(s−r)→Ae^(rt), A/(s−r)^j→At^(j−1)e^(rt)/(j−1)!, (Bs+C)/((s−α)²+β²)→e^(αt)\[Bcos(βt)+…sin(βt)\]). Klassiker: 1/(s²+3s+2) → e^(−t)−e^(−2t); (3s+5)/(s²+4) → 3cos(2t)+2,5sin(2t).
- [Laplace-Transformationsrechner (Paar-Tabelle)](https://elysiatools.com/de/tools/laplace-transform-calculator): Liefert per Tabelle die Laplace-Transformierte F(s) = ∫₀^∞ e^(−st)f(t)dt: 14 Standardpaare (1, t, tⁿ, e^(at), tⁿe^(at), sin/cos(kt) mit exponentieller Verschiebung, sinh/cosh, t·sin/t·cos, δ(t)), mit Parametereinsetzung, Konvergenzbereich (z. B. s > a), Herleitungshinweis und optionaler numerischer Auswertung an einer Stelle s (mit Konvergenzprüfung). Beispiel: L{e^t} = 1/(s−1), s>1, F(2) = 1.
- [Multiplikative Ordnung modulo n (Elementordnung)](https://elysiatools.com/de/tools/order-of-element-mod-n): Berechnet die multiplikative Ordnung ord\_n(a) — das kleinste k ≥ 1 mit a^k ≡ 1 (mod n) (erfordert ggT(a, n) = 1). Der Algorithmus startet bei φ(n) und entfernt Primfaktoren unter Prüfung von a^(ord/p); die Ausgabe enthält die Potenztafel von a, den Minimalitätsbeweis (a^(k/p) ≢ 1 für jede Primzahl p | k), die erzeugte zyklische Untergruppe sowie Kennzeichnungen, ob a Primitivwurzel ist (ord = φ(n)) oder die maximale Ordnung erreicht (ord = λ(n)). Klassiker: ord\_7(3) = 6 = φ(7), 3 ist Primitivwurzel modulo 7; ord\_15(2) = 4 < φ(15) = 8.
- [Partialbruchzerlegungs-Rechner (rationale Funktionen)](https://elysiatools.com/de/tools/partial-fraction-decomposer): Zerlegt die rationale Funktion F(x) = N(x)/D(x) in Partialbrüche (Nennergrad ≤ 6, Zähler ≤ 8; unechte Brüche werden zuerst durch Polynomdivision geteilt): Wurzeln des Nenners nach Durand–Kerner, gruppiert nach Vielfachheit und konjugierten Paaren, exaktes lineares Koeffizientensystem für Terme A/(x−r)^j und (Bx+C)/((x−α)²+β²) sowie numerische Restprüfung an algebraischen Testpunkten. Klassiker: (3x+5)/(x²+3x+2) = 2/(x+1) + 1/(x+2); (x³+2x)/(x²+1) = x + x/(x²+1); 1/(x(x+1)²) = 1/x − 1/(x+1) − 1/(x+1)².

## Beispiele

- [Web Python Bildverarbeitung Beispiele](https://elysiatools.com/de/samples/web-image-processing-python): Web Python Bildverarbeitungsbeispiele mit PIL/Pillow einschließlich Lesen, Speichern, Skalieren und Formatkonvertierung
- [Android Java Bildverarbeitungsbeispiele](https://elysiatools.com/de/samples/android-image-processing-java): Android Java Bildverarbeitungsbeispiele einschließlich Lesen/Schreiben, Skalierung und Formatkonvertierung
- [Android Kotlin Bildverarbeitungsbeispiele](https://elysiatools.com/de/samples/android-image-processing-kotlin): Android Kotlin Bildverarbeitungsbeispiele einschließlich Lesen/Schreiben, Skalierung und Formatkonvertierung
- [Web Rust Bildverarbeitungsbeispiele](https://elysiatools.com/de/samples/web-image-processing-rust): Web Rust Bildverarbeitungsbeispiele einschließlich Lesen/Schreiben, Skalierung und Formatkonvertierung