Euler'in $\phi$ fonksiyonunun ispatı

Question

$\phi(n)$, $n$ Doğal sayısından küçük ve $n$ sayısı ile aralarında asal sayı sayısı olarak tanımlansın. O zaman 

$n=p_1^{a_1}.p_2^{a_2} \cdots  p_n^{a_n}$  için

$\phi(n)$=$n.(\frac{p_1-1}{p_1}).(\frac{p_2-1}{p_2})\cdots (\frac{p_n-1}{p_n})$ olduğunu ispatlayınız.

Ben soru için çarpanları saymayı denedim ama işe yaramıyor. $x^a.y^b.z^c$ sayısında ($x,y,z$ asal)

 x ile ortak çarpan bulunduranlar $1x,2x,3x,\cdots ,nx$ oluyor bu $x.a_i$ sayılarında $a_i$'ler y ve z ile ortak çarpan bulundurabilir ki bu saymaya engel olan nedenlerden biri. İnternetten araştırdım matematik dünyası dergisinin yayınladığı bir ispat var ama halkalar kuramını kullanarak ispat ettiği için anlamadım. Bunun ispatı için ne kullanabiliriz ?

Comments

Şunu gösterebilirsen işin çoğu yapılmış olur mu?

$m$ ve $n$ aralarında asal ise $\phi(mn)=\phi(m)\phi(n)$

---

Senin yonteminde uc asal var. Istersen ilk olarak bir tane asal al: $$p_1^{e_1}.$$ Bu sayiyla arasinda asal olmayan sayilar $p_1$'e tam bolunmeli; yani $$p_1, 2p_1,\ldots,(p^{e_1-1}-1)p_1$$ sayilaridir. Buradan istenen sayi $$(p_1^{e_1}-1)-(p_1^{e_1-1}-1)=p_1^{e_1}-p_1^{e_1-1}$$ olur.

Simdi bunu iki asal icin yapmayi dene: $$p_1^{e_1}p_2^{e_2}.$$ Bu durumda arasinda asal olmayanlar ya $p_1$ ile ya da $p_2$ ile tam bolunmeli.  Tabii bunlarin kesisim kumesine de bakmak gerekli.

---

Burada Dogan hocanin verdigi bilgi ile benim verdigim asal kuvveti bilgisini birlestirirsek sonuc zaten geliyor. 

Fakat bundan once ekle cikart yaparak sonucu gormek iyi olabilir, senin acindan. 

---

İki asal için $\phi(p_1^{e_1}p_2^{e_2})=p_1^{e_1-1}p_2^{e_2-1}(p_1-1)(p_2-1)$ bulunuyor bu bilgiyle doğan hocanın söylediği $\phi(m)\phi(n)=\phi(mn)$ eşitliğini m ve n asalken kanıtladım. ama galiba bu yeterli değil her $(m,n)=1$ için nasıl kanıtlayacağız ?

Aklıma çok bir şey gelmedi. Asal sayılarda bunun varlığını kullanarak bir şeyler elde edebilir miyiz ?

---

$(m,n)=1$ (aralarında asal) ise $mn$ yi bölen bir sayı nasıl olabilir?

---

Matematik Dünyası dergisindeki sayın Mehmet Kıral'ın buradaki yazısı sanıyorum sizin isteğinize cevap olabilir.

---

$(m,n)=1$ ise $mn$'yi bölen bir sayı ya yalnızca $m$'yi böler ya yalnızca $n$'yi böler yada her ikisinide bölmez ama bunu nasıl kullanacağımızı anlamadım.

---

Buradan carpimsal ayrilabildiklerin gosterebilir misin?

---

çarpımsal ayırılabildikleri derken neyi kastettiniz onu pek anlamadım.

---

"(m,n)=1  ise mn'yi bölen bir sayı ya yalnızca m'yi böler ya yalnızca n'yi böler ya da her ikisini de bölmez" deki 

"ikisini de bölmez" i biraz düşün. Çarpımı bölüyor olmasının (ve m ile n nin aralarında asal olmasının) bir anlamı olmalı. İki asalın kuvvetleri çarpımı durumunu dikkatli incele, asal olmaları o kadar önemli mi? İstersen m ile n inin asal sayıların çarpımı olarak yazılışlarını düşün.

---

$\phi(p_1^{e_1})\phi(p_2^{e_2})=\phi(p_1^{e_1}p_2^{e_2})$ ile 

$m=k_1^{l_1}\cdots  k_m^{l_m}$  gibi bir sayıyı 2'li asal grupları halinde yazınca 3'lü grupları bilmek gerekiyor 3 için bilince 4 için bilince 5 ...... yine sonuç olarak tüm $(m,n)=1$ için kanıtlanması gerekiyor.

(m,n)=1 ken mn'yi bölen sayılardan ne m'yi ne de n'yi bölenler hem m'den hemde n'den çapran içermiş oluyor her ne kadar m ve n'yi bölmesede çarpan, m ve n'in her ikisi ile de aralarında asal olmuyor. yani

mn'den küçük ve hem m hem de n ile aralarında asal olmayan sayı sayısı=mn'i bölen ama m ve n'yi bölmeyen sayı sayısı.

$m=p_1^{e_1}.p_2^{e_2} \cdots .p_n^{e_n}$

$n=k_1^{l_1}.k_2^{l_2} \cdots .k_n^{l_n}$ olsun.

$\phi(m)=m$-[($p_1$ ile aralarında asal olmayanlar )+  ...... +($p_n$ ile aralarında asal olmayanlar)-(hem $p_1$ hemde $p_2$ ile aralarında asal olmayanlar)-(..........]

bu uzayıp gider biz mn'in bölenlerinden bulduğumuz eşitliği burdamı kullanacağız ?

Answer 1

Farklı bir ispat kombinatorik yöntemle verilebilir.

Anlaşılırlığı artırmak için $n$ pozitif tam sayısının üç farklı asal bölene sahip olması halinde ispatı verelim. $n=p^aq^br^c$ biçiminde asal çarpanlara ayrılmış olsun. $E=\{ 1,2, \dots , n\}$ kümesini ve sırasıyla $p,q,r$ ile tam bölünebilen elemanlardan oluşan $A = \{ x|p : x\in E \}$, $B = \{ x|q : x\in E \}$, $C = \{ x|r : x\in E \}$ kümelerini tanımlayalım. Öncelikle $A \cup B \cup C$ kümesinin eleman sayısını hesaplayacağız. İçerme dışarma prensibinden:

$$|A \cup B \cup C | = |A| + |B| + |C| - |A \cap B | - |A \cap C| - |B \cap C| + |A \cap B \cap C |$$

yazılır.

$|A|=\dfrac{n}{p}$,  $|B|=\dfrac{n}{q}$,  $|C|=\dfrac{n}{r}$,  $|A \cap B|=\dfrac{n}{pq}$,  $|A\cap C |=\dfrac{n}{pr}$,  $|B \cap C|=\dfrac{n}{qr}$ ve $|A \cap B \cap C|=\dfrac{n}{pqr}$

olup

$|A \cup B \cup C | = \dfrac{n}{p} + \dfrac{n}{q} + \dfrac{n}{r} - \dfrac{n}{pq} - \dfrac{n}{pr}- \dfrac{n}{qr} + \dfrac{n}{pqr}$

bulunur. Böylece

$E$ kümesinin $p,q,r$ asallarından herhangi birine bölünmeyen elemanlarının sayısı

$|E|-|A \cup B \cup C | =  n \left( 1- \dfrac{1}{p}\right)\left( 1- \dfrac{1}{q} \right) \left( 1- \dfrac{1}{r}\right)$

olarak elde edilir.

 

Not: İçerme dışarma prensibinin daha genel biçiminin ispatı için I.M. Yaglom'un Challenging Mathematical Problems Volume-1 kitabınında sayfa 52-53'e (Pr 12) bakılabilir. Bu yolla, Euler $\phi$ fonksiyonu için verilen formül genel gösterimlerle ispatlanabilir.