Totient

frame|sağ|φ(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 \varphi 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, 36nın asal çarpanları 2 ve 3tü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: küçükresim|420px|sağ| İ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 Cnnin olası generatörlerine eşittir. Bu nedenleCnin her elemanı, bir dairesel altgrup oluşturur. Cnnin algrupları Cd 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 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, n) = 1, : 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 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|<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) (herhangi bir ε > 0 ve n > N(ε) için) Aslında :\,\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 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 ot| 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, γ 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 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 min varolmadığına inanılır. == Kaynakça == * . See paragraph 24.3.2. * . See page 234 in section 8.8. * . * . Kategori:Sayılar teorisi Kategori:Çarpım fonksiyonları