Euler Phi (Totient) Fonksiyonu Hesaplayıcı

Euler Phi (Totient) Fonksiyonu Hesaplayıcı

Popüler AI Skill PRO

Hesaplamaya Girin

Formül

φ(n)=n∏p|n(1−1p)\varphi\!\left(\text{n}\right) = \text{n} \prod_{p \mid \text{n}} \left(1 - \frac{1}{p}\right)
Kullanım istatistikleri

Reklam

Sonuç

Euler Phi Fonksiyonu φ(13)
12
ile aralarında asal tam sayılar 13 in [1, n]
n değeri 13
Farklı asal çarpanlar 13

Bu sayfadaki bir hatayı bildir

Euler Phi Fonksiyonu Nedir?

\(\varphi(n)\) ile gösterilen Euler phi fonksiyonu (totient fonksiyonu olarak da bilinir), 1'den n'ye kadar olan pozitif tam sayılardan kaç tanesinin n ile 1 dışında ortak böleni olmadığını sayar; yani n ile aralarında asal olan tam sayıların sayısını verir. Örneğin \(\varphi(9) = 6\)'dır, çünkü 1, 2, 4, 5, 7 ve 8 sayılarının hepsi 9 ile aralarında asaldır. Bu fonksiyon sayılar teorisinin temel taşlarından biridir ve kriptografide sıkça karşımıza çıkar; en bilinen örneği, anahtar üretiminde kullanılan modüler ters hesabını \(\varphi(n)\)'in belirlediği RSA algoritmasıdır.

12 ile aralarında asal olanların vurgulandığı 1'den 12'ye kadar tam sayı ızgarası
Euler'in totient fonksiyonu, n ile ortak böleni olmayan ve n'ye kadar olan tam sayıları sayar.

Bu hesaplayıcı nasıl kullanılır?

Herhangi bir pozitif tam sayı olan n değerini girin ve hesapla düğmesine basın. Araç, n'yi farklı asal bölenlerine ayırır ve çarpım formülünü uygulayarak \(\varphi(n)\) sonucunu anında verir; ayrıca bulduğu farklı asal sayıların listesini de gösterir. Hem küçük sayılarda hem de bir milyara kadar olan çok büyük sayılarda sorunsuz çalışır.

Formülün açıklaması

Phi fonksiyonunu hesaplamanın en verimli yolu çarpım formülüdür:

$$\varphi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)$$

burada çarpım, n'yi bölen her farklı asal sayı \(p\) üzerinden alınır.

Asal sayıların katlarına değil, yalnızca farklı asal sayılara ihtiyacınız vardır. Her bir \(\left(1 - \frac{1}{p}\right)\) çarpanı, o asal sayıya bölünebilen sayıların oranını eler.

Reklam
n'nin asal çarpanlarına ayrılıp (1 eksi 1 bölü p) terimleriyle çarpıldığını gösteren şema
Çarpım formülü, her farklı asal bölen \(p\) için n'yi \(\left(1 - \frac{1}{p}\right)\) çarpanıyla çarpar.

Çözümlü örnek

\(n = 36\) olsun. Asal çarpanlara ayrılışı \(2^2 \times 3^2\) olduğundan farklı asal sayılar 2 ve 3'tür. O hâlde:

$$\varphi(36) = 36 \times \left(1 - \frac{1}{2}\right) \times \left(1 - \frac{1}{3}\right) = 36 \times \frac{1}{2} \times \frac{2}{3} = 36 \times \frac{1}{3} = \mathbf{12}$$

Yani 1 ile 36 arasında tam olarak 12 tam sayı 36 ile aralarında asaldır.

Daha Fazla Çözümlü Örnek

Örnek 1: Asal sayı, φ(13)

13 bir asal sayıdır, dolayısıyla tek asal çarpanı 13'ün kendisidir:

\(\varphi(13) = 13\left(1-\frac{1}{13}\right) = 13 \cdot \frac{12}{13} = \)12. Bu, \(\varphi(p) = p-1\) asal sayı kısayoluyla uyumludur.

Örnek 2: Asal sayı kuvveti, φ(32)

Çarpanlara ayırma: \(32 = 2^5\). Tek farklı asal sayı 2'dir.

\(\varphi(32) = 32\left(1-\frac{1}{2}\right) = 32 \cdot \frac{1}{2} = \)16.

Eşdeğer asal kuvvet biçimi: \(\varphi(p^k) = p^k - p^{k-1}\), dolayısıyla \(\varphi(2^5) = 2^5 - 2^4 = 32 - 16 = 16\). Bunlar tam olarak 1 ile 31 arasındaki tek sayılardır.

Örnek 3: Üç veya daha fazla farklı asal sayı, φ(210)

Çarpanlara ayırma: \(210 = 2 \cdot 3 \cdot 5 \cdot 7\).

  1. \(210\) ile başlayın.
  2. \(1-\frac{1}{2} = \frac{1}{2}\) ile çarpın: \(210 \cdot \frac{1}{2} = 105\).
  3. \(1-\frac{1}{3} = \frac{2}{3}\) ile çarpın: \(105 \cdot \frac{2}{3} = 70\).
  4. \(1-\frac{1}{5} = \frac{4}{5}\) ile çarpın: \(70 \cdot \frac{4}{5} = 56\).
  5. \(1-\frac{1}{7} = \frac{6}{7}\) ile çarpın: \(56 \cdot \frac{6}{7} = 48\).

Dolayısıyla \(\varphi(210) = \)48. Çarpım kuralının her farklı asal sayıyı yalnızca bir kez kullandığına dikkat edin. Örneğin, \(60 = 2^2 \cdot 3 \cdot 5\) için \(60 \cdot \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{4}{5} = 16\) elde edilir.

Reklam

φ(n) Fonksiyonunun Yorumlanması ve Kullanım Alanları

  • Asallık bağlantısı: \(n \ge 2\) için, \(\varphi(n) = n-1\) ancak ve ancak \(n\) asal ise geçerlidir. Bir asal sayıdan küçük her sayı, o asal sayıya göre aralarında asaldır. Eğer \(n\) bileşik ise, ondan küçük en az bir sayı ortak bir çarpan paylaşır ve bu durumda \(\varphi(n) < n-1\) olur.
  • Birimler grubu: \(\varphi(n)\), \(n\) modülüne göre birimler grubundaki eleman sayısıdır; yani mod \(n\) çarpımsal tersi olan kalıntılardır. \(n = 15\) için bunlar 1, 2, 4, 7, 8, 11, 13, 14 olup 8 eleman eder.
  • Euler teoremi: \(\gcd(a, n) = 1\) ise, \(a^{\varphi(n)} \equiv 1 \pmod{n}\). Örnek: \(a = 2\), \(n = 15\), \(\varphi(15) = \)8 ve \(2^8 = 256 = 17 \cdot 15 + 1 \equiv 1 \pmod{15}\). Fermat'nın küçük teoremi, \(n = p\) asal olduğu özel durumdur.
  • RSA: \(n = pq\), burada \(p\) ve \(q\) farklı asal sayılar ise, \(\varphi(n) = (p-1)(q-1)\). \(n = 15 = 3 \cdot 5\) için: \(\varphi(15) = 2 \cdot 4 = 8\). Açık üs \(e\), \(\varphi(n)\) ile aralarında asal olmalı ve özel üs \(d\), \(ed \equiv 1 \pmod{\varphi(n)}\) koşulunu sağlamalıdır. Gerçek RSA, yüzlerce basamak uzunluğunda asal sayılar kullanır. \(n\)'yi çarpanlarına ayırabilen herkes \(\varphi(n)\)'yi hesaplayabilir; güvenliğin çarpanlara ayırmanın zor olmasına dayanmasının nedeni budur.
  • Oran yalnızca farklı asal sayılara bağlıdır: \(\dfrac{\varphi(n)}{n} = \prod_{p \mid n}\left(1-\frac{1}{p}\right)\). Üsler önemli değildir. Örneğin, 6 ve 12'nin asal kümesi {2, 3} olup, \(\varphi(6)/6 = 2/6 = 1/3\) ve \(\varphi(12)/12 = 4/12 = 1/3\) olur.

Sıkça Sorulan Sorular

\(\varphi(1)\) kaçtır? Tanım gereği \(\varphi(1) = 1\)'dir, çünkü 1 kendisiyle aralarında asal kabul edilir.

Bir p asal sayısının \(\varphi\) değeri nedir? Her p asal sayısı için \(\varphi(p) = p - 1\)'dir; çünkü 1'den \(p-1\)'e kadar olan her tam sayı p ile aralarında asaldır.

\(\varphi\) çarpımsal bir fonksiyon mudur? Evet. Eğer \(\gcd(a, b) = 1\) ise \(\varphi(a \cdot b) = \varphi(a) \cdot \varphi(b)\) olur. Çarpımın farklı asal sayılar üzerinden alınmasının nedeni de tam olarak budur.

Son güncelleme:

Matematik ve İstatistik kategorisinde en popüler

Tüm Matematik ve İstatistik hesap makinelerini gör