質問: 素因数分解の証明問題 素因数分解の証明問題 証明方法がわかりません。 自然数の素因数分解を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)であることを用いよ。 よろしくお願いします。
回答: 数学的帰納法で解けそうです。 [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)」 という事を利用できそうです。