Totient

φ(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 sayı sayısını belirten fonksiyondur. Genellikle Euler Totient ya da Euler'in Totienti olarak adlandırılan Totient, İsveçli matematikçi Leonhard Euler tarafından yaratılmıştır. Totient fonksiyonu, Yunan harflerinden phi($\varphi$) ile simgelendiği için Phi fonksiyonu olarak da anılabilir.

Örneğin, $\varphi$(8) = 4 zira 8 ile dört sayı asaldır: 1, 3, 5 ve 7.

Euler fonksiyonu, Euler'in teoremininde de kullanılır. Şöyle ki:

$a^{\varphi(n)}\equiv1\pmod{n}$

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, 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, Çin Kalan Teoremi'nden 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. Eğer

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

Öyleyse

$\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 sayı bölenleri 2 ve 3'tür. 36'nın yarısı olan 18 tane sayı iki ile bölünür, dolayısıyla 36 ile aralarında asal değildir. Kalan 18 sayının da 3te 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:

İlk 100 değerin grafiğe dökümü

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

Fonksiyonun Özellikleri

$\varphi(n)$ sayısı aynı zamanda dairesel grup olan C_nnin olası generatörlerine eşittir. Bu nedenleC_nin her elemanı, bir dairesel altgrup oluşturur. C_nnin algrupları C_d formundadır, eğer d böler n (d | n şeklinde yazılır). Böylece

$\sum_{d\mid n}\varphi(d)=n$

Buradaki toplam nnin tüm d positif 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)$

öyle ki μ pozitif tamsayılarda tanımlanan Möbius fonksiyonudur.

Euler'in teoremine göre, eğer a ile n aralarında asallarsa, bu demektir ki, ebob(a, n) = 1, yani

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

Bu durum Lagrange'ın teoremini ve anın $\mathbb{Z}/n\mathbb{Z}$nin mod n'e göre tamsayı 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|<1 için ıraksar.

Bu durumun nedeni

$\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üçüknler için $\varphi(n)$in nden küçük olacağı düşüncesi tam olarak doğru değildir. Asimptotik olarak,

$\,n^{1-\varepsilon}<\varphi(n)<n$

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

Aslnda

$\,\varphi(n)/n,$

ele alınırsa,

$1-p^{-1}\,$

yazılabilir. p|ni 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 ne 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 positif 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) min asal sayı çarpanlarını ifade eder. (Bu formül nden 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} < \varphi(n) \sigma(n) < n^2 \mbox{ için } n>1.$

Ford'un Teoremi

Ford, her k ≥ 2 tamsayı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 min varolmadığına inanılır.

Referanslar

• Abramowitz, M.; Stegun, I. A. (1964), Handbook of Mathematical Functions, New York: Dover Publications, ISBN 0-486-61272-4 . See paragraph 24.3.2.

• Bach, E.; Shallit, J. (1996), Algorithmic Number Theory, 1, Cambridge, MA: MIT Press, ISBN 0-262-02405-5 . See page 234 in section 8.8.

• Ford, K. (1999), "The number of solutions of φ(x) = m", Annals of Mathematics 150 (1): 283–311, doi:10.2307/121103, 1715326 .

• Schramm, Wolfgang (2008), "The Fourier transform of functions of the greatest common divisor", Electronic Journal of Combinatorial Number Theory A50 (8(1)), http://www.integers-ejcnt.org/vol8.html .