Euler Phi ve Mobius fonksiyonu ilişkisi

1 beğenilme 0 beğenilmeme
531 kez görüntülendi

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.

8, Temmuz, 2016 Akademik Matematik kategorisinde Kirmizi (473 puan) tarafından  soruldu

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. 

aynı yerde ipucu da var.

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

...