Totient

**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 <math>\varphi</math> ile simgelendiği için **Fi fonksiyonu** olarak da anılabilir.

Örneğin, \varphi(10) = 4; zira 10 ile dört sayma sayısı, hem 10'dan küçüktür, hem de 10 ile arasında asaldır: 1, 3, 7 ve 9.

Euler fonksiyonu, Euler Fermat teoreminde de kullanılır. Şöyle ki:

a^{\varphi(n)}\equiv1\pmod{n}, *a* ile *n* aralarında asal ise. Dolayısıyla,
a^{\varphi(n)}-1, *n*'in bir tam katıdır.

Örneğin, a^4-1, a=1, 3, 7, 9 için sırasıyla 0, 80, 2400, 6560, *10*'un bir tam katıdır.

Totient fonksiyonu ayrıca RSA kriptografi sisteminde de kilit rol oynamaktadır.

## Totient fonksiyonunun hesaplanması
Fonksiyonun yukarıda verilen tanımına göre \varphi(1)=1 ve eğer p bir asal sayıysa \varphi(p^{k})=(p-1)p^{k-1}.
Bunun yanında, totient fonksiyonunun çarpım özelliği de vardır: *m* ve *n* aralarında asallarsa \varphi(mn)=\varphi(m)\varphi(n). (Bu yargının ispatının anahattı: *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, \varphi fonksiyonunun değeri aritmetiğin temel teoremi kullanılarak hesaplanabilir. Öyleyse,

n=p_1^{k_1}\cdots p_r^{k_r}

için

:\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

\varphi(n)=n\cdot\prod_{p|n}\left(1-\frac{1}{p}\right)

şeklinde yazılır.

### Hesaplama Örneği

\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.

## Fonksiyonun Bazı Değerleri

İlk birkaç değer aşağıdaki tabloda ve grafikte gösterilmiştir:

## Fonksiyonun Özellikleri
\varphi(n) sayısı aynı zamanda dairesel grup olan *C**n*nin olası generatörlerine eşittir. Bu nedenle *C**n*in her elemanı, bir dairesel altgrup oluşturur. *C**n*nin algrupları *C**d* formundadır, eğer *d* böler *n* (*d*&nbsp;|&nbsp;*n* şeklinde yazılır). Böylece

:\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 \varphi(n) için bir formül daha elde etmek için kullanabiliriz:

:\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*,&nbsp;*n*) = 1,

: a^{\varphi(n)} \equiv 1\mod n.\,

Bu durum Lagrange'ın teoremini ve *a*nın \mathbb{Z}/n\mathbb{Z}nin mod n'e göre tam sayı grubuna ait olmasını takip eder. (Ancak ve ancak *a* ile *n* aralarında asallarsa).

## Formül Geliştirilmesi

Burada gösterilen iki fonksiyon da

:\sum_{d|n} \varphi(d) = n.

nın sonucudur.

\varphi(*n*)yi içeren bir Dirichlet Serisi

:\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:

:\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)
:\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}
:\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}
:\sum_{h=1}^\infty \left(\sum_{d|h} \varphi(d) \right) \frac{1}{h^s} =\sum_{h=1}^\infty\frac{h}{h^s}
:\sum_{h=1}^\infty \frac{h}{h^s} = \zeta(s-1)

Lambert serisi fonksiyonu,

:\sum_{n=1}^{\infty} \frac{\varphi(n) q^n}{1-q^n}= \frac{q}{(1-q)^2}

öyle ki |*q*|\sum_{n=1}^{\infty} \frac{\varphi(n) q^n}{1-q^n} =
\sum_{n=1}^{\infty} \varphi(n) \sum_{r\ge 1} q^{rn}

yani

:
\sum_{k\ge 1} q^k \sum_{n|k} \varphi(n) =
\sum_{k\ge 1} k q^k = \frac{q}{(1-q)^2}.

## Fonksiyonun Büyümesi

\varphi(n)nin fonksiyon olarak büyümesi ilginç bir sorudur; çünkü küçük*n*ler için \varphi(n)in *n*den küçük olacağı düşüncesi tam olarak doğru değildir. Asimptotik olarak,

:\,n^{1-\varepsilon}

(herhangi bir ε > 0 ve *n* > *N*(ε) için)

Aslında

:\,\varphi(n)/n,

ele alınırsa,

: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.

\varphi de ortalama olarak *n*e yakındır.

:\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, \ldots , n \}ndan rastgele seçilen iki pozitif sayının aralarında asal olma olasılığı *n* sonsuza yaklaşırken \frac{6}{\pi^2}a yaklaşır. Bununla ilgili bir sonuç da,

:
\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ü \frac{6}{\pi^2} = \frac{1}{\zeta(2)}, formül bu şekilde de ifade edilebilir.

:
\frac{1}{n} \sum_{k=1}^n \frac{\varphi(k)}{k} = 
\frac{1}{\zeta(2)} + \mathcal{O}\left(\frac{\log n }{n}\right)


## Euler Totient Fonksiyonu'nu İçeren Diğer Formüller

* \;\varphi\left(n^m\right) = n^{m-1}\varphi(n) \text{ for } m\ge 1
* \text{herhangi } a, n > 1 \text{, öyle vardır ki} l \geq n \text{ öyledir ki } l|\varphi(a^n-1)
* \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)
* \sum_{d \mid n} \frac{\mu^2(d)}{\varphi(d)} = \frac{n}{\varphi(n)}
* \sum_{1\le k\le n \atop (k,n)=1}\!\!k = \frac{1}{2}n\varphi(n)\text{ for }n>1
* \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)
* \sum_{k=1}^n\frac{\varphi(k)}{k} = \sum_{k=1}^n\frac{\mu(k)}{k}\left\lfloor\frac{n}{k}\right\rfloor
* \sum_{k=1}^n\frac{k}{\varphi(k)} = \mathcal{O}(n)
* \sum_{k=1}^n\frac{1}{\varphi(k)} = \mathcal{O}(\log(n))
* \sum_{1\le k\le 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.)

## Eşitsizlikler

\varphi fonksiyonunu içeren bazı eşitsizlikler:

:
\varphi(n) > \frac {n} {e^\gamma\; \log \log n + \frac {3} {\log \log n}}
 *n* > 2 için, &gamma Euler sabiti iken,

:
\varphi(n) \ge \sqrt{\frac {n} {2} }
 *n* için > 0,

ve

:
\varphi(n) \ge \sqrt{n}\text{ for } n > 6.


*n* asal sayısı için, açıkça \varphi(n) = n-1.

*n* birleşik sayısı için
:
\varphi(n) \le 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:

:\liminf \frac{\varphi (n)}{n}=0 \mbox{ ve } \limsup \frac{\varphi (n)}{n}=1. 

\varphi fonksiyonu ile \sigma fonksiyonunu birleştiren birkaç eşitsizlik:

:
\frac {6 n^2}{\pi^2} 1.


## Ford'un Teoremi

Ford, her *k*&nbsp;≥&nbsp;2 tam sayısı için φ(*x*)&nbsp;=&nbsp;*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*&nbsp;=&nbsp;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.

## Kaynakça

* . See paragraph 24.3.2.

* . See page 234 in section 8.8.

* .

* .