素因数分解の証明問題

素因数分解の証明問題

証明方法がわかりません。
自然数の素因数分解をn=(P_1)^e_1(p_2)^e_2・・・(p_r)^e_rとする。このとき、
φ(n)=n｛1-(1/p_1)｝｛1-(1/p_2)｝・・・｛1-(1/p_r)｝となることを示せ。

ただし、自然数m,nに対して、gcd(m,n)=1ならば、φ(mn)=φ(m)φ(n)であることを用いよ。

よろしくお願いします。

No.2 回答者： Tacosan 回答日時： 2010/06/29 10:33

文章に不明確なところがあります:

・「φ(n)」の定義を書いてください.
・「p_1, p_2, ..., p_r がすべて異なる」という条件はありますか? ありませんか?

この回答への補足

φ(n)はEuler関数のことです。
p∈Nに対して、φ(p)=｜｛n|1≦n≦p,gcd(n,p)=1｝｜
つまり、φ(p)は集合の要素の個数を表しています。
p_1, p_2, ..., p_r はすべて素数で異なります。

補足日時：2010/06/29 18:05

No.1 ベストアンサー 回答者： R_Earl 回答日時： 2010/06/29 01:46

数学的帰納法で解けそうです。

[1]
n = (p_1)^e_1の時にφ(n)=n{1-(1/p_1)}{1-(1/p_2)}…{1-(1/p_r)}を証明

[2]
r = kの時にφ(n)=n{1-(1/p_1)}{1-(1/p_2)}…{1-(1/p_r)}が成り立つと仮定した時、
r = k + 1の時でもφ(n)=n{1-(1/p_1)}{1-(1/p_2)}…{1-(1/p_r)}が成り立つ事を証明

[1], [2]より全ての整数n = (p_1)^e_1(p_2)^e_2・・・(p_r)^e_rに対して
φ(n)=n{1-(1/p_1)}{1-(1/p_2)}…{1-(1/p_r)}が成立

とすれば良さそうです。
[2]を証明する際に
「自然数m,nに対して、gcd(m,n)=1ならば、φ(mn)=φ(m)φ(n)」
という事を利用できそうです。

この回答へのお礼

参考にさせていただき、解くことができました。
ありがとうございました。

お礼日時：2010/06/30 16:41