Die ersten tausend Werte von
φ
(
n
)
{\displaystyle \varphi (n)}
Die eulersche
φ
{\displaystyle \varphi }
(auch eulersche Funktion genannt) ist eine zahlentheoretische Funktion . Sie gibt für jede natürliche Zahl
n
{\displaystyle n}
a
≤
n
{\displaystyle a\leq n}
teilerfremd sind:
φ
(
n
)
:=
|
{
1
≤
a
≤
n
|
ggT
(
a
,
n
)
=
1
}
|
{\displaystyle \varphi (n)\;:=\;{\Big |}\{1\leq a\leq n\,|\,\operatorname {ggT} (a,n)=1\}{\Big |}}
Dabei bezeichnet
ggT
(
a
,
n
)
{\displaystyle \operatorname {ggT} (a,n)}
größten gemeinsamen Teiler von
a
{\displaystyle a}
n
{\displaystyle n}
Die
φ
{\displaystyle \varphi }
Leonhard Euler und wird mit dem griechischen Buchstaben
φ
{\displaystyle \varphi }
phi ) bezeichnet.
Beispiele
Die Zahl 6 ist zu zwei der Zahlen von 1 bis 6 teilerfremd (1 und 5), also ist
φ
(
6
)
=
2
{\displaystyle \varphi (6)=2}
Die Zahl 13 ist als Primzahl zu den zwölf Zahlen 1 bis 12 teilerfremd, also ist
φ
{\displaystyle \varphi }
Die ersten zehn Werte der
φ
{\displaystyle \varphi }
n 1
2
3
4
5
6
7
8
9
10
teilerfremde
1
1
1, 2
1, 3
1, 2, 3, 4
1, 5
1, 2, 3, 4, 5, 6
1, 3, 5, 7
1, 2, 4, 5, 7, 8
1, 3, 7, 9
φ
(
n
)
{\displaystyle \varphi (n)}
1
1
2
2
4
2
6
4
6
4
Eigenschaften
Multiplikative Funktion
Die
φ
{\displaystyle \varphi }
multiplikative zahlentheoretische Funktion . Das heißt, dass für teilerfremde Zahlen
m
{\displaystyle m}
n
{\displaystyle n}
φ
(
m
⋅
n
)
=
φ
(
m
)
⋅
φ
(
n
)
{\displaystyle \varphi (m\cdot n)=\varphi (m)\cdot \varphi (n)}
gilt. Beispielsweise ist
φ
(
18
)
=
φ
(
2
)
⋅
φ
(
9
)
=
1
⋅
6
=
6
{\displaystyle \varphi (18)=\varphi (2)\cdot \varphi (9)=1\cdot 6=6}
Dichte
φ
(
n
)
{\displaystyle \varphi (n)\,}
Z
/
n
Z
{\displaystyle {\mathbb {Z} }/n{\mathbb {Z} }}
Denn ist
a
¯
∈
Z
/
n
Z
{\displaystyle {\overline {a}}\in {\mathbb {Z} }/n{\mathbb {Z} }}
a
¯
∈
(
Z
/
n
Z
)
∗
{\displaystyle {\overline {a}}\in ({\mathbb {Z}}/n{\mathbb {Z}})^{*}}
b
¯
∈
Z
/
n
Z
{\displaystyle {\overline {b}}\in {\mathbb {Z} }/n{\mathbb {Z} }}
a
¯
⋅
b
¯
=
1
¯
{\displaystyle {\overline {a}}\cdot {\overline {b}}={\overline {1}}}
Was äquivalent zu
a
b
≡
1
m
o
d
n
{\displaystyle ab\equiv 1\,\mathrm {mod} \,n}
a
b
+
n
x
=
1
{\displaystyle ab+nx=1\,}
x
∈
Z
{\displaystyle x\in {\mathbb {Z}}}
Nach dem Lemma von Bézout ist dies äquivalent zur Teilerfremdheit von
a
{\displaystyle a\,}
n
{\displaystyle n\,}
φ
(
n
)
{\displaystyle \varphi (n)}
n
>
2
{\displaystyle n>2}
Ist
a
n
{\displaystyle a_{n}}
i
m
(
φ
)
{\displaystyle \mathrm {im} (\varphi )}
n
{\displaystyle n}
lim
n
→
∞
a
n
n
=
0
{\displaystyle \lim _{n\to \infty }{\frac {a_{n}}{n}}=0}
Das Bild der
φ
{\displaystyle \varphi }
Berechnung
Primzahlen
Da jede Primzahl
p
{\displaystyle p}
teilbar ist, ist sie zu den Zahlen 1 bis
p
−
1
{\displaystyle p-1}
φ
(
p
)
=
p
−
1
{\displaystyle \varphi (p)=p-1}
Potenz von Primzahlen
Eine Potenz
p
k
{\displaystyle p^{k}}
p
{\displaystyle p}
k
{\displaystyle k}
p
{\displaystyle p}
p
k
{\displaystyle p^{k}}
Vielfachen von
p
{\displaystyle p}
p
k
{\displaystyle p^{k}}
1
⋅
p
,
2
⋅
p
,
3
⋅
p
,
⋯
,
p
k
−
1
⋅
p
=
p
k
{\displaystyle 1\cdot p,2\cdot p,3\cdot p,\cdots ,p^{k-1}\cdot p=p^{k}}
Das sind
p
k
−
1
{\displaystyle p^{k-1}}
p
k
{\displaystyle p^{k}}
φ
{\displaystyle \varphi }
φ
(
p
k
)
=
p
k
−
p
k
−
1
=
p
k
−
1
(
p
−
1
)
=
p
k
(
1
−
1
p
)
{\displaystyle \varphi (p^{k})=p^{k}-p^{k-1}=p^{k-1}(p-1)=p^{k}\left(1-{\frac {1}{p}}\right)}
Beispiel:
φ
(
16
)
=
φ
(
2
4
)
=
2
4
−
2
3
=
2
3
⋅
(
2
−
1
)
=
2
4
⋅
(
1
−
1
2
)
=
8
{\displaystyle \varphi (16)=\varphi (2^{4})=2^{4}-2^{3}=2^{3}\cdot (2-1)=2^{4}\cdot \left(1-{\frac {1}{2}}\right)=8}
Der Wert der eulerschen
φ
{\displaystyle \varphi }
kanonischen Primfaktorzerlegung
n
=
∏
p
∣
n
p
k
p
{\displaystyle n=\prod _{p\mid n}p^{k_{p}}}
berechnen:
φ
(
n
)
=
∏
p
∣
n
p
k
p
−
1
(
p
−
1
)
=
n
∏
p
∣
n
(
1
−
1
p
)
{\displaystyle \varphi (n)=\prod _{p\mid n}p^{k_{p}-1}(p-1)=n\prod _{p\mid n}\left(1-{\frac {1}{p}}\right)}
Diese Formel folgt direkt aus der Multiplikativität der
φ
{\displaystyle \varphi }
Beispiel:
φ
(
72
)
=
φ
(
2
3
⋅
3
2
)
=
2
3
−
1
⋅
(
2
−
1
)
⋅
3
2
−
1
⋅
(
3
−
1
)
=
2
2
⋅
1
⋅
3
⋅
2
=
24
{\displaystyle \varphi (72)=\varphi (2^{3}\cdot 3^{2})=2^{3-1}\cdot (2-1)\cdot 3^{2-1}\cdot (3-1)=2^{2}\cdot 1\cdot 3\cdot 2=24}
Eine Abschätzung für das arithmetische Mittel von
φ
{\displaystyle \varphi }
∑
n
=
1
N
φ
(
n
)
=
1
2
ζ
(
2
)
N
2
+
O
(
N
log
N
)
{\displaystyle \sum _{n=1}^{N}\varphi (n)={\frac {1}{2\zeta (2)}}N^{2}+{\mathcal {O}}(N\log N)}
wobei ζ die riemannsche Zetafunktion und O das Landau-Symbol ist.
Das heißt: Im Mittel ist
φ
(
n
)
≈
n
3
π
2
.
{\displaystyle \varphi (n)\approx n{\frac {3}{\pi ^{2}}}.}
φ
{\displaystyle \varphi }
Eine der wichtigsten Anwendungen findet die
φ
{\displaystyle \varphi }
Satz von Fermat-Euler :
Wenn zwei ganze Zahlen a und m ≥ 2 teilerfremd sind, gilt:
m
∣
a
φ
(
m
)
−
1
{\displaystyle m\mid a^{\varphi (m)}-1}
oder anders formuliert:
a
φ
(
m
)
≡
1
(
mod
m
)
{\displaystyle a^{\varphi (m)}\equiv 1{\pmod {m}}}
Ein Spezialfall (für Primzahlen p ) dieses Satzes ist der kleine fermatsche Satz :
p
∣
a
p
−
1
−
1
{\displaystyle p\mid a^{p-1}-1}
bzw.
a
p
−
1
≡
1
(
mod
p
)
{\displaystyle a^{p-1}\equiv 1{\pmod {p}}}
Der Satz von Fermat-Euler findet unter anderem Anwendung bei der Generierung von Schlüsseln für das RSA -Verfahren in der Kryptographie .
Weblinks
