φ(n) fonksiyonun ilk 1000 değeri Totient (kısaca φ, n ) sayılar teorisinde , bir tam sayının o sayıdan daha küçük ve o sayı ile aralarında asal olan sayma sayı sayısını belirten fonksiyondur. Genellikle Euler Totient ya da Euler'in Totienti olarak adlandırılan Totient, İsviçreli matematikçi Leonhard Euler tarafından yaratılmıştır. Totient fonksiyonu, Yunan harflerinden
φ
{\displaystyle \varphi }
Fi fonksiyonu olarak da anılabilir.
Örneğin,
φ
(
10
)
=
4
{\displaystyle \varphi (10)=4}
Euler fonksiyonu, Euler Fermat teoreminde de kullanılır. Şöyle ki:
a
φ
(
n
)
≡
1
(
mod
n
)
{\displaystyle a^{\varphi (n)}\equiv 1{\pmod {n}}}
a ile n aralarında asal ise. Dolayısıyla,
a
φ
(
n
)
−
1
{\displaystyle a^{\varphi (n)}-1}
n' in bir tam katıdır.
Örneğin,
a
4
−
1
{\displaystyle a^{4}-1}
a
=
1
,
3
,
7
,
9
{\displaystyle a=1,3,7,9}
0
,
80
,
2400
,
6560
{\displaystyle 0,80,2400,6560}
10' un bir tam katıdır.
Totient fonksiyonu ayrıca RSA kriptografi sisteminde de kilit rol oynamaktadır.
Fonksiyonun yukarıda verilen tanımına göre
φ
(
1
)
=
1
{\displaystyle \varphi (1)=1}
φ
(
p
k
)
=
(
p
−
1
)
p
k
−
1
{\displaystyle \varphi (p^{k})=(p-1)p^{k-1}}
m ve n aralarında asallarsa
φ
(
m
n
)
=
φ
(
m
)
φ
(
n
)
{\displaystyle \varphi (mn)=\varphi (m)\varphi (n)}
A ,B ve C kümeleri sırasıyla m ,n ve mn ile aralarında asal ve modlarının kalan kümesi olsun. Bu durumda, Çinlilerin kalan teoreminden yararlanılırsa görülür ki, AxB ve C arasında eşleme olur.) Yani,
φ
{\displaystyle \varphi }
n
=
p
1
k
1
⋯
p
r
k
r
{\displaystyle n=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}}
için
φ
(
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}.}
Yukarıdaki formül bir Euler Çarpımı'dır ve genellikle
φ
(
n
)
=
n
⋅
∏
p
|
n
(
1
−
1
p
)
{\displaystyle \varphi (n)=n\cdot \prod _{p|n}\left(1-{\frac {1}{p}}\right)}
şeklinde yazılır.
φ
(
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}
Yani yazıyla ifade edersek, 36 'nın asal çarpanları 2 ve 3 'tür. 36' nın yarısı olan 18 tane sayı 2 ile bölünür, dolayısıyla 36 ile aralarında asal değildir. Kalan 18 sayının da 3'te biri 3 ile bölünür. Bu durumda 36 sayı içerisinde 36 ile aralarında asal olan sadece 12 sayı kalır.
İlk birkaç değer aşağıdaki tabloda ve grafikte gösterilmiştir:
İlk 100 değerin grafiğe dökümü
φ
(
n
)
{\displaystyle \varphi (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 C n C n C d d böler n (d | n şeklinde yazılır). Böylece
∑
d
∣
n
φ
(
d
)
=
n
{\displaystyle \sum _{d\mid n}\varphi (d)=n}
Buradaki toplam n nin tüm d pozitif bölenlerine kadar genişler.
Şimdi Möbius formülünü, bu toplamı değiştirmek ve
φ
(
n
)
{\displaystyle \varphi (n)}
φ
(
n
)
=
∑
d
∣
n
d
⋅
μ
(
n
d
)
{\displaystyle \varphi (n)=\sum _{d\mid n}d\cdot \mu \left({\frac {n}{d}}\right)}
Burada, μ pozitif tam sayılarda tanımlanan Möbius fonksiyonudur.
Euler'in teoremine göre, eğer a ile n aralarında asallarsa, yani ebob (a , n ) = 1,
a
φ
(
n
)
≡
1
mod
n
.
{\displaystyle a^{\varphi (n)}\equiv 1\mod n.\,}
Bu durum Lagrange'ın teoremini ve a nın
Z
/
n
Z
{\displaystyle \mathbb {Z} /n\mathbb {Z} }
a ile n aralarında asallarsa).
Burada gösterilen iki fonksiyon da
∑
d
|
n
φ
(
d
)
=
n
.
{\displaystyle \sum _{d|n}\varphi (d)=n.}
nın sonucudur.
φ
{\displaystyle \varphi }
n )yi içeren bir Dirichlet Serisi
∑
n
=
1
∞
φ
(
n
)
n
s
=
ζ
(
s
−
1
)
ζ
(
s
)
{\displaystyle \sum _{n=1}^{\infty }{\frac {\varphi (n)}{n^{s}}}={\frac {\zeta (s-1)}{\zeta (s)}}}
öyle ki ζ(s ) Rienmann Zeta Fonksiyonudur. Bunun ispatı aşağıda gösterildiği gibidir:
ζ
(
s
)
∑
f
=
1
∞
φ
(
f
)
f
s
=
(
∑
g
=
1
∞
1
g
s
)
(
∑
f
=
1
∞
φ
(
f
)
f
s
)
{\displaystyle \zeta (s)\sum _{f=1}^{\infty }{\frac {\varphi (f)}{f^{s}}}=\left(\sum _{g=1}^{\infty }{\frac {1}{g^{s}}}\right)\left(\sum _{f=1}^{\infty }{\frac {\varphi (f)}{f^{s}}}\right)}
(
∑
g
=
1
∞
1
g
s
)
(
∑
f
=
1
∞
φ
(
f
)
f
s
)
=
∑
h
=
1
∞
(
∑
f
g
=
h
1
⋅
φ
(
g
)
)
1
h
s
{\displaystyle \left(\sum _{g=1}^{\infty }{\frac {1}{g^{s}}}\right)\left(\sum _{f=1}^{\infty }{\frac {\varphi (f)}{f^{s}}}\right)=\sum _{h=1}^{\infty }\left(\sum _{fg=h}1\cdot \varphi (g)\right){\frac {1}{h^{s}}}}
∑
h
=
1
∞
(
∑
f
g
=
h
φ
(
g
)
)
1
h
s
=
∑
h
=
1
∞
(
∑
d
|
h
φ
(
d
)
)
1
h
s
{\displaystyle \sum _{h=1}^{\infty }\left(\sum _{fg=h}\varphi (g)\right){\frac {1}{h^{s}}}=\sum _{h=1}^{\infty }\left(\sum _{d|h}\varphi (d)\right){\frac {1}{h^{s}}}}
∑
h
=
1
∞
(
∑
d
|
h
φ
(
d
)
)
1
h
s
=
{\displaystyle \sum _{h=1}^{\infty }\left(\sum _{d|h}\varphi (d)\right){\frac {1}{h^{s}}}=}
∑
h
=
1
∞
h
h
s
{\displaystyle \sum _{h=1}^{\infty }{\frac {h}{h^{s}}}}
∑
h
=
1
∞
h
h
s
=
ζ
(
s
−
1
)
{\displaystyle \sum _{h=1}^{\infty }{\frac {h}{h^{s}}}=\zeta (s-1)}
Lambert serisi fonksiyonu,
∑
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}}}}
öyle ki |q |<1 için ıraksar.
Bu durumun nedeni
∑
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}}
yani
∑
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 ler için
φ
(
n
)
{\displaystyle \varphi (n)}
n den küçük olacağı düşüncesi tam olarak doğru değildir. Asimptotik olarak,
n
1
−
ε
<
φ
(
n
)
<
n
{\displaystyle \,n^{1-\varepsilon }<\varphi (n)<n}
(herhangi bir ε > 0 ve n > N (ε) için)
Aslında
φ
(
n
)
/
n
,
{\displaystyle \,\varphi (n)/n,}
ele alınırsa,
1
−
p
−
1
{\displaystyle 1-p^{-1}\,}
yazılabilir. p|n i sağlayan p asal sayıları için)
Asal sayı teoremi'nden εnin yerine aşağıdakinin yazılabileceği gösterilebilir:
C
log
log
n
/
log
n
.
{\displaystyle C\,\log \log n/\log n.}
φ
{\displaystyle \varphi }
n e yakındır.
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)}
Yani
{
1
,
2
,
…
,
n
}
{\displaystyle \{1,2,\ldots ,n\}}
n sonsuza yaklaşırken
6
π
2
{\displaystyle {\frac {6}{\pi ^{2}}}}
1
n
∑
k
=
1
n
φ
(
k
)
k
=
6
π
2
+
O
(
log
n
n
)
{\displaystyle {\frac {1}{n}}\sum _{k=1}^{n}{\frac {\varphi (k)}{k}}={\frac {6}{\pi ^{2}}}+{\mathcal {O}}\left({\frac {\log n}{n}}\right)}
ile gösterilir; çünkü
6
π
2
=
1
ζ
(
2
)
{\displaystyle {\frac {6}{\pi ^{2}}}={\frac {1}{\zeta (2)}}}
1
n
∑
k
=
1
n
φ
(
k
)
k
=
1
ζ
(
2
)
+
O
(
log
n
n
)
{\displaystyle {\frac {1}{n}}\sum _{k=1}^{n}{\frac {\varphi (k)}{k}}={\frac {1}{\zeta (2)}}+{\mathcal {O}}\left({\frac {\log n}{n}}\right)}
φ
(
n
m
)
=
n
m
−
1
φ
(
n
)
for
m
≥
1
{\displaystyle \;\varphi \left(n^{m}\right)=n^{m-1}\varphi (n){\text{ for }}m\geq 1}
herhangi
a
,
n
>
1
, öyle vardır ki
l
≥
n
öyledir ki
l
|
φ
(
a
n
−
1
)
{\displaystyle {\text{herhangi }}a,n>1{\text{, öyle vardır ki}}l\geq n{\text{ öyledir ki }}l|\varphi (a^{n}-1)}
Herhangi
a
>
1
ve
n
>
6
öyle vardır ki
4
⧸
|
n
öyledir ki
l
≥
2
n
öyledir ki
l
|
φ
(
a
n
−
1
)
{\displaystyle {\text{Herhangi }}a>1{\text{ ve }}n>6{\text{ öyle vardır ki }}4\not |n{\text{ öyledir ki }}l\geq 2n{\text{ öyledir ki }}l|\varphi (a^{n}-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
)
for
n
>
1
{\displaystyle \sum _{1\leq k\leq n \atop (k,n)=1}\!\!k={\frac {1}{2}}n\varphi (n){\text{ for }}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),}
Burada m > 1 bir pozitif tam sayıdır ve ω(m ) m in asal sayı çarpanlarını ifade eder. (Bu formül n den küçük ve m ile aralarında asal olan doğal sayıların sayısını gösterir.)
φ
{\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 > 2 için, &gamma Euler sabiti iken,
φ
(
n
)
≥
n
2
{\displaystyle \varphi (n)\geq {\sqrt {\frac {n}{2}}}}
n için > 0,ve
φ
(
n
)
≥
n
for
n
>
6.
{\displaystyle \varphi (n)\geq {\sqrt {n}}{\text{ for }}n>6.}
n asal sayısı için, açıkça
φ
(
n
)
=
n
−
1
{\displaystyle \varphi (n)=n-1}
n birleşik sayısı için
φ
(
n
)
≤
n
−
n
{\displaystyle \varphi (n)\leq n-{\sqrt {n}}}
Rastgele büyüklükteki n için, bu sınırlar halen geliştirilememeiştir ya da daha kesin olmak gerekirse:
lim inf
φ
(
n
)
n
=
0
ve
lim sup
φ
(
n
)
n
=
1.
{\displaystyle \liminf {\frac {\varphi (n)}{n}}=0{\mbox{ ve }}\limsup {\frac {\varphi (n)}{n}}=1.}
φ
{\displaystyle \varphi }
σ
{\displaystyle \sigma }
6
n
2
π
2
<
φ
(
n
)
σ
(
n
)
<
n
2
için
n
>
1.
{\displaystyle {\frac {6n^{2}}{\pi ^{2}}}<\varphi (n)\sigma (n)<n^{2}{\mbox{ için }}n>1.}
Ford, her k ≥ 2 tam sayısı için φ(x ) = m eşitliğinin tam olarak k sağlayanı bulunması durumunu sağlayan bir m sayısının bulunduğunu ispatladı. Ne yazık ki, k = 1 için herhangi bir m bulunamamıştır, Carmichal'ın Totient Fonksiyonu Konjektürü'ne göre, bu durumda böyle bir m in varolmadığına inanılır.
