Eulersche Phi-Funktion (φ) Rechner

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, inklusive Primfaktorzerlegung und verwendeter Formel. Mit einer φ(n)-Referenztabelle für 1 bis 100.

φ(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

Tipps

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.

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

Eulersche Phi-Funktion (φ) Rechner

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

Tipps

Häufig gestellte Fragen

Wofür wird die Eulersche φ-Funktion verwendet?

Warum ist φ(1) gleich 1?

Lässt sich φ(p) für eine Primzahl p leicht berechnen?

Wie hängt φ(n) mit der RSA-Verschlüsselung zusammen?

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