Euler totient fonksiyonu

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

φ(n) fonksiyonun ilk 1000 değeri

Örneğin, ${\displaystyle \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, de kullanılır. Şöyle ki:

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

Örneğin, ${\displaystyle a^{4}-1}$, ${\displaystyle a=1,3,7,9}$ için sırasıyla ${\displaystyle 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 ${\displaystyle \varphi (1)=1}$ ve eğer p bir asal sayıysa ${\displaystyle \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 ${\displaystyle \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, yararlanılırsa göürülür ki, AxB ve C arasında eşleme olur.) Yani, ${\displaystyle \varphi }$ fonksiyonunun değeri aritmetiğin temel teoremi kullanılarak hesaplanabilir. Öyleyse,

${\displaystyle n=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}}$

için

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

${\displaystyle \varphi (n)=n\cdot \prod _{p|n}\left(1-{\frac {1}{p}}\right)}$

şeklinde yazılır.

Hesaplama Örneği

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

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ü

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

Fonksiyonun Özellikleri

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

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

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

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

Bu durum Lagrange'ın teoremini ve anın ${\displaystyle \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

${\displaystyle \sum _{d|n}\varphi (d)=n.}$

nın sonucudur.

${\displaystyle \varphi }$(n)yi içeren bir Dirichlet Serisi

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

${\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)}$

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

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

${\displaystyle \sum _{h=1}^{\infty }\left(\sum _{d|h}\varphi (d)\right){\frac {1}{h^{s}}}=}$${\displaystyle \sum _{h=1}^{\infty }{\frac {h}{h^{s}}}}$

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

Lambert serisi fonksiyonu,

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

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

${\displaystyle \sum _{k\geq 1}q^{k}\sum _{n|k}\varphi (n)=\sum _{k\geq 1}kq^{k}={\frac {q}{(1-q)^{2}}}.}$

Fonksiyonun Büyümesi

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

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

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

Aslında

${\displaystyle \,\varphi (n)/n,}$

ele alınırsa,

${\displaystyle 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:

${\displaystyle C\,\log \log n/\log n.}$

${\displaystyle \varphi }$ de ortalama olarak ne yakındır.

${\displaystyle {\frac {1}{n^{2}}}\sum _{k=1}^{n}\varphi (k)={\frac {3}{\pi ^{2}}}+{\mathcal {O}}\left({\frac {\log n}{n}}\right)}$

Yani

${\displaystyle \{1,2,\ldots ,n\}}$ndan rastgele seçilen iki pozitif sayının aralarında asal olma olasılığı n sonsuza yaklaşırken ${\displaystyle {\frac {6}{\pi ^{2}}}}$a yaklaşır. Bununla ilgili bir sonuç da,

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

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

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

${\displaystyle \varphi }$ fonksiyonunu içeren bazı eşitsizlikler:

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

${\displaystyle \varphi (n)\geq {\sqrt {\frac {n}{2}}}}$ n için > 0,

ve

${\displaystyle \varphi (n)\geq {\sqrt {n}}{\text{ for }}n>6.}$

n asal sayısı için, açıkça ${\displaystyle \varphi (n)=n-1}$.

n birleşik sayısı için

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

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

${\displaystyle \varphi }$ fonksiyonu ile ${\displaystyle \sigma }$ fonksiyonunu birleştiren birkaç eşitsizlik:

${\displaystyle {\frac {6n^{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

• ; (1964), Handbook of Mathematical Functions, New York: Dover Publications, ISBN  . See paragraph 24.3.2.

• ; (1996), Algorithmic Number Theory, 1, Cambridge, MA: MIT Press, ISBN  . See page 234 in section 8.8.

• Ford, K. (1999), "The number of solutions of φ(x) = m", , 150 (1), ss. 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)), 1 Mayıs 2009 tarihinde kaynağından , erişim tarihi: 29 Nisan 2009 .