Euler fi fonksiyonunun çok güzel bir kullanımı

Question

$n\in\mathbb{N}$,    $p_1,p_2,...,p_k$ farklı asal sayılar, $r_1,r_2,...,r_k$ doğal sayılar olmak üzere  eğer $n= p_1^{r_1}.p_2^{r_2}...p_k^{r_k}$ ise,Euler fi fonksiyonu olarak bilinen fonksiyonun 

 $\phi(n)=(p_1^{r_1}-p_1^{r_1-1})(p_2^{r_2}-p_2^{r_2-1})(p_3^{r_3}-p_3^{r_3-1})...(p_k^{r_k}-p_k^{r_k-1})$

olduğunu biliyoruz. Keza $\phi(n)=n.(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_k})$ dir. 

Burada   daha ayrıntılı bilgi var. Benim sormak istediğim yine Euler'e ait olan $OBEB(a,n)=1$  olmak üzere, $a^{\phi(n)}=1 (modn)$ olduğunun ispatı nasıldır?

Comments

Grup yapisini kullanmak yeterli. 

---

Hocam biraz daha fazla açıklama ve mümkünse ispatı alabilir miyiz?

Answer 1

$r_{1},r_{2},\ldots r_{\varphi \left( n\right) }$ kalanları $Mod$ $n$ de elde edilebilecek, $n$ ile aralarında asal farklı kalanlar olsunlar. Bu kalanları $OBEB(a,n)=1$ olacak biçimde bir $a$ tam sayısı ile çarparsak

$ar_{1},ar_{2},\ldots ar_{\varphi \left( n\right) }$ olurlar. Tabii ki $OBEB(ar_{i},n)=1$ olacaktır. Ben iddia ediyorum ki bu kalanların hepsi birbirinden farklı kalanlardır. Yani demek istiyorum ki

                                                     $r_{1},r_{2},\ldots r_{\varphi \left( n\right) }$

bir sıralama olarak düşünürsek

                                                     $ar_{1},ar_{2},\ldots ar_{\varphi \left( n\right) }$

sıralaması, onun bir permütasyonudur. Bu iddiamizi çelişki yöntemi ile ispatlayalım. Farz edelim ki, birbirinden farklı $r_{i} = r_{j}$ için

                                                         $ar_{i} = ar_{j} (mod n)$

olsun.  $OBEB(ar_{k},n)=1$ olacağından rahatlıkla

                                                          $r_{i} = r_{j} (mod n)$

olacaktır. Bu durum $r_{i} = r_{j}$ olmasını gerektirir. Çelişki. O halde

                                            $ar_{1}.ar_{2}.\ldots ar_{\varphi \left( n\right) }$=$r_{1}.r_{2}.\ldots r_{\varphi \left( n\right) }$ $(mod n)$

                                                            $a^{\varphi \left( n\right) } = 1 (mod n)$

Comments

teşekkürler Dogukan.

---

Rica ederim hocam :) :)

---

fermat'ın küçük teoremi de benzer şekilde ispatlanıyordu sanırım.

---

Düzeltme: Farz edelim ki, birbirinden farklı $r_i = r_j$ için ... ifadesi yerine $r_i \neq r_j$ yazılmalıdır.