- 締切済み
ユークリッドの互除法がわからない
ユークリッドの互除法は、どうして割っていくと公約数が求められるのですか? 公約数を求めるやり方はわかったのですが、どうしてそうなるのかわかりません。 調べて説明や証明を読んでもチンプンカンプンでした。 わかりやすく教えていただけたら嬉しいです。 よろしくお願いします。
- みんなの回答 (7)
- 専門家の回答
みんなの回答
- lopk563
- ベストアンサー率43% (14/32)
a=bq+r(0<=r<b)の時 aとbの最大公約数をm、bとrの最大公約数をnとする。 そうするとa=a'm、b=b'm b=b''n、r=r''n となる。 まずa=bq+rより r=a-bq=a'm-b'mq=m(a'-b'q) よってmはrの約数の一つだと分かる。つまりmはaとbの最大公約数というだけでなく、bとrの約数の一つでもある。言い換えればbとrの公約数の一つであると分かります。bとrの最大公約数はnだから、n以外のbとrの約数はnの約数となる。だからmもまたnの約数であると分かります。 次にa=bq+r=b''nq+r''n=n(b''q+r'')より nはaの約数の一つだと分かる。つまりnはbとrの最大公約数というだけでなく、aとbの約数の一つでもある。言い換えればaとbの公約数の一つであると分かります。aとbの最大公約数はmだから、m以外のaとbの約数はmの約数となる。だからnもまたmの約数であると分かります。 この二つのことから、mはnの約数であり、またnはmの約数であることが分かりました。この二つが同時に成り立つとは即ちm=nであることを意味しています(そうでなければ両立しません)。ゆえにa=bq+r(0<=r<b)の時、aとbの最大公約数mと、bとrの最大公約数はnは同じであると分かります。 まとめ:a=bq+r(0<=r<b)の時、最大公約数(a,b)=最大公約数(b,r) 目的は最大公約数(a,b)を求めることです。最大公約数(a,b)=?=?-?=?と繋げていきます。最大公約数(b、r)の次は規則的に考え、最大公約数(b、r)=最大公約数(r、bをrで割った余り)となります。こうしてどんどん繋げていき最終的に割り切れて=(c,0)となると(0=c×0より)最大公約数(c,0)=cとなり結果、最大公約数(a,b)=?=?=?=(c,0)=cとなり答えはcと求まります。 まずはa=bq+r(0<=r<b)の時、最大公約数(a,b)=最大公約数(b,r)となる理屈・論理を理解することだと思います。その後はその規則性で繋げていき答えが分かるという訳です。
- 麻野 なぎ(@AsanoNagi)
- ベストアンサー率45% (763/1670)
No. 5 です。 > 18の中に6は3つ、12の中に6は2つあるわけですが、 > それを求めるときになぜ12で18を割ってみようという発想になるのかわかりません。 簡単に言えば、割り算の余りは、「公約数を保存する」からです。 さて、(以下、入力が面倒なので、かけ算の×は、* で代用します) 18 = 6 * 3 12 = 6 * 2 余りの計算をするために、「引き算バージョン」で説明します。 つまり、割り算の余り=引くだけ引いてみて、残った数 なので、結果は同じになります。 今回の場合も 18÷12=1...6 と、18-12=6 で、同じ結果になりますね。 さて、18-12 は、言い換えれば、 (6 * 3) - (6 * 2) です。 共通因数の「6」があるので、分配法則が使えます。 つまり、 18 - 12 = 6 * 3 - 6 * 2 = 6 * (3 - 2) です。 ここで注意すべきことは、分配法則によって、引き算答えは、必ず、 「共通因数(上の式では6)」×「それ以外の因数の差(上の式では 3 - 2)」の形に書けるということです。 1回の引き算の答えと、割り算の余りは、厳密には、「それ以外の引数の差」の部分が異なりますが、「引けるだけ引く」と同じ結果になります。 さて、引き算の結果を見ると、必ず「共通因数」の項が残ります。 つまり、引き算の結果には、「共通因数が保存される」ということですね。さて、共通因数=どちらの因数でもあるもの(の責ですね、本当は)=公約数です。 つまり、引き算の結果は、もともとの数の公約数を保存するということになります。 実際には、何回も引き算をするのは大変なので、これと同じ結果となる、割り算の余りを使うわけです。
- 麻野 なぎ(@AsanoNagi)
- ベストアンサー率45% (763/1670)
互除法の「証明」の基礎として押さえておくべき性質は、 「a÷bのあまりが0のとき(つまり、割り切れるとき)bは、aの約数」ということです。 ついでにいえば、bはb自身の約数なので、このとき、bは、a,bの公約数となります。 次に、「aとbの公約数は、『bと(a÷b)のあまり』の公約数でもある」という性質です。 こちらは、少し説明が必要です。 a÷bの商をn、余りをrとすれば、 a=b×n + r と書けます。これはいいですか? これを、aとbの公約数xで割ってみましょう。 a÷xの余りは0 いいですね? xはaの約数でもありますから。 b÷xの余りは同じく0です。 さて、表現を変えて、a=b×n+r をxで割ってみましょう。(ここで、a÷xの余りは0だったことに注意) 前半のb×nをxで割ると、割り切れます(xはbの約数)つまり、後半の、rもxで割り切れる必要があります。(rがxで割り切れなければ、b×nがxで割り切れている以上、余りが出てしまう) つまり、rはxで割り切れることになります。 ここで、 「aとbの公約数は、『bと(a÷b)のあまり』の公約数でもある」が言えました。 この性質を使って、公約数を求めると、 1)a と b の公約数が知りたい 2)b と (a÷bのあまり) の公約数と同じ 3)1)に帰る つまり、 355 と 113 なら、 1) 355 と 113 の公約数が知りたい 2) 113 と (355÷113 の余り)の公約数だ 3) 113 と 16 の公約数が知りたい 4) 16 と (113÷16 の余り)の公約数だ 5) 16 と 1 の公約数だ 6) あ、公約数は、1だった(互いに素) という経路になります。 あと、この方法で、「最大」公約数が求まるというのは、もう少し説明が必要ですが。 あと、互除法のバリエーションとして、「互いに引く」ちうのもあります。 これは、「aとbの公約数は、aと(a-b)の公約数と等しい(ただし、引き算は大小関係でうまく方向をあわせる必要がありますが)という性質を使って、割り算をせずに公約数を求める方法です。 ただ、割り算の余りは、「引ききれるだけ引いて、残ったもの」でもあるので、やっていることは同じです。
- yoikagari
- ベストアンサー率50% (87/171)
忘れていた nは正の整数です。
お礼
ありがとうございます!
- yoikagari
- ベストアンサー率50% (87/171)
q_1はaをbで割ったときの商、r_1はaをbで割ったときの余り q_2はbをr_1で割ったときの商、r_2はbをr_1で割ったときの余り q_nはr_(n-2)をr_(n-1)で割ったときの商、r_nはr_(n-2)をr_(n-1)で割ったときの余り q_(n+1)はr_(n-1)をr_nで割ったときの商(このときの余りは0) 要するに、q_1,q_2,・・・,q_n,q_(n+1),r_1,r_2,・・・,r_nはすべて整数です。
お礼
なんとなくわかりました。 ありがとうございました!
- yoikagari
- ベストアンサー率50% (87/171)
私の知っている限り、一番やさしい証明を書いておきます。 多少の文字は覚悟してください。 「 実際に、aとb(ただしa≧b)で互防法を行ってみます。 a=b*(q_1)+r_1 b=(r_1)*(q_2)+r_2 ・・・ r_(n-2)={r_(n-1)}*(q_n)+r_n r_(n-1)=(r_n)*{q_(n+1)} でr_nがaとbの最大公約数になっていることが示せればいいわけです。 aとbの最大公約数をdとすると a=d*a'、b=d*b'とかけます(ただし、a'とb'は整数)。 r_1=a-b*(q_1)=d*{(a')-(b')*(q_1)} ですから、r_1もdで割り切れる。 したがって、r_1=d*k (ただし、kは整数) よって r_2=b-(r_1)*(q_2)=d*{(b')-k*(q_2)} となってr_2もdで割り切れることがわかる。 以上のようなことを繰り返すと、r_nもdで割り切れることがわかる。 よってr_n≦d・・・※ となります。 一方 r_(n-1)=(r_n)*{q_(n+1)} だから、r_(n-1)がnで割り切れる。 r_(n-2)={r_(n-1)}*(q_n)+r_n=r_n*[(q_n)+{q_(n+1)}] となってr_(n-2)もr_nで割り切れる。 以上を繰り返すと、r_2,r_1もr_nで割り切れることがわかる。 よって、r_1=(r_n)*k'、r_2=(r_n)*h'とかける。 (ただしk'とh'は整数) b=(r_1)*(q_2)+r_2=(r_n)*{(k')*(q_2)+h'} となってbもr_nで割り切れる。・・・△ よって、b=(r_n)*b"と書ける (ただしb"は整数) a=b*(q_1)+r_1=(r_n)*{(b")*(q_1)+(k')} となって、aもr_nで割り切れる・・・□ △と□よりr_nはaとbの公約数です。 公約数≦最大公約数ですからr_n≦d・・・○ となります ※と○よりr_n=d つまり、aとbの最大公約数がr_nであることが示されました。 」
お礼
ご回答ありがとうございます! ごめんなさい・・>_< わかりません。 q_1やr_1は何ですか?
公約数xを持つ二つの数Ax,Bxが存在する時、・・・※ Ax ÷ Bx = C ・・・・ D となるなら Ax - Bx * C = D (A- B * C ) x = D となりDもxを約数に持ちますから ※まで戻って見比べてみます 同様に 公約数xを持つ二つの数Bx,D=(A-B*C)xが存在する時、 ・・・・ D と BxをDで割った余りもxを公約数に持つことになります。「この処理を繰り返す間は比較される二つの数は必ずx以上で、その差はどんどん小さくなっていく。 最終的に割ったときのあまりが0になったとき、割る数がxになる」
お礼
ご回答ありがとうございます! >となりDもxを約数に持ちますから >※まで戻って見比べてみます どうして、Dもxを約数に持つと※まで戻って見比べてみるのですか? なにを見比べるのですか?
お礼
ありがとうございます!なんとなくわかりました。 まだ理解できないのは、 たとえば18と12の最大公約数は6で、 18の中に6は3つ、12の中に6は2つあるわけですが、 それを求めるときになぜ12で18を割ってみようという発想になるのかわかりません。