φ(n)
Asal çarpanlar
Aralarında asal payı
Bölenler

          Göster

          Euler totient fonksiyonu hakkında daha fazlası

          Euler totient hesaplayıcı

          1'den 12'ye kadar olan sayılardan yalnızca 1, 5, 7 ve 11'in 12 ile ortak böleni yoktur, bu yüzden φ(12) = 4. Euler totient fonksiyonu her n için bu aralarında asal sayıları sayar. 10^18'e kadar bir sayı girerek φ(n)'yi asal çarpanları ve açıkça yazılmış çarpım formülüyle alın, 1'den n'ye kadar sayıları aralarında asal olanlar vurgulanmış hâlde görün, Euler teoremini kontrol edin, tek seferde 100.000'e kadar sayı için φ(k)'yi çizin ya da verilen bir φ(n) değerine sahip her n'yi bulun. 10^18'e kadar bir n tam sayısı girin veya çözümlü bir örnek seçin. Kutucuklar φ(n)'yi, n'nin asal çarpanlarını, 1'den n'ye kadar olan sayılardan n ile aralarında asal olanların payını ve bölen sayısını gösterir; adımlar çarpım formülünü sizin sayılarınızla yazar. n = 500'e kadar 1'den n'ye kadar olan sayılar çizilir: n ile aralarında asal olanlar dolu, diğerleri n ile paylaştıkları en küçük asalın rengindedir. Bir sayının n ile EBOB'unu görmek için üzerine gelin, Euler teoreminde a olarak kullanmak için tıklayın. Grafik, bir sınıra kadar her k için φ(k)'yi gösterir; o sayıyı açmak için bir noktaya tıklayın. Ters, φ(n) = m olan her n'yi listeler; açmak için birine tıklayın.

          Nasıl çalışır

          1. 10^18'e kadar bir n tam sayısı girin veya φ(60), bir RSA modülü ya da Carmichael sayısı 561 gibi çözümlü bir örnek seçin.
          2. φ(n)'yi, asal çarpanları ve sizin sayılarınızla çarpım formülünü okuyun. 500'e kadar, 1'den n'ye kadar olan sayıların n ile EBOB'unu görmek için üzerlerine gelin ve Euler teoremini denemek için birine tıklayın.
          3. 100.000'e kadar her k için φ(k)'yi görmek üzere Grafik'e, φ(n) = m olan her n'yi listelemek için Ters'e geçin.

          φ(n) nasıl hesaplanır

          n'yi asal çarpanlarına ayırın ve n'yi, onu bölen her p asalı için (1 − 1/p) ile çarpın. 60 = 2² × 3 × 5 için bu 60 × 1/2 × 2/3 × 4/5 = 16 eder. Silmek de aynı sayıyı verir: 60 sayının 30'u çifttir; 30 tek sayının 10'u 3'ün katıdır; kalan 20 sayının 4'ü 5'in katıdır ve geriye 16 sayı kalır. Bir asalın kuvveti için formül φ(p^k) = p^(k−1)(p − 1) olur ve değerler çarpılır: φ(60) = 2 × 2 × 4. Zor olan çarpanlara ayırmaktır. Hesaplayıcı deneme bölmesi, bir Miller–Rabin asallık testi ve Pollard'ın rho yöntemini kullanır; böylece iki 9 basamaklı asalın 18 basamaklı çarpımı bile saniyenin küçük bir kesrini alır.

          Totient fonksiyonu nerede kullanılır

          φ(n), 0 ile 1 arasında zaten sadeleşmiş olan k/n kesirlerini, n saatlik bir kadranda ibreyi her saatten geçiren adım uzunluklarını (12 saatlik bir kadranda 1, 5, 7 ve 11) ve mod n'ye göre tersi olan sayıları sayar. Euler, n ile aralarında asal her a için a^φ(n) ≡ 1 (mod n) olduğunu kanıtladı ve RSA şifrelemesi buna dayanır: n = 3233 = 61 × 53 için φ(n) = 60 × 52 = 3.120'dir ve açık üs 17'nin özel eşi 2.753'tür, çünkü 17 × 2.753 = 15 × 3.120 + 1.

          Sık sorulan sorular

          Euler totient fonksiyonu nedir?

          φ(n), 1'den n'ye kadar olan ve n ile 1'den başka ortak böleni olmayan tam sayıların sayısıdır. φ(9) = 6'dır, çünkü 1, 2, 4, 5, 7 ve 8, 9 ile aralarında asaldır; 3, 6 ve 9 ise 3 çarpanını paylaşır. Geleneksel olarak φ(1) = 1 kabul edilir. Euler fonksiyonu 1760'larda inceledi; Gauss 1801'de ona φ simgesini, James Joseph Sylvester de 1879'da İngilizce totient adını verdi.

          Bir asal sayının φ değeri nedir?

          p − 1'dir, çünkü 1'den p − 1'e kadar her sayı asal bir p ile aralarında asaldır; yani φ(97) = 96. Bir asalın kuvveti için φ(p^k) = p^k − p^(k−1)'dir, çünkü onunla ortak böleni olanlar yalnızca p'nin katlarıdır: φ(81) = 81 − 27 = 54.

          Euler teoremi ne söyler?

          a ile n aralarında asalsa, a^φ(n) sayısının n'ye bölümünden kalan 1'dir. n = 60 ve a = 7 için: φ(60) = 16 ve 7^16 ≡ 1 (mod 60). Fermat'nın küçük teoremi, n'nin asal olduğu durumdur. Çoğu zaman daha küçük bir üs de yeter: 7^4 = 2.401 = 40 × 60 + 1. n ile aralarında asal her a için işe yarayan en küçük üs Carmichael fonksiyonu λ(n)'dir; 60 için bu değer 4'tür.

          İki sayının totient değeri aynı olabilir mi?

          Evet, genellikle birden fazla sayınınki aynıdır: n = 35, 39, 45, 52, 56, 70, 72, 78, 84 ve 90 için φ(n) = 24. Bazı çift sayılar hiçbir zaman φ'nin değeri olmaz, bunların en küçüğü 14'tür; 1'den büyük hiçbir tek sayı da olmaz, çünkü φ(n), n = 3'ten itibaren çifttir. Robert Carmichael 1907'de hiçbir değerin tam olarak bir kez alınmadığını öne sürdü. Bu hâlâ kanıtlanmadı ve Kevin Ford 1998'de bir istisnanın 10^(10^10)'dan büyük olması gerektiğini gösterdi.

          Ne kadar büyük bir sayı girebilirim?

          10^18'e kadar herhangi bir tam sayı. Hesaplayıcı onu tarayıcınızda kesin tam sayı aritmetiğiyle çarpanlarına ayırır; böylece φ(10^18) = 4 × 10^17 ve φ(999.999.866.000.004.473) = 999.999.864.000.004.608 son basamağına kadar doğru çıkar. 1'den n'ye kadar sayılar 500'e kadar çizilir, grafik 100.000'e kadar gider ve ters işlem 10^10'a kadar değerler için çalışır.

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

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

          Editöre Git