Eulersche Phi-Funktion (φ) Rechner — Teilerfremde Zahlen zählen

Gib eine ganze Zahl N (1 bis 1.000.000) ein, um sofort die Anzahl der zu N teilerfremden ganzen Zahlen von 1 bis N (Eulersche φ-Funktion φ(N)) zu berechnen – nicht nur das Ergebnis, sondern auch Primfaktorzerlegung und verwendete Formel. Kostenlose φ(n)-Referenztabelle für 1 bis 100 inklusive.

Zuletzt aktualisiert: 2026-09-06

φ(n)-Referenztabelle für 1 bis 100

Eine Tabelle mit der Primfaktorzerlegung und dem Wert der Eulerschen φ-Funktion für jede ganze Zahl von 1 bis 100.

N	Zerlegung	φ(n)
1	1	1
2	2	1
3	3	2
4	2²	2
5	5	4
6	2 × 3	2
7	7	6
8	2³	4
9	3²	6
10	2 × 5	4
11	11	10
12	2² × 3	4
13	13	12
14	2 × 7	6
15	3 × 5	8
16	2⁴	8
17	17	16
18	2 × 3²	6
19	19	18
20	2² × 5	8
21	3 × 7	12
22	2 × 11	10
23	23	22
24	2³ × 3	8
25	5²	20
26	2 × 13	12
27	3³	18
28	2² × 7	12
29	29	28
30	2 × 3 × 5	8
31	31	30
32	2⁵	16
33	3 × 11	20
34	2 × 17	16
35	5 × 7	24
36	2² × 3²	12
37	37	36
38	2 × 19	18
39	3 × 13	24
40	2³ × 5	16
41	41	40
42	2 × 3 × 7	12
43	43	42
44	2² × 11	20
45	3² × 5	24
46	2 × 23	22
47	47	46
48	2⁴ × 3	16
49	7²	42
50	2 × 5²	20
51	3 × 17	32
52	2² × 13	24
53	53	52
54	2 × 3³	18
55	5 × 11	40
56	2³ × 7	24
57	3 × 19	36
58	2 × 29	28
59	59	58
60	2² × 3 × 5	16
61	61	60
62	2 × 31	30
63	3² × 7	36
64	2⁶	32
65	5 × 13	48
66	2 × 3 × 11	20
67	67	66
68	2² × 17	32
69	3 × 23	44
70	2 × 5 × 7	24
71	71	70
72	2³ × 3²	24
73	73	72
74	2 × 37	36
75	3 × 5²	40
76	2² × 19	36
77	7 × 11	60
78	2 × 3 × 13	24
79	79	78
80	2⁴ × 5	32
81	3⁴	54
82	2 × 41	40
83	83	82
84	2² × 3 × 7	24
85	5 × 17	64
86	2 × 43	42
87	3 × 29	56
88	2³ × 11	40
89	89	88
90	2 × 3² × 5	24
91	7 × 13	72
92	2² × 23	44
93	3 × 31	60
94	2 × 47	46
95	5 × 19	72
96	2⁵ × 3	32
97	97	96
98	2 × 7²	42
99	3² × 11	60
100	2² × 5²	40

Was die eulersche φ-Funktion ist

Die eulersche φ-Funktion zählt, wie viele der ganzen Zahlen von 1 bis n zu n teilerfremd sind. Teilerfremd heißt, dass ihr größter gemeinsamer Teiler 1 ist – dass sie also keinen Primfaktor gemeinsam haben. So ist φ(9) gleich 6, denn 1, 2, 4, 5, 7 und 8 teilen mit 9 keinen Primfaktor.

Dieses Werkzeug ermittelt φ(N) aus der eingegebenen ganzen Zahl und zeigt neben der Antwort **die Primfaktorzerlegung von N sowie die Formel, die von ihr zu φ(N) führt**. Die Formel lautet φ(n) = n × Π(1 − 1/p), das Produkt genommen über die verschiedenen Primfaktoren p von n. Wie oft ein Primfaktor auch auftritt, er geht nur einmal in das Produkt ein: der Exponent ändert am Ergebnis nichts. Zulässig ist alles von 1 bis 1.000.000, und darunter steht eine Tabelle von φ(n) für 1 bis 100.

So benutzen Sie den Rechner

Die ganze Zahl N eingeben Geben Sie eine ganze Zahl von 1 bis 1.000.000 an. Alles außerhalb dieses Bereichs oder Nichtganzzahlige führt zu einem Hinweis.
Den Wert von φ(N) ablesen Während der Eingabe erscheint die Anzahl der zu N teilerfremden ganzen Zahlen von 1 bis N.
Die Primfaktorzerlegung prüfen Es wird gezeigt, in welche Primzahlen N zerfällt – ein Faden, dem Sie folgen können, um zu sehen, woher der Wert von φ(N) rührt.
Die Herleitung an der Formel verfolgen Die Formel φ(n) = n × Π(1 − 1/p) erscheint mit den wirklichen Primfaktoren eingesetzt – bereit, eine von Hand geführte Rechnung zu prüfen.
Mit der Tabelle vergleichen Unten steht eine Liste von φ(n) für 1 bis 100, an der sich Regelmäßigkeiten mit eigenen Augen sehen lassen – etwa, dass φ einer Primzahl um eins kleiner ist als sie selbst.

Tipps für die Nutzung

Die Eulersche φ-Funktion φ(n) zählt die ganzen Zahlen von 1 bis n, die zu n teilerfremd sind. Beispiel: φ(9) = 6 (1, 2, 4, 5, 7 und 8 sind teilerfremd zu 9).
Ist n eine Primzahl p, gilt φ(p) = p − 1, denn alle Zahlen von 1 bis p außer p selbst sind zu einer Primzahl teilerfremd.
Ist n das Produkt zweier verschiedener Primzahlen p und q, gilt φ(pq) = (p−1)(q−1) — eine Eigenschaft, die direkt bei der RSA-Schlüsselerzeugung verwendet wird.
Die Formel φ(n) = n × Π(1 − 1/p) ist ein Produkt über die verschiedenen Primfaktoren p von n; der Exponent jeder Primzahl beeinflusst das Ergebnis nicht.
Dieses Tool deckt den Bereich 1 bis 1.000.000 ab und berechnet φ(n) sofort mittels Primfaktorzerlegung durch Probedivision.

Wofür sich die φ-Funktion eignet

Zahlentheorie lernen und Hausaufgaben prüfen

Bestätigen Sie, ob das von Hand gewonnene φ(n) stimmt. Da Zerlegung und Formel danebenstehen, findet man auch einen Fehler in der Herleitung und nicht bloß im Ergebnis.

Verstehen, wie RSA arbeitet

RSA nimmt das Produkt n = pq zweier Primzahlen als Teil des öffentlichen Schlüssels, und für den geheimen Schlüssel braucht es φ(n) = (p−1)(q−1). Mit kleinen Primzahlen durchgerechnet, wird dieser Zusammenhang greifbar.

Den eulerschen Satz nachprüfen

Der eulersche Satz besagt, dass für ein zu n teilerfremdes a die Potenz a hoch φ(n) bei Division durch n den Rest 1 lässt. Hat man φ(n) zuerst, so lässt sich der Satz an kleinen Zahlen ausprobieren.

Die multiplikative Eigenschaft beobachten

Sind m und n teilerfremd, so gilt φ(mn) = φ(m)φ(n). Kombiniert man Werte aus der Tabelle, so sieht man, dass dies wirklich zutrifft.

Wenn Sie die Zerlegung selbst suchen

Brauchen Sie nur die Faktoren, so nehmen Sie die Primfaktorzerlegung; um zu prüfen, ob eine Zahl prim ist, den Primzahltest.

Begriffe rund um die φ-Funktion

Eulersche φ-Funktion: Die Funktion, die angibt, wie viele ganze Zahlen von 1 bis n zu n teilerfremd sind. Sie wird φ(n) geschrieben und wurde im 18. Jahrhundert von Leonhard Euler eingeführt.
Teilerfremd: Der Zustand zweier ganzer Zahlen, deren größter gemeinsamer Teiler 1 ist – gleichbedeutend damit, dass sie überhaupt keinen Primfaktor gemeinsam haben.
Primfaktorzerlegung: Das Schreiben einer ganzen Zahl als Produkt von Primzahlen. Da φ(n) allein von den verschiedenen Primfaktoren von n abhängt, beginnt die Rechnung bei dieser Zerlegung.
Multiplikative Funktion: Eine Funktion, für die f(mn) = f(m)f(n) gilt, sooft m und n teilerfremd sind. φ hat diese Eigenschaft, weshalb sich der Wert für eine große Zahl aus ihren Primfaktoren zusammensetzen lässt.
Eulerscher Satz: Der Satz, dass für jedes zu n teilerfremde a die Potenz a hoch φ(n) bei Division durch n stets den Rest 1 lässt. Auf einen Primzahlmodul eingeschränkt, ist er der kleine Satz von Fermat.
RSA: Ein Verfahren mit öffentlichem Schlüssel, das das Produkt zweier großer Primzahlen als öffentlichen Schlüssel nimmt. Der geheime Schlüssel braucht φ(n), und dass sich φ(n) ohne Zerlegung von n nicht gewinnen lässt, ist einer der Gründe seiner Sicherheit.

Häufig gestellte Fragen

Neben ihrer Bedeutung in der Zahlentheorie ist sie zentral für die Kryptografie, insbesondere für die RSA-Schlüsselerzeugung. Der private RSA-Schlüssel wird mithilfe von φ(n) = (p−1)(q−1) berechnet.

Per Konvention wird φ(1) = 1 festgelegt. Zwar ist die einzige zu 1 teilerfremde ganze Zahl bis 1 die 1 selbst, aber die Definition φ(1) = 1 hält die multiplikativen Eigenschaften der Funktion konsistent – dies ist die mathematische Standardkonvention.

Ja. Da eine Primzahl p außer 1 und sich selbst keine Teiler hat, sind alle ganzen Zahlen von 1 bis p außer p selbst teilerfremd zu ihr, also gilt φ(p) = p − 1.

RSA verwendet eine zusammengesetzte Zahl n = pq, das Produkt zweier großer Primzahlen, als Teil des öffentlichen Schlüssels. Zur Berechnung des privaten Schlüssels ist φ(n) = (p−1)(q−1) nötig, aber φ(n) lässt sich ohne Faktorisierung von n nicht bestimmen — diese Schwierigkeit der Faktorisierung großer Zahlen ist die Grundlage der RSA-Sicherheit.

Übrigens – Die Funktion aus dem 18. Jahrhundert, die Teilerfremdes zählt

Die Eulersche φ-Funktion wurde um 1763 vom Schweizer Mathematiker Leonhard Euler eingeführt, ursprünglich im Zuge der Verallgemeinerung des kleinen Satzes von Fermat auf zusammengesetzte Zahlen. Das heute übliche Symbol φ (phi) wurde erst später von anderen Mathematikern bei der Systematisierung der Notation übernommen.

Das Zählen teilerfremder Zahlen klingt einfach, doch φ(n) besitzt mehrere elegante Eigenschaften. Summiert man beispielsweise φ(d) über alle Teiler d von n, erhält man stets n selbst (Σφ(d) = n) — eine der grundlegenden Identitäten der elementaren Zahlentheorie.

Heute spielt φ(n) eine wesentliche Rolle in der RSA-Kryptografie. RSA verwendet das Produkt zweier großer Primzahlen n = pq als Teil des öffentlichen Schlüssels, und zur Berechnung des privaten Schlüssels wird φ(n) = (p−1)(q−1) benötigt. Dass φ(n) ohne Faktorisierung von n nicht berechnet werden kann (zumindest mit derzeit bekannten Algorithmen), ist eine der Grundlagen der Sicherheit von RSA.

Alle Wissenstexte ansehen