Totient

Vikipedi, özgür ansiklopedi

φ(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.

Konu başlıkları

1 Totient fonksiyonunun hesaplanması
- 1.1 Hespalama Örneği
2 Fonksiyonun Bazı Değerleri
3 Fonksiyonun Özellikleri
4 Formül Geliştirilmesi
5 Fonksiyonun Büyümesi
6 Euler Totient Fonksiyonu'nu İçeren Diğer Formüller
7 Eşitsizlikler
8 Ford'un Teoremi
9 Referanslar

[değiştir] 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.

[değiştir] Hespalama Ö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.

[değiştir] Fonksiyonun Bazı Değerleri

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

İlk 100 değerin grafike edilmesi

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

[değiştir] 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).

[değiştir] 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}.$

[değiştir] 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)$

[değiştir] 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.)

[değiştir] 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 $σ$ fonksiyonunu birleştiren birkaç eşitsizlik:

$\frac {6 n^2}{\pi^2} < \varphi(n) \sigma(n) < n^2 \mbox{ için } n>1.$

[değiştir] 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.

[değiştir] 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, Moritanya .

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 .

Bu sayfa, İngilizce Euler's totient function maddesinden çevrilmektedir.
Siz de yardım etmek istiyorsanız ya da çeviri yarıda kalmışsa, çalışmaya katılan kişilerle iletişime geçip, sayfanın durumunu onlara sorabilirsiniz.
Sayfanın geçmişine baktığınızda, sayfa üzerinde çalışma yapanları görebilirsiniz.

Totient

Vikipedi, özgür ansiklopedi

Konu başlıkları

[değiştir] Totient fonksiyonunun hesaplanması

[değiştir] Hespalama Örneği

[değiştir] Fonksiyonun Bazı Değerleri

[değiştir] Fonksiyonun Özellikleri

[değiştir] Formül Geliştirilmesi

[değiştir] Fonksiyonun Büyümesi

[değiştir] Euler Totient Fonksiyonu'nu İçeren Diğer Formüller

[değiştir] Eşitsizlikler

[değiştir] Ford'un Teoremi

[değiştir] Referanslar

Görünüm

Kişisel aletler

gezinti

katılım

Ara

Araçlar

Diğer diller

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

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

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