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 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 $\phi$ ile simgelendiği için Fi fonksiyonu olarak da anılabilir.

Örneğin, $\phi (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^{\phi (n)}\equiv 1(\mathrm{mod}n)$, a ile n aralarında asal ise. Dolayısıyla, $a^{\phi (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 $\phi (1)=1$ ve eğer p bir asal sayıysa $\phi (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 $\phi (mn)=\phi (m)\phi (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, $\phi$ fonksiyonunun değeri aritmetiğin temel teoremi kullanılarak hesaplanabilir. Öyleyse,

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

için

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

$\phi (n)=n\cdot \prod _{p|n}(1-\frac{1}{p})$

şeklinde yazılır.

Hesaplama Örneği

$\phi (36)=\phi \left(3^2{2}^2\right)=36(1-\frac{1}{3})(1-\frac{1}{2})=36\cdot \frac{2}{3}\cdot \frac{1}{2}=12$

Yani yazıyla ifade edersek, 36Şablon:'nın asal çarpanları 2 ve 3Şablon:'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:

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

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

Fonksiyonun Özellikleri

$\phi (n)$ sayısı aynı zamanda dairesel grup olan C_nnin olası generatörlerine eşittir. Bu nedenle C_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}\phi (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 $\phi (n)$ için bir formül daha elde etmek için kullanabiliriz:

$\phi (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^{\phi (n)}\equiv 1modn.$

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}\phi (d)=n.$

nın sonucudur.

$\phi$(n)yi içeren bir Dirichlet Serisi

$\sum _{n=1}^{\mathrm{\infty }}\frac{\phi (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}^{\mathrm{\infty }}\frac{\phi (f)}{f^s}=\left(\sum _{g=1}^{\mathrm{\infty }}\frac{1}{g^s}\right)\left(\sum _{f=1}^{\mathrm{\infty }}\frac{\phi (f)}{f^s}\right)$

$\left(\sum _{g=1}^{\mathrm{\infty }}\frac{1}{g^s}\right)\left(\sum _{f=1}^{\mathrm{\infty }}\frac{\phi (f)}{f^s}\right)=\sum _{h=1}^{\mathrm{\infty }}(\sum _{fg=h}1\cdot \phi (g))\frac{1}{h^s}$

$\sum _{h=1}^{\mathrm{\infty }}(\sum _{fg=h}\phi (g))\frac{1}{h^s}=\sum _{h=1}^{\mathrm{\infty }}(\sum _{d|h}\phi (d))\frac{1}{h^s}$

$\sum _{h=1}^{\mathrm{\infty }}(\sum _{d|h}\phi (d))\frac{1}{h^s}=$$\sum _{h=1}^{\mathrm{\infty }}\frac{h}{h^s}$

$\sum _{h=1}^{\mathrm{\infty }}\frac{h}{h^s}=\zeta (s-1)$

Lambert serisi fonksiyonu,

$\sum _{n=1}^{\mathrm{\infty }}\frac{\phi (n)q^n}{1-q^n}=\frac{q}{(1-q{)}^2}$

öyle ki |q|<1 için ıraksar.

Bu durumun nedeni

$\sum _{n=1}^{\mathrm{\infty }}\frac{\phi (n)q^n}{1-q^n}=\sum _{n=1}^{\mathrm{\infty }}\phi (n)\sum _{r\ge 1}{q}^{rn}$

yani

$\sum _{k\ge 1}{q}^k\sum _{n|k}\phi (n)=\sum _{k\ge 1}k{q}^k=\frac{q}{(1-q{)}^2}.$

Fonksiyonun Büyümesi

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

$n^{1-\epsilon }<\phi (n)<n$

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

Aslında

$\phi (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.$

$\phi$ de ortalama olarak ne yakındır.

$\frac{1}{n^2}\sum _{k=1}^n\phi (k)=\frac{3}{{\pi }^2}+𝒪\left(\frac{\log n}{n}\right)$

Yani

$\{1,2,\dots ,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{\phi (k)}{k}=\frac{6}{{\pi }^2}+𝒪\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{\phi (k)}{k}=\frac{1}{\zeta (2)}+𝒪\left(\frac{\log n}{n}\right)$

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

• $\phi \left(n^m\right)=n^{m-1}\phi (n)\text{ for }m\ge 1$
• $\text{herhangi }a,n>1\text{, öyle vardır ki}l\ge n\text{ öyledir ki }l|\phi (a^n-1)$
• $\text{Herhangi }a>1\text{ ve }n>6\text{ öyle vardır ki }4|n\text{ öyledir ki }l\ge 2n\text{ öyledir ki }l|\phi (a^n-1)$
• $\sum _{d\mid n}\frac{{\mu }^2(d)}{\phi (d)}=\frac{n}{\phi (n)}$
• $\sum _{\genfrac{}{}{0ex}{}{1\le k\le n}{(k,n)=1}}k=\frac{1}{2}n\phi (n)\text{ for }n>1$
• $\sum _{k=1}^n\phi (k)=\frac{1}{2}(1+\sum _{k=1}^n\mu (k){\lfloor \frac{n}{k}\rfloor }^2)$
• $\sum _{k=1}^n\frac{\phi (k)}{k}=\sum _{k=1}^n\frac{\mu (k)}{k}\lfloor \frac{n}{k}\rfloor$
• $\sum _{k=1}^n\frac{k}{\phi (k)}=𝒪(n)$
• $\sum _{k=1}^n\frac{1}{\phi (k)}=𝒪(\log (n))$
• $\sum _{\genfrac{}{}{0ex}{}{1\le k\le n}{(k,m)=1}}1=n\frac{\phi (m)}{m}+𝒪\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

$\phi$ fonksiyonunu içeren bazı eşitsizlikler:

$\phi (n)>\frac{n}{e^{\gamma }\log \log n+\frac{3}{\log \log n}}$ n > 2 için, &gamma Euler sabiti iken,

$\phi (n)\ge \sqrt{\frac{n}{2}}$ n için > 0,

ve

$\phi (n)\ge \sqrt{n}\text{ for }n>6.$

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

n birleşik sayısı için

$\phi (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:

$\mathrm{lim\; inf}\frac{\phi (n)}{n}=0\text{ ve }\mathrm{lim\; sup}\frac{\phi (n)}{n}=1.$

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

$\frac{6n^2}{{\pi }^2}<\phi (n)\sigma (n)<n^2\text{ 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

• Şablon:Kaynak. See paragraph 24.3.2.

• Şablon:Kaynak. See page 234 in section 8.8.

• Şablon:Kaynak.

• Şablon:Kaynak.