離散数学の証明

質問

離散数学の証明

次の問題の証明方法が分かりません。助けてください。
任意の整数m,nに対して次の(1)(2)を証明せよ。
(1)m,n≠0のとき、dがm,nの正の公約数であるならば、gcd（m/d,n/d）＝gcd（m,n）/d
(2)m,n≠0のとき、gcd（m/gcd(m,n),n/gcd(m,n)）＝１

ちなみにxが非負整数でm,nの最大公約数であるとき、gcd（m,n）=xと表されます。
よろしくお願いします。

回答No.2

banakona · ベストアンサー

ふつう、（２）は自明のことというか、＝１だからこそ最大公約数という気がするんだけど・・・ということで、（２）の方が基本的なので、（２）から。

gcd（m,n）=xとするとき、ｍ＝ａｘ、ｎ＝ｂｘと置ける。

gcd（m/gcd(m,n),n/gcd(m,n)）＝gcd（ａ，ｂ）で、これが１ではないとすると、
ａ，ｂが１ではない公約数を持つことになる（これをｐ（ｐ＞１）とする）。

すると、ａ＝ｅｐ，ｂ＝ｆｐと置け、ｍ＝ｅｐｘ、ｎ＝ｆｐｘとなって、ｐｘもｍ，ｎの公約数。

ところが、ｐ＞１なのでｐｘはｘよりも大きい。これはｘがｍ、ｎの「最大」公約数であることと矛盾する。
よってgcd（m/gcd(m,n),n/gcd(m,n)）＝１

（１）は簡単でしょ。

お礼

すごくヒントになり、助かりました！
どうもありがとうございました。

回答No.1

B-juggler

こっちが先でしたか。もう一つありましたね。

これも同じ。

素因数分解の形で　ｍ，ｎ　を丁寧に表すと、

何も考える必要なんてないよ。難しく考えてはいけない。

数学は、「物事を理論的に、順序だてて考える」という、ものですから

最初から難しく考える、というのは不合理だよ。

どこまで簡単に分かるか、それを書いてみるだけでも

ずいぶんと違うからね。　

この（２）は、互いに素　ということになるけど、

公約数は存在しないということだね。もう一問のほうで出てきているけれど、

互いに素って言うのはちょっと注意しながら扱わないといけないから、

「素因数分解」の形で出すこと！　が先。

がんばってね。

お礼

ご指摘ありがとうございます。
頑張って考えます。