オイラーの関数φ(ab)=φ(a)φ(b)の証明

オイラーの関数φ(ab)=φ(a)φ(b)の証明を
わかりやすく教えてください。

自然数nを素因数分解して n=(p^α)・(q^β)・(r^γ)・・・ と表せるとき、
オイラーの関数は
φ(n)=n(1-1/p)(1-1/q)(1-1/r)・・・
となる証明の途中でφ(ab)=φ(a)φ(b)が出て来たのですが、
この式の証明よくわかりませんでした。

No.7 ベストアンサー 回答者： kabaokaba 回答日時： 2011/03/09 23:13

>これは順序が逆です。

>
>φ(n)=n(1-1/p)(1-1/q)(1-1/r)・・・を証明するために
>φ(ab)=φ(a)φ(b)が出て来て、φ(ab)=φ(a)φ(b)の証明が
>わからないのです。

まったく「学習の方法」が分かってないのですね．
証明が分からないというから
逆手にとって
証明対象が正しいと認めて
まずは具体例で考えてみなさいと
アドバイスされてるのが分からないのですか？

そもそも・・・既約剰余類を導入して
abの既約剰余類と，aの既約剰余類とbの既約剰余類の組が
1対1に対応するということを証明するだけなんだから
まずは具体的に
a=5,b=3とかで手を動かせばいいのです．

(1) 15の既約剰余類は 1,2,4,7,8,11,13,14
(2) 5の既約剰余類は 1,2,3,4
(3) 3の既約剰余類は 1,2

(2)と(3)のペア(m,n)と(1)の値 3m+5n を対応させる
(1,1) -> 8
(1,2) -> 13
(2,1) -> 11
(2,2) -> 16 -> 1
(3,1) -> 14
(3,2) -> 19 -> 4
(4,1) -> 17 -> 2
(4,2) -> 22 -> 7

逆に，(1)の値に対しては 3*2+5*(-1)=1（ユークリッドの互除法）を使って

1 -> (2,-1) -> (2,2)
2 -> (4,-2) -> (4,1)
4 -> (8,-4) -> (3,2)
7 -> (14,-7) -> (4,2)
8 -> (16,-8)-> (1,1)
11 -> (22,-11) -> (2,1)
13 -> (26,-13) -> (1,2)
14 -> (28,-14) -> (3,1)

この二つの対応は明らかに互いに逆写像になっているので
abの既約剰余類と，
aの既約剰余類とbの既約剰余類の組が
1対1に対応する
のが見えるのです．

これを一般的に書けば証明です．
はっきりいって
具体的に数字で書き下せば納得できるでしょう．
この手の初等整数論に限らず
数学で泥臭い手計算を避けるのは愚策以外の何物でもありません．

この回答へのお礼

丁寧な回答ありがとうございます。
だいぶわかってきました。

> まずは具体例で考えてみなさいと
> アドバイスされてるのが分からないのですか？
φ(n)=n(1-1/p)(1-1/q)(1-1/r)・・,φ(ab)=φ(a)φ(b)に
数値を代入して成立するのはわかります。

わからなかったのは
・既約類、既約剰余系、既約代表の一組の概念の違い
・φ(a)、φ(b)の既約剰余系の「組」をφ(ab)の既約剰余系に対応させる
・φ(ab)→φ(a)、φ(b)に対応させるところ
でした。

お礼日時：2011/03/10 11:08

No.6 回答者： uyama33 回答日時： 2011/03/09 22:03

n=ab　で、a,b　は互いに素とする。

互いに素なので、a,bを素因数分解するとき、共通の素因数は無い。
a の素因数分解を、ΠPi
b の素因数分解を、ΠQj
とすれば、
n＝ab の素因数分解は　n＝ΠPi*ΠQj
となり、
オイラーの関数は
φ(n)=nΠ(1-1/pi)*Π(1-1/Qｊ)
　　＝abΠ(1-1/pi)*Π(1-1/Qｊ)
＝aΠ(1-1/pi)*bΠ(1-1/Qｊ)
＝φ(a)φ(b)
となり、等式は成立する。

ポイントは、互いに素なので共通因数が無いので
素数をaからのものと、ｂからのものに分けることが出来る
ところです。

この回答へのお礼

回答ありがとうございます。

お礼日時：2011/03/10 11:09

No.5 回答者： uyama33 回答日時： 2011/03/09 19:46

φ(n)=n(1-1/p)(1-1/q)(1-1/r)・・・

の式で、
a=14=2*7
b=15=3*5
n=14*15＝210
として、
φ(210)=210(1-1/2)(1-1/7)(1-1/3)(1-1/5)
と、
φ(14)=14(1-1/2)(1-1/7)
φ(15)=15(1-1/3)(1-1/5)
を比べてください。

この回答へのお礼

これは順序が逆です。

φ(n)=n(1-1/p)(1-1/q)(1-1/r)・・・を証明するために
φ(ab)=φ(a)φ(b)が出て来て、φ(ab)=φ(a)φ(b)の証明が
わからないのです。

お礼日時：2011/03/09 21:25

No.4 回答者： koko_u_u 回答日時： 2011/03/09 18:02

＞φ(ab)=φ(a)φ(b)の証明がわからなかったとしか

＞いいようがないです

それではアドバイスのしようがありませんね。
どんな証明が書いてあって、最初に分からなかった箇所はどこですか？

この回答へのお礼

合同の観念を応用して、φ(n)の意味を練れば、
簡単にφ(ab)=φ(a)φ(b)が解決するとあり、
既約類、既約剰余系を導入するんですが
これがよくわからないです。
次にay+bxを考察しφ(ab)とφ(a)などの既約代表を考えるのですが
これもよくわかりませんでした。
連立合同式を使う他の証明もあったのですが
お手上げです。

お礼日時：2011/03/09 21:36

No.3 回答者： uyama33 回答日時： 2011/03/09 06:15

a,bは互いに？？とする。

なんて書いてありませんでしたか？

この回答へのお礼

a,bは互いに素です。

お礼日時：2011/03/09 09:43

No.2 回答者： koko_u_u 回答日時： 2011/03/08 20:17

具体的にどの辺がわからなかったか説明できますか？

この回答へのお礼

φ(ab)=φ(a)φ(b)の証明がわからなかったとしか
いいようがないです。

お礼日時：2011/03/09 09:42

No.1 回答者： koko_u_u 回答日時： 2011/03/08 10:40

φ(ab)=φ(a)φ(b) の証明が書かれていたけど、よくわからなかった。

という意味ですか？

この回答へのお礼

そうです。

お礼日時：2011/03/08 12:17