Eulerin φ-funktio
φ
(
n
)
{\displaystyle \varphi (n)}
k
≤
n
{\displaystyle k\leq n}
n , k ) = 1 eli n ja k ovat suhteellisia alkulukuja .[1]
φ
(
10
)
=
4
{\displaystyle \varphi (10)=4}
φ-funktion arvo voidaan laskea kaavasta
φ
(
n
)
=
n
∏
p
|
n
(
1
−
1
p
)
{\displaystyle \varphi (n)=n\prod _{p|n}\left(1-{\frac {1}{p}}\right)}
eli tuloon otetaan tekijöiksi kaikki alkuluvut
p
{\displaystyle p}
n
{\displaystyle n}
[2]
φ
(
10
)
=
10
∏
p
|
10
(
1
−
1
p
)
=
10
(
1
−
1
2
)
(
1
−
1
5
)
=
4
{\displaystyle \varphi (10)=10\prod _{p|10}\left(1-{\frac {1}{p}}\right)=10\left(1-{\frac {1}{2}}\right)\left(1-{\frac {1}{5}}\right)=4}
koska vain alkuluvut 2 ja 5 jakavat luvun 10.
∑
d
∣
n
μ
2
(
d
)
φ
(
d
)
=
n
φ
(
n
)
{\displaystyle \sum _{d\mid n}{\frac {\mu ^{2}(d)}{\varphi (d)}}={\frac {n}{\varphi (n)}}}
∑
1
≤
k
≤
n
(
k
,
n
)
=
1
k
=
1
2
n
φ
(
n
)
jos
n
>
1
{\displaystyle \sum _{1\leq k\leq n \atop (k,n)=1}\!\!k={\frac {1}{2}}n\varphi (n){\text{ jos }}n>1}
φ
(
n
)
=
∑
d
∣
n
d
⋅
μ
(
n
d
)
=
n
∑
d
∣
n
μ
(
d
)
d
{\displaystyle \varphi (n)=\sum _{d\mid n}d\cdot \mu \left({\frac {n}{d}}\right)=n\sum _{d\mid n}{\frac {\mu (d)}{d}}}
φ
(
n
)
=
∑
k
=
1
n
gcd
(
k
,
n
)
cos
2
π
k
n
{\displaystyle \varphi (n)=\sum \limits _{k=1}^{n}\gcd(k,n)\cos {2\pi {\frac {k}{n}}}}
∑
k
=
1
n
φ
(
k
)
=
1
2
ζ
(
2
)
n
2
+
O
(
n
log
n
)
{\displaystyle \sum _{k=1}^{n}\varphi (k)={\frac {1}{2\zeta (2)}}n^{2}+{\mathcal {O}}(n\log n)}
missä ζ on Riemannin zeeta-funktio .
Kaavasta seuraa approximaatio
φ
(
n
)
≈
n
3
π
2
.
{\displaystyle \varphi (n)\approx n{\frac {3}{\pi ^{2}}}.}
∑
k
=
1
n
φ
(
k
)
=
1
2
(
1
+
∑
k
=
1
n
μ
(
k
)
⌊
n
k
⌋
2
)
{\displaystyle \sum _{k=1}^{n}\varphi (k)={\frac {1}{2}}\left(1+\sum _{k=1}^{n}\mu (k)\left\lfloor {\frac {n}{k}}\right\rfloor ^{2}\right)}
∑
k
=
1
n
φ
(
k
)
k
=
∑
k
=
1
n
μ
(
k
)
k
⌊
n
k
⌋
=
6
π
2
n
+
O
(
(
log
n
)
2
/
3
(
log
log
n
)
4
/
3
)
{\displaystyle \sum _{k=1}^{n}{\frac {\varphi (k)}{k}}=\sum _{k=1}^{n}{\frac {\mu (k)}{k}}\left\lfloor {\frac {n}{k}}\right\rfloor ={\frac {6}{\pi ^{2}}}n+{\mathcal {O}}\left((\log n)^{2/3}(\log \log n)^{4/3}\right)}
∑
k
=
1
n
k
φ
(
k
)
=
315
ζ
(
3
)
2
π
4
n
−
log
n
2
+
O
(
(
log
n
)
2
/
3
)
{\displaystyle \sum _{k=1}^{n}{\frac {k}{\varphi (k)}}={\frac {315\zeta (3)}{2\pi ^{4}}}n-{\frac {\log n}{2}}+{\mathcal {O}}\left((\log n)^{2/3}\right)}
∑
k
=
1
n
1
φ
(
k
)
=
315
ζ
(
3
)
2
π
4
(
log
n
+
γ
−
∑
p
alkuluku
log
p
p
2
−
p
+
1
)
+
O
(
(
log
n
)
2
/
3
n
)
{\displaystyle \sum _{k=1}^{n}{\frac {1}{\varphi (k)}}={\frac {315\zeta (3)}{2\pi ^{4}}}\left(\log n+\gamma -\sum _{p{\text{ alkuluku}}}{\frac {\log p}{p^{2}-p+1}}\right)+{\mathcal {O}}\left({\frac {(\log n)^{2/3}}{n}}\right)}
(missä γ on Eulerin vakio ).
∑
1
≤
k
≤
n
(
k
,
m
)
=
1
1
=
n
φ
(
m
)
m
+
O
(
2
ω
(
m
)
)
,
{\displaystyle \sum _{1\leq k\leq n \atop (k,m)=1}1=n{\frac {\varphi (m)}{m}}+{\mathcal {O}}\left(2^{\omega (m)}\right),}
missä m > 1 on positiivinen kokonaisluku ja ω(m ) on m :n eri alkulukujakajien määrä.
φ-funktiolle on voimassa
φ
(
n
)
≥
n
{\displaystyle \varphi (n)\geq {\sqrt {n}}}
n >6.
φ
(
n
)
>
n
e
γ
log
log
n
+
3
log
log
n
{\displaystyle \varphi (n)>{\frac {n}{e^{\gamma }\;\log \log n+{\frac {3}{\log \log n}}}}}
γ
{\displaystyle \gamma }
Eulerin vakio .
φ
(
n
)
≥
n
2
{\displaystyle \varphi (n)\geq {\sqrt {\frac {n}{2}}}}
n > 0,
Kaikille
n
>
1
{\displaystyle n>1}
0
<
φ
(
n
)
n
<
1
{\displaystyle 0<{\frac {\varphi (n)}{n}}<1}
Suurillekaan luvuille n yllä olevaa epäyhtälöä ei voi parantaa. Tarkemmin sanoen:
lim inf
φ
(
n
)
n
=
0
ja
lim sup
φ
(
n
)
n
=
1.
{\displaystyle \liminf {\frac {\varphi (n)}{n}}=0{\mbox{ ja }}\limsup {\frac {\varphi (n)}{n}}=1.}
∑
gcd
(
k
,
n
)
=
1
1
≤
k
≤
n
gcd
(
k
−
1
,
n
)
=
φ
(
n
)
d
(
n
)
{\displaystyle \sum _{\stackrel {1\leq k\leq n}{\gcd(k,n)=1}}\gcd(k-1,n)=\varphi (n)d(n)}
Rosen, Kenneth H.: Elementary Number Theory and Its Applications . Reading, Massachusetts: Addison-Wesley, 1984. ISBN 0-201-06561-4 . (englanniksi)
↑ Rosen, s. 161
↑ Rosen, s. 169
