Euler Phi ve Mobius fonksiyonu ilişkisi

Question

Bir $n$ doğal sayısı için  Euler Phi fonksiyonu $\varphi (n)$ bize $n$ sayısından küçük $n$ ile arasında asal olan sayıların adedini veriyor. Mobius $\mu$ fonksiyonu da şöyle tanımlanıyor:

$$\mu\left(n\right)=\begin{cases}1 & \mbox{eğer }n=1\\\left(-1\right)^{t} & \mbox{eğer }n\mbox{ sayısı }t\mbox{ tane farklı asalın çarpımı şeklinde ise}\\0 & \mbox{eğer bir }p\mbox{ asal sayısı için }p^2 \mid n .\end{cases}$$

Bu iki fonksiyon arasında bir ilişki veren şöyle bir teorem var:

Teorem. $\varphi\left(n\right)={\displaystyle \sum_{d|n}}\mu\left(d\right)\frac{n}{d}$

Bu teoremin kanıtında iki tane alet kullanılıyor, önce onları verelim:

$\sum_{d\mid n}\mu (d)=\lfloor \frac{1}{n}\rfloor$ ve $\varphi(n) = \sum_{k=1}^n \left\lfloor \frac{1}{(n,k)} \right\rfloor$.

Kanıt şöyle başlıyor( ve bitiyor):

$\begin{align*}\varphi(n) & = \sum_{k=1}^n \left\lfloor \frac{1}{(n,k)} \right\rfloor = \sum_{k=1}^n\sum_{d\mid (n,k)} \mu(d) = \sum_{k=1}^n \sum_{\substack{d\mid n\\ d\mid k}}\mu(d) \\ & = \sum_{d\mid n}\sum_{q=1}^{n/d}\mu(d)=\sum_{d\mid n}\mu(d)\Biggl( \sum_{q=1}^{n/d}1\Biggr)=  \sum_{d\mid n}\mu(d)\frac{n}{d}\end{align*}$

2 gündür düşünüyorum, örnek üzerinde bakıyorum ama şu geçişi bir türlü anlayamıyorum:

$\sum_{k=1}^n \sum_{\substack{d\mid n\\ d\mid k}}\mu(d)  = \sum_{d\mid n}\sum_{q=1}^{n/d}\mu(d)$.

İlk sorum bu.

İkincisi bu toplam sembolleri şu şekilde mi çalışıyor acaba?:

"Sırayla $k=1,2,\dots,n$'i seç. $n$'nin bölenlerine, $d$'lere, bak. Hem $n$, hem $k$'yı bölen $d$'lerin $\mu(d)$ değerlerini toplaya toplaya git."

Son olarak bu toplam sembollerini soldan sağa(dışarıdan içe) mı yoksa sağdan sola(içten dışarı) mı okumak gerekir?

Cevaplar için şimdiden teşekkürler.

Comments

Aslinda adimlar direkt atlanabilir de. $n$'nin bir boleni $d$'yi sabitleyelim. Bu durumda $d$  sayisi $1,\cdots, n$ arasindaki "$k$" degerlerinden sadece $\frac nd$ tanesini boler.

---

Bir $d$ bölenini sabitlersek olacakları anlıyorum lakin indislerin nasıl çalıştığını anlamıyorum.

---

$M=\{m_1,\cdots,m_s\}$ ve $N=\{n_1,\cdots,n_t\}$ olsun. Istenilen $f(m_i,n_j)$'lerin hepsini toplamak olsun. Nasil topladigimiz bize kalmis.

Ilk sorun gecisi anlamadigin hakkindaydi. Ona cevap vermeye calismistim. 

---

şurada sorulmuşu var: http://matkafasi.com/5281/mobius-ters-yuz-etme-formulu?show=5281#q5281

---

aynı yerde ipucu da var.

---

İnceliyorum başlığı, teşekkürler.