n'den küçük ve n ile arasında asal doğal sayıların sayısı

Question

$n\in \mathbb{N}^+$ ve $p_1, p_2, ...., p_k$   $n$'nin birbirlerinden farklı asal çarpanları olmak üzere,

$n$'den küçük ve $n$ ile arasında asal doğal sayıların sayısını veren formülün 

$$n*\bigg(1-\frac{1}{p_1}\bigg)*\bigg(1-\frac{1}{p_2}\bigg)*....*\bigg(1-\frac{1}{p_k}\bigg)$$

olduğunu gösteriniz.

Comments

kategori ortaogretim ya da lisans olmali.

Answer 1

Aslinda sitede sorulmus bir soru olmasi lazim bunun.

1)$(n,m)=1$ olsun. $(a,nm)=1 \iff (a,n)=(a,m)=1$. Yani $\phi(nm)=\phi(n)\phi(m)$.

Artik sadece asal kuvvetleri icin inceleyebiliriz.

2) $p$ asal bir sayi olsun. $(a,p^n)=1 \iff (a,p)=1$. Yani $p$ sayisinin boldugu sayilari hepsinden cikartirsak istedigimiz sayiyi elde ederiz: $\{p,2p,\cdots,p^{n-1}\cdot p\}=p \cdot\{1,2,\cdots,p^{n-1}\}$ kumesinde $p^{n-1}$ eleman var.

Artik verilenlerle ispatimizi rahatlikla yapabiliriz.