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.