$n>2$ için $\phi(n)$ nin çift olduğunu gösterin. ($\phi(n)$: $n$ den küçük, $n$ ile aralarında asal doğal sayıların sayısı, Euler in fonksiyonu)

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


9, Kasım, 2016 Lisans Matematik kategorisinde DoganDonmez (3,673 puan) tarafından  soruldu

$\phi $ fonksiyonu $n$'den küçük veya $n$'ye eşit olan, $n$ ile aralarında asal pozitif tam sayıların sayısı olarak tanımlanıyor. 

http://www.wikizeroo.net/index.php?q=aHR0cHM6Ly9lbi53aWtpcGVkaWEub3JnL3dpa2kvRXVsZXIlMjdzX3RvdGllbnRfZnVuY3Rpb24 

Problemi etkilemiyor ama linkinde de $\phi (1) = 0 $ değil $1$ olarak verilmiş.

Evet haklısın. Zaten 1 ile ilgilenmediğimiz için böyle yazmak daha kolayıma geldi.

(Ama 0 ı doğal sayı kabul edince, bu tanımla da, yine $\phi(1)=1$ oluyor!)

$\phi(1)=0$ olmasi (olasiligi) tam olarak nereden cikti, o kismi goremedim. 

Ben, sorumdaki $\phi(n)$ tanımını "$n$ den küçük doğal sayıların sayısı" olarak yazmıştım. 0 'ı doğal sayı saymazsak  öyle çıkıyor. Onu kastetmiş.

2 Cevaplar

2 beğenilme 0 beğenilmeme
 
En İyi Cevap

Diger bir cozum: $n=1$ durumunu ayirirsak, arada bir sayi var cunku... ve $1$ ve $1-1=0$ arada olmuyor ayni anda...

$(n,d)=(n,n-d)$ olacagindan aradaki aralarinda asal olanlari bu sekilde eslestirirsek $d=n-d$ durumu disinda ikili eslesme elde ederiz. Esitlik $n=2d$ saglandiginda olur ve $d>1$ ise $(n,d)=1$ olmaz. Bu nedenle sadece $n=2$ durumunda bunu elde ederiz. 

Bu da $n>2$ icin $\phi(n)$ cift der.

10, Kasım, 2016 Sercan (23,831 puan) tarafından  cevaplandı
27, Ekim, 27 DoganDonmez tarafından seçilmiş

Yukarıda verdiğim linkte $\phi (1) = 1 $ olarak veriliyor. (Bu durum problemin çözümünü etkilemiyor tabii)

Evet, o bariz durum. Coumu de dediginiz gibi etkilemiyor.

1 beğenilme 0 beğenilmeme

$p_1 , p_2 , . . . , p_n$ asal sayıları ve $\alpha_1 , \alpha_2 , . . . , \alpha_n$ pozitif tamsayıları için aritmetiğin temel teoremini kullanarak $ n = p_{1}^{\alpha_1} \cdot p_{2}^{\alpha_2} \cdots p_{n}^{\alpha_n}$ olduğunu varsayabiliriz. Her bir $p_{i}^{\alpha_i}$ aralarında asal olduğundan ve $\phi$ fonksiyonu çarpımsal olduğundan, biraz hesaplarsak:

                            $\phi(n) = \phi(p_{1}^{\alpha_1} \cdot p_{2}^{\alpha_2} \cdots p_{n}^{\alpha_n}) = \phi(p_{1}^{\alpha_1}) \cdot \phi(p_{2}^{\alpha_2}) \cdots \phi(p_{n}^{\alpha_n})$

buluruz. Ayrıca kanıtlanabilir ki : $\phi(p_{i}^{\alpha_i}) = p_{i}^{\alpha_i} - p_{i}^{\alpha_i - 1}$ .

O halde, 

$\phi(n) = \phi(p_{1}^{\alpha_1}) \cdot \phi(p_{2}^{\alpha_2}) \cdots \phi(p_{n}^{\alpha_n}) =(p_{1}^{\alpha_1} - p_{1}^{\alpha_1 - 1}) \cdot (p_{2}^{\alpha_2} - p_{2}^{\alpha_2 - 1}) \cdots (p_{n}^{\alpha_n} - p_{n}^{\alpha_n - 1})$

elde ederiz. Her bir $p_i$ tek sayı olduğundan, her bir $p_i$'nin bir kuvveti de tek sayıdır. Her bir parantez içinde iki tek sayıyıdan küçüğü büyüğünden çıkardığımızdan, bir pozitif çift sayı buluruz. Sonlu tane pozitif çift sayının çarpımı da pozitif çift sayıdır. Her bir $p_i$'nin tek sayi olmadigi durumda ise ancak bir tanesi $2$ olabilir. Bu durumda parantez icindeki ifade yine cift olur. Yalnizca bir tane $p$ olup onun da 2 olma durumu ise varsayimla celisiyor.

9, Kasım, 2016 Cagan Ozdemir (672 puan) tarafından  cevaplandı

Küçük bir nokta eksik Cagan, $n>2$ gerekiyor ($\phi(2)=1$).

Senin cevabında, bunun nerede kullanıldığı anlaşılmıyor.

Haklisiniz Dogan hocam, soruda zaten varsayildigi icin cevaba yazmamistim. 

Tum $p_i$ lerin tek oldugunu soylerken kullandik.

Tüm $p_i$ ler tek olmak zorunda değil. $n=2^k\ (k>1)$ iken de $\phi(n)$ in çift olduğunu göstermeliyiz.

...