Euler totient fonksiyonu açıklaması

1'den 10'a kadar sayıları yazın ve 10 ile ortak böleni olan her birini silin. Dört sayı kalır: 1, 3, 7 ve 9. Bu sayı, φ(10) = 4, Euler totient fonksiyonudur; kesirlerden ve saatlerden çevrim içi ödemeleri koruyan şifrelemeye kadar sayılar teorisinin en çok kullanılan fonksiyonlarından biridir.

1'den 30'a kadar sayılar bir ızgarada, 30 ile aralarında asal olan sekizi dolu; φ(30) = 30 × 1/2 × 2/3 × 4/5 = 8 formülü ve asalların bir doğru üzerinde durduğu bir φ(k) grafiği
1'den 30'a kadar sayılar bir ızgarada, 30 ile aralarında asal olan sekizi dolu; φ(30) = 30 × 1/2 × 2/3 × 4/5 = 8 formülü ve asalların bir doğru üzerinde durduğu bir φ(k) grafiği

Aralarında asal sayıları saymak

En büyük ortak bölenleri 1 olan iki sayı aralarında asaldır. φ(n), 1'den n'ye kadar EBOB(k, n) = 1 olan k'leri sayar: φ(9) = 6, φ(10) = 4, φ(12) = 4 ve φ(1) = 1. Aynı sayı birçok yerde karşımıza çıkar. 0 ile 1 arasında zaten sadeleşmiş k/n kesirlerinin sayısıdır, n saatlik bir kadranda ibreyi her saatten geçiren adım uzunluklarının sayısıdır ve mod n'ye göre tersi olan, dolayısıyla k × x ≡ 1 (mod n) denkleminin çözülebildiği k'lerin sayısıdır.

Çarpım formülü

n'yi bölen asallar p₁, p₂ … ise φ(n) = n × (1 − 1/p₁) × (1 − 1/p₂) × … olur. Nedeni bir eleketir. Tüm sayıların yarısı çifttir, bu yüzden 2'nin katlarını çıkarmak 1 − 1/2 oranını bırakır; kalan sayıların üçte biri 3'ün katıdır ve bu böyle sürer. Çin kalan teoremine göre farklı asallara ait koşullar birbirinden bağımsızdır, bu yüzden oranlar basitçe çarpılır. 100 = 2² × 5² için bu 100 × 1/2 × 4/5 = 40 eder. İki özellik aynı sonucu başka bir biçimde verir: φ(p^k) = p^(k−1)(p − 1) ve m ile n aralarında asalsa φ(mn) = φ(m) φ(n); yani φ(100) = φ(4) × φ(25) = 2 × 20 = 40.

Euler teoremi

Fermat 1640'ta asal bir p ve p'ye bölünmeyen her a için a^(p−1) ≡ 1 (mod p) olduğunu fark etti. Euler genel hâlini kanıtladı ve 1763'te yayımladı: EBOB(a, n) = 1 olduğunda a^φ(n) ≡ 1 (mod n). Kanıt kısadır. n ile aralarında asal olan φ(n) sayıyı a ile çarpın; çarpımlar yine n ile aralarında asaldır ve mod n'ye göre hepsi farklıdır, yani aynı sayıların başka bir sıralamasıdır; iki çarpımı karşılaştırınca geriye a^φ(n) ≡ 1 kalır. Belirli bir a için işe yarayan en küçük üs onun mertebesidir ve her zaman φ(n)'yi böler; tüm a'lar için aynı anda işe yarayan en küçük üs Carmichael fonksiyonu λ(n)'dir. 561 = 3 × 11 × 17 için λ(561) = 80, 560'ı böler; bu yüzden 561 asal olmadığı hâlde 561 ile aralarında asal her a için a^560 ≡ 1 (mod 561) olur. 561 en küçük Carmichael sayısıdır ve Fermat testinin tek başına bir sayının asal olduğunu kanıtlayamamasının nedenidir.

Leonhard Euler, Jakob Emanuel Handmann’ın portresinde. Fermat’nın gözleminin genel biçimini 1763’te yayımladı: a ve n aralarında asal olduğunda a^φ(n) ≡ 1 (mod n).
Leonhard Euler, Jakob Emanuel Handmann’ın portresinde. Fermat’nın gözleminin genel biçimini 1763’te yayımladı: a ve n aralarında asal olduğunda a^φ(n) ≡ 1 (mod n).

Gauss'un bölen toplamı ve ortalama

n'nin d bölenleri üzerinden φ(d)'leri toplayın, her zaman yeniden n'yi elde edersiniz: 12 için φ(1) + φ(2) + φ(3) + φ(4) + φ(6) + φ(12) = 1 + 1 + 2 + 2 + 2 + 4 = 12. Gauss bunu 1801 tarihli Disquisitiones Arithmeticae'sinde kanıtladı; 1/12, 2/12 … 12/12 kesirlerini sadeleştirip paydalarına göre sıralayınca görülür. Ortalamada φ(k) yaklaşık 0,61 k'dir: φ(k)/k'nin ortalaması 6/π² ≈ 0,6079'a yaklaşır; bu aynı zamanda rastgele seçilen iki tam sayının aralarında asal olma olasılığıdır. φ(1) + … + φ(N) de 3N²/π²'ye yakındır. N = 1.000 için toplam 304.192'dir, 3N²/π² ≈ 303.964 ile karşılaştırıldığında.

Carl Friedrich Gauss, Christian Albrecht Jensen’in 1840 tarihli portresinde. a ≡ b (mod n) kongrüans gösterimini 1801’deki Disquisitiones Arithmeticae’de ortaya koydu.
Carl Friedrich Gauss, Christian Albrecht Jensen’in 1840 tarihli portresinde. a ≡ b (mod n) kongrüans gösterimini 1801’deki Disquisitiones Arithmeticae’de ortaya koydu.

Hiç ortaya çıkmayan değerler

φ(n), 3'ten itibaren her n için çifttir, çünkü n ile aralarında asal sayılar k ve n − k çiftleri hâlinde gelir. Her çift sayı da bir değer değildir: 14, 26, 34, 38 ve 50 hiç ortaya çıkmayan ilk sayılardır; 24 ise 35'ten 90'a on farklı sayının değeridir. Bunları bulmak sonlu bir aramadır, çünkü n'yi bölen her p asalı için p − 1, φ(n)'yi bölmelidir. 1907'de Robert Carmichael hiçbir değerin tam olarak bir kez alınmadığını öne sürdü. Kanıtı hatalıydı, iddia hâlâ açıktır ve herhangi bir istisna 10^(10^10)'dan büyük olmak zorundadır. D. H. Lehmer 1932'de bileşik bir n için φ(n)'nin n − 1'i bölüp bölemeyeceğini sordu; bilinen bir örnek yoktur.

RSA'da totient

RSA iki büyük p ve q asalı seçer ve n = pq ile bir e üssünü yayımlar. φ(n) = (p − 1)(q − 1) olduğundan, n'yi çarpanlarına ayırabilen herkes φ(n)'yi ve oradan e × d ≡ 1 (mod φ(n)) olan özel d üssünü hesaplayabilir; Euler teoremi de (m^e)^d ≡ m (mod n) olmasını sağlar. Ders kitabı örneğinde n = 3233 = 61 × 53, φ(n) = 3.120, e = 17 ve d = 2.753'tür. Birçok uygulama bunun yerine λ(n) = EKOK(p − 1, q − 1) kullanır; burada 780'dir ve daha küçük d = 413 değerini verir. 600 basamaklı bir RSA modülü için φ(n)'yi hesaplamak, onu çarpanlarına ayırmak kadar zordur: n ve φ(n)'den iki asal tek bir karekökle elde edilir.

Ron Rivest, Adi Shamir ve Len Adleman (soldan sağa)
Ron Rivest, Adi Shamir ve Len Adleman (soldan sağa)

Kendiniz keşfedin

Hesaplayıcıyı açın ve φ(n)'yi asal çarpanları ve formülüyle görmek için 10^18'e kadar herhangi bir n girin. 500'e kadar 1'den n'ye kadar sayılar çizilir; aralarında asal olanlar dolu, diğerleri n ile paylaştıkları en küçük asalın rengindedir, böylece çarpım formülü sayılabilen bir eleğe dönüşür. Euler teoremini denemek için bir a sayısı seçin, asalların φ(p) = p − 1 doğrusunda durduğu 100.000'e kadar φ(k)'yi görmek için Grafik'e, φ(n) = m olan her n'yi bulmak için Ters'e geçin.

Sık sorulan sorular

φ(1) neden 1'dir?

Çünkü EBOB(1, 1) = 1'dir: 1'den 1'e kadar olan tek sayı 1 ile aralarında asaldır. Bu kabul formüllerin de geçerli kalmasını sağlar; örneğin Gauss'un n'nin bölenleri üzerinden toplamı n = 1 için basitçe φ(1) = 1'dir.

φ, asal sayma fonksiyonuyla aynı mıdır?

Hayır. π(n), n'ye kadar olan asalları; φ(n) ise n'ye kadar olan ve n ile aralarında asal olan sayıları sayar. φ(10) = 4; 1, 3, 7 ve 9'u sayar, π(10) = 4 ise 2, 3, 5 ve 7'yi. Burada eşit olmaları tesadüftür: φ(12) = 4, ama π(12) = 5.

φ(n) ne kadar hızlı hesaplanabilir?

n ne kadar hızlı çarpanlarına ayrılabiliyorsa o kadar. Asal çarpanlar biliniyorsa birkaç çarpma yeter; bilinmiyorsa hızlı bir yöntem bilinmez ve RSA buna dayanır. 10^18'e kadar sayılar için çarpanlara ayırma tarayıcıda milisaniyeler sürer, yüzlerce basamaklı sayılar için yıllar sürebilir.

Hangi sayıların φ(n)'si n'ye göre en küçüktür?

Çok sayıda küçük asal çarpanı olan sayıların. φ(n)/n = (1 − 1/p₁)(1 − 1/p₂)… yalnızca n'yi hangi asalların böldüğüne bağlıdır, kuvvetlerine bağlı değildir: 2'nin her kuvveti için tam olarak 1/2'dir, 30 = 2 × 3 × 5 için ise 8/30, yaklaşık %27'dir. İlk 15 asalın çarpımı olan 614.889.782.588.491.410 için φ(n)/n ≈ %14'tür; bu, 10^18'e kadar tüm sayılar arasındaki en düşük değerdir.

Denemeye hazır mısınız?

PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.

Totient hesaplayıcıyı açın