Euler Phi Fonksiyonu ( ϕ )

İsviçreli matematikçi Leonhard Euler (1707-1783) tarafından ortaya koyan ve sayılar teorisinde çok büyük öneme sahip olan bu fonksiyon bize bir sayının kendisinden küçük kendisi ile aralarında asal sayıların sayısını vermekte. Euler Phi fonksiyonu Euler teoremi gibi pek çok teoremde ve RSA kriptografi sisteminde de kullanılmaktadır.

Teorem 1: P bir asal sayı iken ϕ(p)=p-1
İspat: P bir asal sayı olduğundan kendisinden küçük hiçbir sayıyla ortak çarpanı olmayacağından hepsiyle aralarında asaldır.

Teorem 2: P bir asal sayı ve a bir pozitif tam sayı iken ϕ(p^a)=p^a-p^a-1
İspat: p tane ardışık sayıdan sadece 1 tanesi p ile tam bölüneceği için 1’den p sayısına kadar olan sayılardan sadece p^a-1 tanesi p ile tam bölünür. Bu yüzden p^a sayısından küçük ve o sayıyla aralarında asal olan sayıların sayısı p^a-p^a-1 dir.

Teorem 3: n = ab ve a ile b aralarında asal olmak üzere ϕ(n)=ϕ(a).ϕ(b)

İspat için bilinmesi gereken ön tanım ve kurallar:

Ön Teorem 1: n=ab ve a ile b aralarında asal sayılar olmak üzere x’in 1, 2, 3, … , n-1 değerleri için [x] elemanıdır Z_n ile ([x],[x]) elemanıdır Z_axZ_b ‘nin sadece 1 elemanıyla eşleşir. Burada eşleşmeden kastettiğim n’ye bölündüğünde x kalanı elde ettiğimiz bir p sayısı olsun bu sayının a’ya bölümünden elde ettiğimiz kalan k ve b’ye böldüğümüzde elde ettiğimiz kalan p olsun. O zaman elde edeceğimiz eşleşme [x]↔([n],[p]) şeklinde olur.
Ön Teorem İspatı: Varsayalım ki [x₁], [x₂] sayıları Z_axZ_b’de aynı eleman ile eşleşsin o zaman x₁ ve x₂ sayılarının a ve b’ye bölümünden elde edilen kalanlar eşit olur. Bu da demek oluyor ki x₁-x₂ sayısı hem a hem de b sayısını tam böler. Hem a sayısını hem de b sayısını tam böldüğü için bu sayı n sayısını da tam böler. O zaman buradan da x₁ ve x₂ sayılarının n’ye bölünmesiyle oluşan kalanlar eşittir. Bu da gösterir ki [x₁]=[x₂]

Örnek:
Z₁₂’deki ifadeleri Z₃xZ₄ ile  eşleştirelim
[0] ↔ ([0],[0])                                  
[1] ↔ ([1],[1])                                  
[2] ↔ ([2],[2])                                  
[3] ↔ ([3],[3]) = ([0],[3])
[4] ↔ ([4],[4]) = ([1],[0])                               
[5] ↔ ([5],[5]) = ([2],[1])
[6] ↔ ([6],[6]) = ([0],[2])
[7] ↔ ([7],[7]) = ([1],[3])
[8] ↔ ([8],[8]) = ([2],[0])
[9] ↔ ([9],[9]) = ([0],[1])
[10] ↔ ([10],[10]) = ([1],[2])
[11] ↔ ([11],[11]) = ([2],[3])

Teorem 3 İspat: Yukarıda bahsettiğimiz Z_n ve Z_axZ_b  arasında olan eşleşmenin benzerini U_n ile U_axU_b ile de kurabiliriz. Örnek olarak  U₂₀ ile U₄xU₅ arasındaki eşleşmeyi gösterebiliriz.

U₂₀ = {[1],[3],[7],[9],[11],[13],[17],[19]}
U₄ = {[1],[3]}
U₅ = {[1],[2],[3],[4]}
[1] ↔ ([1],[1])
[3] ↔ ([3],[3])
[7] ↔ ([7],[7]) = ([3],[2])
[9] ↔ ([9],[9]) = ([1],[4])
[11] ↔ ([11],[11]) = ([3],[1])
[13] ↔ ([13],[13]) = ([1],[3])
[17] ↔ ([17],[17]) = ([1],[2]}
[19] ↔ ([19],[19]) = ([3],[4]}

Eğer U_n’deki her elemanın U_axU_b’deki her elemanla sadece bir eşleşmesi olduğunu kanıtlarsak 3. teoremi de kanıtlamış oluruz. Z_n ile Z_axZ_b için aynısını kanıtlamıştık şimdi kanıtlamamız gereken şey aynısının U_n ile U_axU_b ile olan eşleşme için de sağlandığı. Zaten [x] ile ([x],[x]) arasında nasıl bir eşleşme olacağını biliyoruz. [x] U_n’nin elemanıdır ancak ve ancak ([x],[x]) U_axU_b’nin elemanıyken. [x] U_n’nin elemanı ise x ile n’nin aralarında asal olduğunu gösterir. Bu da x sayısının hem a hem de b sayısıyla aralarında asal olduğunu gösterir ve ([x],[x]) ile eşleşmesi olduğunu kanıtlar.

Bu 3. teoremle de istediğimiz pozitif tam sayının Euler Phi fonksiyonundaki değerini hesaplayabiliriz.

ϕ(20)=ϕ(4).ϕ(5)=(2²-2¹).(5-1)=2.4=8

Bu yazımda Euler Phi fonksiyonundaki değerlerin nasıl hesaplandığında ve Euler Phi fonksiyonunun kullanım alanlarına kısaca değinmiş oldum.