最大公約数について！

Question

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

ferien · Accepted Answer

「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で割った商をｑ，あまりをｒとすると、
ｍ＝ｎｑ＋ｒより、ｒ＝ｍ－ｎｑ＝ａｇ－ｂｇｑ＝（ａ－ｂｑ）ｇだから、
ｎとｒは、ｇを公約数にもつ。
（ｂとａ－ｂｑも互いに素であることが言えれば、公約数ｇは最大公約数であると証明できる。）

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

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

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

eclipse2maven · Answer

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

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

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

eclipse2maven · Answer

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

eclipse2maven · Answer

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

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 のときだけをつかっていいよって　感じなのです。

Tacosan · Answer

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

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

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

alice_44 · Answer

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

LHS07 · Answer

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

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

最大公約数について！

「m、nが互いに素であるとき、nとm－nも互いに素である」のときの回答者です。

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

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

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

繰返し補足要求をしていた回答者です (苦笑) が, 正直なところ

同じ質問で、三回目の投稿ですかね。

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

似たような質問が見つかりました

関連するカテゴリからQ&Aを探す

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング

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

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