Првих хиљаду вредности за
ϕ
(
n
)
{\displaystyle \phi (n)}
У теорији бројева , Ојлерова фи функција
ϕ
(
n
)
{\displaystyle \phi (n)}
позитивне целе бројеве n , је дефинисана као број позитивних целих бројева мањих или једнаких n , који су узајамно прости са n .
На пример,
ϕ
(
9
)
=
6
{\displaystyle \phi (9)=6}
Ојлерова функција је добила име по швајцарском математичару Леонарду Ојлеру .
Ојлерова фи функција је важна углавном због тога што даје величину мултипликативних група целих бројева по модулу n . Прецизније,
ϕ
(
n
)
{\displaystyle \phi (n)}
јединица прстена
Z
/
n
Z
{\displaystyle \mathbb {Z} /n\mathbb {Z} }
Лагранжовом теоремом , даје доказ Ојлерове теореме .
Из дефиниције следи да је
ϕ
(
1
)
=
1
{\displaystyle \phi (1)=1}
ϕ
(
n
)
=
(
p
−
1
)
p
k
−
1
{\displaystyle \phi (n)=(p-1)p^{k-1}}
n k -ти степен простог броја p . Штавише,
ϕ
{\displaystyle \phi }
мултипликативна функција ; ако су m и n узајамно прости, онда
ϕ
(
m
n
)
=
ϕ
(
m
)
ϕ
(
n
)
{\displaystyle \phi (mn)=\phi (m)\phi (n)}
ϕ
(
n
)
{\displaystyle \phi (n)}
Основне теореме аритметике : ако
n
=
p
1
k
1
⋯
p
r
k
r
{\displaystyle n=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}}
где су
p
j
{\displaystyle p_{j}}
φ
(
n
)
=
(
p
1
−
1
)
p
1
k
1
−
1
⋯
(
p
r
−
1
)
p
r
k
r
−
1
{\displaystyle \varphi (n)=(p_{1}-1)p_{1}^{k_{1}-1}\cdots (p_{r}-1)p_{r}^{k_{r}-1}}
Задња формула је Ојлеров производ , и често се записује као
φ
(
n
)
=
n
∏
p
|
n
(
1
−
1
p
)
{\displaystyle \varphi (n)=n\prod _{p|n}\left(1-{\frac {1}{p}}\right)}
а производ узима само вредности различитих простих бројева
p
{\displaystyle p}
n
{\displaystyle n}
φ
(
36
)
=
φ
(
3
2
2
2
)
=
36
(
1
−
1
3
)
(
1
−
1
2
)
=
36
⋅
2
3
⋅
1
2
=
12
{\displaystyle \varphi (36)=\varphi \left(3^{2}2^{2}\right)=36\left(1-{\frac {1}{3}}\right)\left(1-{\frac {1}{2}}\right)=36\cdot {\frac {2}{3}}\cdot {\frac {1}{2}}=12}
Речима, ово значи да су различити прости фактори броја 36 бројеви 2 и 3; половина тридесет и шест целих бројева од 1 до 36 су дељиви са 2, што оставља осамнаест; трећина њих је дељиво са 3, што оставља дванаест узајамно простих са 36. А ових 12 бројева су: 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, и 35.
ϕ
(
n
)
{\displaystyle \phi (n)}
+0
+1
+2
+3
+4
+5
+6
+7
+8
+9
0+
1
1
2
2
4
2
6
4
6
10+
4
10
4
12
6
8
8
16
6
18
20+
8
12
10
22
8
20
12
18
12
28
30+
8
30
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
Број
φ
(
n
)
{\displaystyle \varphi (n)}
цикличне групе
C
n
{\displaystyle C_{n}}
C
n
{\displaystyle C_{n}}
подгрупу и подгрупе од
C
n
{\displaystyle C_{n}}
C
d
{\displaystyle C_{d}}
d дели n (што се записује као
d
|
n
{\displaystyle d|n}
∑
d
∣
n
φ
(
d
)
=
n
{\displaystyle \sum _{d\mid n}\varphi (d)=n}
где сума пролази кроз све позитивне делиоце d од n .
Сада можемо да искористимо Мебијусову инверзиону формулу да инвертујемо ову суму и добијемо још једну формулу за
φ
(
n
)
{\displaystyle \varphi (n)}
φ
(
n
)
=
∑
d
∣
n
d
⋅
μ
(
n
/
d
)
{\displaystyle \varphi (n)=\sum _{d\mid n}d\cdot \mu (n/d)}
где је
μ
{\displaystyle \mu }
Мебијусова функција дефинисана за позитивне целе бројеве.
Према Ојлеровој теореми , ако су a и n узајамно прости, то јест, нзд (a , n ) = 1, тада
a
φ
(
n
)
≡
1
mod
n
.
{\displaystyle a^{\varphi (n)}\equiv 1\mod n.}
Ово следи из Лагранжове теореме и чињенице да a припада мултипликативној групи
Z
/
n
Z
{\displaystyle \mathbb {Z} /n\mathbb {Z} }
акко је a узајамно просто са n .
Две генераторне функције представљене овде су обе последице чињенице да
∑
d
|
n
φ
(
d
)
=
n
.
{\displaystyle \sum _{d|n}\varphi (d)=n.}
Дирехлеов ред са
φ
{\displaystyle \varphi }
n ) је
∑
n
=
1
∞
φ
(
n
)
n
s
=
ζ
(
s
−
1
)
ζ
(
s
)
.
{\displaystyle \sum _{n=1}^{\infty }{\frac {\varphi (n)}{n^{s}}}={\frac {\zeta (s-1)}{\zeta (s)}}.}
Ово се изводи на следећи начин:
ζ
(
s
)
∑
n
=
1
∞
φ
(
n
)
n
s
=
∑
n
=
1
∞
(
∑
d
|
n
φ
(
d
)
)
1
n
s
=
∑
n
=
1
∞
n
n
s
=
ζ
(
s
−
1
)
,
{\displaystyle \zeta (s)\sum _{n=1}^{\infty }{\frac {\varphi (n)}{n^{s}}}=\sum _{n=1}^{\infty }\left(\sum _{d|n}\varphi (d)\right){\frac {1}{n^{s}}}=\sum _{n=1}^{\infty }{\frac {n}{n^{s}}}=\zeta (s-1),}
где је
ζ
(
s
)
{\displaystyle \zeta (s)}
Риманова зета функција .
Генераторна функција Ламберовог реда је
∑
n
=
1
∞
φ
(
n
)
q
n
1
−
q
n
=
q
(
1
−
q
)
2
{\displaystyle \sum _{n=1}^{\infty }{\frac {\varphi (n)q^{n}}{1-q^{n}}}={\frac {q}{(1-q)^{2}}}}
што конвергира за |q |<1.
Ово следи из
∑
n
=
1
∞
φ
(
n
)
q
n
1
−
q
n
=
∑
n
=
1
∞
φ
(
n
)
∑
r
≥
1
q
r
n
{\displaystyle \sum _{n=1}^{\infty }{\frac {\varphi (n)q^{n}}{1-q^{n}}}=\sum _{n=1}^{\infty }\varphi (n)\sum _{r\geq 1}q^{rn}}
што је
∑
k
≥
1
q
k
∑
n
|
k
φ
(
n
)
=
∑
k
≥
1
k
q
k
=
q
(
1
−
q
)
2
.
{\displaystyle \sum _{k\geq 1}q^{k}\sum _{n|k}\varphi (n)=\sum _{k\geq 1}kq^{k}={\frac {q}{(1-q)^{2}}}.}
Раст
φ
(
n
)
{\displaystyle \varphi (n)}
n је интересантно питање, јер је први утисак добијен на основу малих n да је
φ
(
n
)
{\displaystyle \varphi (n)}
n је унеколико нетачан. Асимптотски имамо
n
1
−
ϵ
<
φ
(
n
)
<
n
{\displaystyle \,n^{1-\epsilon }<\varphi (n)<n}
за свако дато
ϵ
>
0
{\displaystyle \epsilon >0}
n
>
N
(
ϵ
)
{\displaystyle n>N(\epsilon )}
φ
(
n
)
/
n
{\displaystyle \,\varphi (n)/n}
можемо из горње формуле да добијемо, као производ фактора
1
−
p
−
1
{\displaystyle 1-p^{-1}\,}
изнад простих бројева p који деле n . Стога вредности n које одговарају посебно малим вредностима односа су они n који су производ почетног сегмента низа простих бројева. Из Теореме простих бројева се може показати да се константа ε у горњој формули може заменити са
C
log
log
n
/
log
n
{\displaystyle C\,\log \log n/\log n}
φ
{\displaystyle \varphi }
n у смислу просека:
1
n
2
∑
k
=
1
n
φ
(
k
)
=
3
π
2
+
O
(
log
n
n
)
{\displaystyle {\frac {1}{n^{2}}}\sum _{k=1}^{n}\varphi (k)={\frac {3}{\pi ^{2}}}+{\mathcal {O}}\left({\frac {\log n}{n}}\right)}
где је велико O Ландауов симбол . Ово такође значи да је вероватноћа да ће два позитивна цела броја случајно изабрана из {1, 2, ..., n } бити релативно прости тежи
6
/
π
2
{\displaystyle 6/\pi ^{2}}
n тежи бесконачности.
φ
(
n
m
)
=
n
m
−
1
φ
(
n
)
{\displaystyle \;\varphi \left(n^{m}\right)=n^{m-1}\varphi (n)}
m
≥
1
{\displaystyle m\geq 1}
∑
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
)
{\displaystyle \sum _{1\leq k\leq n \atop (k,n)=1}\!\!k={\frac {1}{2}}n\varphi (n)}
n
>
1
{\displaystyle \;n>1}
∑
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
⌋
{\displaystyle \sum _{k=1}^{n}{\frac {\varphi (k)}{k}}=\sum _{k=1}^{n}{\frac {\mu (k)}{k}}\left\lfloor {\frac {n}{k}}\right\rfloor }
∑
k
=
1
n
k
φ
(
k
)
=
O
(
n
)
{\displaystyle \sum _{k=1}^{n}{\frac {k}{\varphi (k)}}={\mathcal {O}}(n)}
∑
k
=
1
n
1
φ
(
k
)
=
O
(
log
(
n
)
)
{\displaystyle \sum _{k=1}^{n}{\frac {1}{\varphi (k)}}={\mathcal {O}}(\log(n))}
∑
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),}
где је
m
>
1
{\displaystyle m>1}
ω
(
m
)
{\displaystyle \omega (m)}
m
{\displaystyle m}
n и релативно простих са m .)
Неке неједнакости које укључују
φ
{\displaystyle \varphi }
φ
(
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}}}}}
Ојлерова константа ,
φ
(
n
)
≥
n
2
{\displaystyle \varphi (n)\geq {\sqrt {\frac {n}{2}}}}
n > 0,и
φ
(
n
)
≥
n
{\displaystyle \varphi (n)\geq {\sqrt {n}}}
n > 6.За прост n , јасно је да
φ
(
n
)
=
n
−
1
{\displaystyle \varphi (n)=n-1}
n имамо
φ
(
n
)
≤
n
−
n
{\displaystyle \varphi (n)\leq n-{\sqrt {n}}}
За све
n
>
1
{\displaystyle n>1}
0
<
φ
(
n
)
n
<
1
{\displaystyle 0<{\frac {\varphi (n)}{n}}<1}
За случајно велики n, ове границе се и даље не могу побољшати, или учинити прецизнијим:
lim inf
φ
(
n
)
n
=
0
and
lim sup
φ
(
n
)
n
=
1.
{\displaystyle \liminf {\frac {\varphi (n)}{n}}=0{\mbox{ and }}\limsup {\frac {\varphi (n)}{n}}=1.}
Milton Abramowitz and Irene A. Stegun, Handbook of Mathematical Functions,. Dover Publications, New York. 1964. ISBN 978-0-486-61272-0 .. See paragraph 24.3.2. Eric Bach and Jeffrey Shallit, Algorithmic Number Theory, volume 1, 1996, MIT Press. ISBN 978-0-262-02405-1 ., see page 234 in section 8.8.
