最大公約数について！

質問

二つの整数m、n(m＞n)の最大公約数をｇとすると、mをnで割ったあまりとnとの最大公約数もｇであることを証明せよ
ただしm、nが互いに素であるとき、nとm－nも互いに素であることを使ってもよい

はじめから解説をお願いします！

回答No.4

ferien · ベストアンサー

「m、nが互いに素であるとき、nとm－nも互いに素である」のときの回答者です。
この証明法を一部分マネして使って証明をすることができました。

＞二つの整数m、n(m＞n)の最大公約数をｇとすると、mをnで割ったあまりとnとの最大公約数もｇであることを証明せよ

「二つの整数m、n(m＞n)の最大公約数はｇである」の意味は、「m＝aｇ、n＝bｇ(a、bは互いに素な整数)とおける」です。
だから、公約数ｇが最大公約数であることを示すには、ａ，ｂに相当する部分が互いに素であることが言えればいいです。

二つの整数m、n(m＞n)の最大公約数をｇとすると
ｍ＝ａｇ，ｎ＝ｂｇ（ａ、ｂは互いに素な整数）とおける。
mをnで割った商をｑ，あまりをｒとすると、
ｍ＝ｎｑ＋ｒより、ｒ＝ｍ－ｎｑ＝ａｇ－ｂｇｑ＝（ａ－ｂｑ）ｇだから、
ｎとｒは、ｇを公約数にもつ。
（ｂとａ－ｂｑも互いに素であることが言えれば、公約数ｇは最大公約数であると証明できる。）

＜ａ，ｂが互いに素　ならば、ｂとａ－ｂｑも互いに素である。＞
ｂとａ－ｂｑの最大公約数をｇ'とおく。
ｂ＝ｃｇ'，ａ－ｂｑ＝ｄｇ'（ｃ，ｄは互いに素な整数）とおくと、
ｂｑ＝ｃｑｇ'より、
ａ＝（ａ－ｂｑ）＋ｂｑ＝ｄｇ'＋ｃｑｇ'＝（ｄ＋ｃｑ）ｇ'となる。
ａとｂは、公約数ｇ'をもつが、ａとｂは互いに素なので、
ａとｂの正の公約数は１しかない。
よって、ｇ'＝１より、ｂとａ－ｂｑは、互いに素である。

よって、ｎとｒの公約数ｇは、最大公約数である。

どうでしょうか？
質問への回答になっていなかったら、申し訳ありません。

お礼

回答本当にありがとうございます！

回答No.7

eclipse2maven

これでいいかな？（^^;

dの最小性をつかうと　dが公約数はすぐ言えます。　そうすると　互いに素だったら
dは１　にとれます　そうすると　最大公約数は　am +bn　の形にかける　従って　d　で割れる

逆に　m,n は　最大公約数で割れるので dも最大公約数で割れる、したがって　
dは　最大公約数

お礼

わかりました！
回答ありがとうございました！

回答No.6

eclipse2maven

ん？　N05　の　括弧の証明　間違ってるかな　ま、　括弧の中は無視してください。(^^;

お礼

わかりました！

回答No.5

eclipse2maven

質問者の方が高校生なのか大学生なのか社会人なのか　判断が私には出来なので　こまるのですが。
とりあえず

m と　n の最大公約数　（最大公約数の定義は、いままでいろいろかかれてますよね）　が d

＜＝＝＞

am +bn (a, b は整数）　で表される正の整数　で　最小のものが　d

という　事実があります。（証明は　dの最小性をつかうと　dが公約数はすぐ言えます。　そうすると　互いに素だったら
dは１　にとれます　そうすると　最大公約数は　am +bn　の形にかける　従って　d　で割れる　商が１でなければ
a,b は　商を公約数にもつので　dよりちいさな　am +bn 作れてしまうので　最小性に矛盾　従って　　d　は最大公約数）　

a(m-n) + bn で　表される　整数の　全体集合　と　　am +bn　で表される　整数の　全体の集合
は同じですよね。　今の場合　上の事実の　d=1 のときだけをつかっていいよって　感じなのです。

お礼

なるほど！ありがとうございます！

回答No.3

Tacosan

繰返し補足要求をしていた回答者です (苦笑) が, 正直なところ
http://okwave.jp/qa/q7373938.html
の #4 に対して「両方説明していただけないでしょうか」と言われてしまうとやる気になれないんだよな～.

この「両方」はおそらく「AとBの最大公約数＝AとB－Aの最大公約数というのを求めた理由」と「引き算と割算とあまりとの関係」なんだろうけど....

後者については, 今の学習指導要領によるとおそらく 3年でやるはずなので, いくらなんでもそこまで遡らにゃならんようではねぇ. 前者にいたっては, そもそも「他人に説明を求める」ようなものではない. だって, あなた自身が「AとBの最大公約数＝AとB－Aの最大公約数というのを求めよう」と思ったんでしょ?

お礼

引き算と割算とあまりとの関係が抽象的で分からないしAとBの最大公約数＝AとB－Aの最大公約数というのを求めようとしたのは答えにそう書いてあったからです！改めて言われるとよく理解してなかったので説明してください！

回答No.2

alice_44

同じ質問で、三回目の投稿ですかね。
初回投稿 Q7373557 に対する A No.4 に
完璧と思われる回答があり、貴方自身も
「わかりやすい」とコメントしています。
それでも解らなかった部分がどこなのか、
質問文からは見えてこないし、二回目質問の際に
繰返し補足要求をしていた回答者がありましたが、
彼への補足も全く要領を得ません。
貴方が引っ掛かっている所はどこか、
何らか表現する努力をすれば、貴方向きの
回答がつく可能性も出てくるでしょう。
もう少し言葉を尽くして、貴方が何を考えたのか
説明する必要があるだろうと思います。

お礼

同じ質問は二回目ですが、前回は解説がなかったのでこのまま流れてしまうと思ってまた立てました
私がわかりやすいとコメントしたときの質問はここの質問の「ただしm、nが互いに素であるとき、nとm－nも互いに素であることを使ってもよい」を証明する問題です
引っかかるところは前回の質問の補足に書きましたが理解してないと言われたのではじめから解説をお願いしたんです！

回答No.1

LHS07

> 二つの整数m、n(m＞n)の最大公約数をｇとすると、mをnで割ったあまりとnとの最大公約数もｇであることを証明せよ
言葉通りですが

> ただしm、nが互いに素であるとき、nとm－nも互いに素であることを使ってもよい
素がわからないのですか？
http://okwave.jp/qa/q5031771.html

お礼

はじめから が余計だったみたいですね
二つの整数m、n(m＞n)の最大公約数をｇとすると、mをnで割ったあまりとnとの最大公約数もｇであることを証明せよ
の解き方の解説をお願いします！