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