オイラーの関数φ(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 · ベストアンサー

>これは順序が逆です。
>
>φ(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)に対応させるところ
でした。

回答No.6

uyama33

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からのものと、ｂからのものに分けることが出来る
ところです。

お礼

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

回答No.5

uyama33

φ(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)の証明が
わからないのです。

回答No.4

koko_u_u

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

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

お礼

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

回答No.3

uyama33

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

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

お礼

a,bは互いに素です。

回答No.2

koko_u_u

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

お礼

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

回答No.1

koko_u_u

φ(ab)=φ(a)φ(b) の証明が書かれていたけど、よくわからなかった。
という意味ですか？

お礼

そうです。