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