Die ersten tausend Werte der Funktion Die Eulersche Phi -Funktion (andere Schreibweise: eulersche φ-Funktion, auch eulersche Funktion genannt) ist eine zahlentheoretische Funktion . Sie gibt für jede positive natürliche Zahl
n
{\displaystyle n}
n
{\displaystyle n}
teilerfremde positive natürliche Zahlen es gibt, die nicht größer als
n
{\displaystyle n}
Totient von
n
{\displaystyle n}
Ihr Funktionswert
φ
(
n
)
{\displaystyle \varphi (n)}
n
{\displaystyle n}
n
{\displaystyle n}
n
>
1
{\displaystyle n>1}
1
≤
φ
(
n
)
<
n
{\displaystyle 1\leq \varphi (n)<n}
Der Name Phi-Funktion geht auf Leonhard Euler zurück.
Die Phi-Funktion entscheidet über die Konstruierbarkeit eines Polygons in Abhängigkeit von der Anzahl der Ecken des Vielecks
n
{\displaystyle n}
φ
(
n
)
{\displaystyle \varphi (n)}
n
{\displaystyle n}
φ
(
n
)
=
2
m
mit
m
∈
N
{\displaystyle \varphi (n)=2^{m}\quad {\text{mit}}\quad m\in \mathbb {N} }
n
{\displaystyle n}
n
{\displaystyle n}
Fermatscher Primzahlen ist.
Die Phi-Funktion ist definiert durch
φ
:
N
+
→
N
+
{\displaystyle \varphi \colon \mathbb {N} ^{+}\to \mathbb {N} ^{+}}
φ
(
n
)
:=
|
{
a
∈
N
∣
1
≤
a
≤
n
∧
ggT
(
a
,
n
)
=
1
}
|
{\displaystyle \varphi (n)\;:=\;{\Big |}\{a\in \mathbb {N} \,\mid \,1\leq a\leq n\land \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.}
Eine andere, trivialerweise äquivalente, Schreibweise ist die Darstellung als Summe:
φ
(
n
)
=
∑
ggT
(
a
,
n
)
=
1
1
≤
a
≤
n
1
{\displaystyle \varphi (n)\;=\;\sum \limits _{\overset {1\leq a\leq n}{\operatorname {ggT} (a,n)=1}}1}
Die Zahl 1 enthält als Leeres Produkt keinen Primfaktor und ist zu allen Zahlen, auch zu sich selbst, teilerfremd, also ist
φ
(
1
)
=
1.
{\displaystyle \varphi (1)=1.}
Die Zahl 6 ist zu genau zwei der sechs Zahlen von 1 bis 6 teilerfremd (nämlich zu 1 und zu 5), also ist
φ
(
6
)
=
2.
{\displaystyle \varphi (6)=2.}
Die Zahl 13 ist als Primzahl zu jeder der zwölf Zahlen von 1 bis 12 teilerfremd (aber natürlich nicht zu 13), also ist
φ
(
13
)
=
12.
{\displaystyle \varphi (13)=12.}
Die ersten 99 Werte der Phi-Funktion lauten:
φ
(
n
)
{\displaystyle \varphi (n)}
+0
+1
+2
+3
+4
+5
+6
+7
+8
+9
0 0+
0 10 10 20 20 40 20 60 40 6
10+
0 410
0 412
0 60 80 816
0 618
20+
0 812
10
22
0 820
12
18
12
28
30+
0 830
16
20
16
24
12
36
18
24
40+
16
40
12
42
20
24
22
46
16
42
50+
20
32
24
52
18
40
24
36
28
58
60+
16
60
30
36
32
48
20
66
32
44
70+
24
70
24
72
36
40
36
60
24
78
80+
32
54
40
82
24
64
42
56
40
88
90+
24
72
44
60
46
72
32
96
42
60
Die Phi-Funktion ist eine multiplikative zahlentheoretische Funktion , sodass 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. Ein Beispiel dazu:
φ
(
18
)
=
φ
(
2
)
⋅
φ
(
9
)
=
1
⋅
6
=
6
{\displaystyle \varphi (18)=\varphi (2)\cdot \varphi (9)=1\cdot 6=6}
Ein geometrisch ausschlaggebendes weiteres Beispiel hierfür lautet:
φ
(
85
)
=
φ
(
5
)
⋅
φ
(
17
)
=
4
⋅
16
=
64
{\displaystyle \varphi (85)=\varphi (5)\cdot \varphi (17)=4\cdot 16=64}
Das bedeutet, dass das reguläre 85-Eck sehr wohl mit Zirkel und Lineal konstruiert werden kann.
Denn der Phi-Funktionswert von der 85, also die 64 ist eine Zweierpotenz.
Die Funktion
φ
{\displaystyle \varphi }
n
∈
N
+
{\displaystyle n\in \mathbb {N} ^{+}}
φ
(
n
)
{\displaystyle \varphi (n)}
Einheiten im Restklassenring
Z
/
n
Z
{\displaystyle \mathbb {Z} /n\mathbb {Z} }
Ordnung der primen Restklassengruppe .
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}},}
a
b
≡
1
mod
n
,
{\displaystyle ab\equiv 1{\bmod {n}},}
x
{\displaystyle x}
a
b
+
n
x
=
1
{\displaystyle ab+nx=1}
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}}
Bild
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.}
Die Dirichlet-erzeugende Funktion der Phi-Funktion hängt mit der riemannschen Zetafunktion
ζ
{\displaystyle \zeta }
∑
n
=
1
∞
φ
(
n
)
n
s
=
ζ
(
s
−
1
)
ζ
(
s
)
{\displaystyle \sum _{n=1}^{\infty }{\frac {\varphi (n)}{n^{s}}}={\frac {\zeta (s-1)}{\zeta (s)}}}
Da eine Primzahl
p
{\displaystyle p}
teilbar ist, ist sie zu den Zahlen 1 bis
p
−
1
{\displaystyle p-1}
nicht zu sich selbst teilerfremd. Es gilt daher
φ
(
p
)
=
p
−
1.
{\displaystyle \varphi (p)=p-1.}
Eine Potenz
p
k
{\displaystyle p^{k}}
p
{\displaystyle p}
k
∈
N
+
{\displaystyle k\in \mathbb {N} ^{+}}
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,\;\dotsc ,\;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 Phi-Funktion lässt sich für jedes
n
∈
N
+
{\displaystyle n\in \mathbb {N} ^{+}}
kanonischer Primfaktorzerlegung
n
=
∏
p
∣
n
p
k
p
{\displaystyle n=\prod _{p\mid n}p^{k_{p}}}
berechnen, indem man die Multiplikativität und die Formel für Primzahlpotenzen anwendet:
φ
(
n
)
=
∏
p
∣
n
φ
(
p
k
p
)
=
∏
p
∣
n
p
k
p
−
1
(
p
−
1
)
=
n
∏
p
∣
n
(
1
−
1
p
)
{\displaystyle \varphi (n)=\prod _{p\mid n}\varphi (p^{k_{p}})=\prod _{p\mid n}p^{k_{p}-1}(p-1)=n\prod _{p\mid n}\left(1-{\frac {1}{p}}\right)}
wobei die Produkte über alle Primzahlen
p
{\displaystyle p}
n
{\displaystyle n}
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}
oder
φ
(
72
)
=
72
⋅
(
1
−
1
2
)
⋅
(
1
−
1
3
)
=
24
{\displaystyle \varphi (72)=72\cdot (1-{\tfrac {1}{2}})\cdot (1-{\tfrac {1}{3}})=24}
Mit der riemannschen Zetafunktion
ζ
{\displaystyle \zeta }
Landau-Symbol
O
{\displaystyle {\mathcal {O}}}
ζ
(
2
)
=
π
2
6
{\displaystyle \zeta (2)={\tfrac {\pi ^{2}}{6}}}
∑
n
=
1
N
φ
(
n
)
=
1
2
ζ
(
2
)
N
2
+
O
(
N
log
N
)
=
3
π
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)={\frac {3}{\pi ^{2}}}N^{2}+{\mathcal {O}}(N\log N)}
Wegen
∑
n
=
1
N
6
π
2
n
=
6
π
2
N
(
N
+
1
)
2
=
3
π
2
N
2
+
O
(
N
)
{\displaystyle \sum _{n=1}^{N}{\tfrac {6}{\pi ^{2}}}n={\tfrac {6}{\pi ^{2}}}{\tfrac {N(N+1)}{2}}={\tfrac {3}{\pi ^{2}}}N^{2}+{\mathcal {O}}(N)}
lim
N
→
∞
∑
n
=
1
N
φ
(
n
)
∑
n
=
1
N
6
π
2
n
=
lim
N
→
∞
3
π
2
+
O
(
log
N
N
)
3
π
2
+
O
(
1
N
)
=
1
{\displaystyle \lim _{N\to \infty }{\frac {\sum _{n=1}^{N}\varphi (n)}{\sum _{n=1}^{N}{\frac {6}{\pi ^{2}}}n}}=\lim _{N\to \infty }{\frac {{\frac {3}{\pi ^{2}}}+{\mathcal {O}}\left({\frac {\log N}{N}}\right)}{{\frac {3}{\pi ^{2}}}+{\mathcal {O}}\left({\frac {1}{N}}\right)}}=1}
Man sagt dazu auch:
Die eulersche Phifunktion ist die diskrete Fourier-Transformation des ggT , ausgewertet an der Stelle 1:[ 1]
F
{
x
}
[
m
]
=
∑
k
=
1
n
x
k
⋅
e
−
2
π
i
m
k
n
,
x
k
=
{
ggT
(
k
,
n
)
}
für
k
∈
{
1
,
…
,
n
}
φ
(
n
)
=
F
{
x
}
[
1
]
=
∑
k
=
1
n
ggT
(
k
,
n
)
e
−
2
π
i
k
n
{\displaystyle {\begin{aligned}{\mathcal {F}}\left\{\mathbf {x} \right\}[m]&=\sum \limits _{k=1}^{n}x_{k}\cdot e^{-2\pi i{\frac {mk}{n}}},\quad \mathbf {x_{k}} =\left\{\operatorname {ggT} (k,n)\right\}\quad {\text{für }}\,k\in \left\{1,\dotsc ,n\right\}\\\varphi (n)&={\mathcal {F}}\left\{\mathbf {x} \right\}[1]=\sum \limits _{k=1}^{n}\operatorname {ggT} (k,n)e^{-2\pi i{\frac {k}{n}}}\end{aligned}}}
Nimmt man auf beiden Seiten den Realteil, ergibt sich die Gleichung
φ
(
n
)
=
∑
k
=
1
n
ggT
(
k
,
n
)
cos
(
2
π
k
n
)
.
{\displaystyle \varphi (n)=\sum \limits _{k=1}^{n}\operatorname {ggT} (k,n)\cos \left(2\pi {\frac {k}{n}}\right).}
Es gilt
φ
(
n
)
>
n
2
,
{\displaystyle \varphi (n)>{\frac {\sqrt {n}}{2}},}
n
{\displaystyle n}
φ
(
n
)
≥
n
.
{\displaystyle \varphi (n)\geq {\sqrt {n}}.}
Für
n
≥
2
{\displaystyle n\geq 2}
∑
1
≤
j
≤
n
−
1
ggT
(
n
,
j
)
=
1
j
=
n
2
φ
(
n
)
{\displaystyle \sum _{1\leq j\leq n-1 \atop \operatorname {ggT} (n,j)=1}j={\frac {n}{2}}\varphi (n)}
Für alle
n
∈
N
+
{\displaystyle n\in \mathbb {N} ^{+}}
[ 2]
∑
d
>
0
d
∣
n
φ
(
d
)
=
n
{\displaystyle \sum _{d>0 \atop d\mid n}\varphi (d)=n}
Beispiel: Für
n
=
100
{\displaystyle n=100}
T
(
n
)
:=
{
t
∈
N
+
|
t
|
n
}
{\displaystyle T(n):=\{t\in \ N^{+}\;{\big |}\;t\vert n\}}
n
{\displaystyle n}
T
(
100
)
=
T
(
2
2
⋅
5
2
)
=
{
2
m
⋅
5
n
∣
m
∈
{
0
,
1
,
2
}
,
n
∈
{
0
,
1
,
2
}
}
=
{
1
,
2
,
4
,
5
,
10
,
20
,
25
,
50
,
100
}
{\displaystyle T(100)=T(2^{2}\cdot 5^{2})=\left\{2^{m}\cdot 5^{n}\mid m\in \{0,1,2\},n\in \{0,1,2\}\right\}=\{1,2,4,5,10,20,25,50,100\}}
gegeben. Addition der zugehörigen
|
T
(
100
)
|
=
(
2
+
1
)
(
2
+
1
)
=
9
{\displaystyle |T(100)|=(2+1)(2+1)=9}
φ
(
1
)
=
1
φ
(
2
)
=
1
φ
(
4
)
=
2
φ
(
5
)
=
4
φ
(
10
)
=
4
φ
(
20
)
=
8
φ
(
25
)
=
20
φ
(
50
)
=
20
φ
(
100
)
=
40
{\displaystyle {\begin{aligned}\varphi (1)&=1\\\varphi (2)&=1\\\varphi (4)&=2\\\varphi (5)&=4\\\varphi (10)&=4\\\varphi (20)&=8\\\varphi (25)&=20\\\varphi (50)&=20\\\varphi (100)&=40\end{aligned}}}
ergibt:
∑
d
>
0
d
∣
100
φ
(
d
)
=
φ
(
1
)
+
φ
(
2
)
+
φ
(
4
)
+
φ
(
5
)
+
φ
(
10
)
+
φ
(
20
)
+
φ
(
25
)
+
φ
(
50
)
+
φ
(
100
)
=
1
+
1
+
2
+
4
+
4
+
8
+
20
+
20
+
40
=
100
{\displaystyle {\begin{aligned}\sum _{d>0 \atop d\mid 100}\varphi (d)&=\varphi (1)+\varphi (2)+\varphi (4)+\varphi (5)+\varphi (10)+\varphi (20)+\varphi (25)+\varphi (50)+\varphi (100)\\&=1+1+2+4+4+8+20+20+40=100\end{aligned}}}
Eine wichtige Anwendung findet die Phi-Funktion im Satz von Fermat-Euler :
Wenn zwei natürliche Zahlen
a
{\displaystyle a}
m
{\displaystyle m}
m
{\displaystyle m}
a
φ
(
m
)
−
1
:
{\displaystyle a^{\varphi (m)}-1\colon }
ggT
(
a
,
m
)
=
1
⇒
m
∣
a
φ
(
m
)
−
1
{\displaystyle \operatorname {ggT} (a,m)=1\Rightarrow m\mid a^{\varphi (m)}-1}
Etwas anders formuliert:
ggT
(
a
,
m
)
=
1
⇒
a
φ
(
m
)
≡
1
mod
m
{\displaystyle \operatorname {ggT} (a,m)=1\Rightarrow a^{\varphi (m)}\equiv 1{\bmod {m}}}
Ein Spezialfall (für Primzahlen
p
{\displaystyle p}
kleine fermatsche Satz :
p
∤
a
⇒
p
∣
a
p
−
1
−
1
{\displaystyle p\nmid a\Rightarrow p\mid a^{p-1}-1}
p
∤
a
⇒
a
p
−
1
≡
1
mod
p
{\displaystyle p\nmid a\Rightarrow a^{p-1}\equiv 1{\bmod {p}}}
Der Satz von Fermat-Euler findet unter anderem Anwendung beim Erzeugen von Schlüsseln für das RSA -Verfahren in der Kryptographie .
Der
φ
{\displaystyle \varphi }
Konstruierbarkeit eines Polygons das entscheidende Kriterium.
↑ Wolfgang Schramm: The Fourier transform of functions of the greatest common divisor . In: Integers Electronic Journal of Combinatorial Number Theory . 8. Jahrgang. University of West Georgia , Karls-Universität Prag , 2008, S. A50 (colgate.edu [abgerufen am 31. Mai 2021]).
↑ Johannes Buchmann: Einführung in die Kryptographie. Theorem 3.8.4.
![{\displaystyle {\begin{aligned}{\mathcal {F}}\left\{\mathbf {x} \right\}[m]&=\sum \limits _{k=1}^{n}x_{k}\cdot e^{-2\pi i{\frac {mk}{n}}},\quad \mathbf {x_{k}} =\left\{\operatorname {ggT} (k,n)\right\}\quad {\text{für }}\,k\in \left\{1,\dotsc ,n\right\}\\\varphi (n)&={\mathcal {F}}\left\{\mathbf {x} \right\}[1]=\sum \limits _{k=1}^{n}\operatorname {ggT} (k,n)e^{-2\pi i{\frac {k}{n}}}\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/95052f791b719faf16447f07084aaa2819ed5591)
