ユークリッドの互除法がわからない

質問

ユークリッドの互除法は、どうして割っていくと公約数が求められるのですか？
公約数を求めるやり方はわかったのですが、どうしてそうなるのかわかりません。
調べて説明や証明を読んでもチンプンカンプンでした。
わかりやすく教えていただけたら嬉しいです。
よろしくお願いします。

回答No.7

lopk563

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の約数はｎの約数となる。だから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)となる理屈・論理を理解することだと思います。その後はその規則性で繋げていき答えが分かるという訳です。

参考URL：

http://www.h6.dion.ne.jp/~hsbook_a/index.html

回答No.6

麻野 なぎ（@AsanoNagi）

No. 5 です。

> １８の中に６は３つ、１２の中に６は２つあるわけですが、
> それを求めるときになぜ１２で１８を割ってみようという発想になるのかわかりません。

簡単に言えば、割り算の余りは、「公約数を保存する」からです。

さて、（以下、入力が面倒なので、かけ算の×は、* で代用します）

18 = 6 * 3
12 = 6 * 2

余りの計算をするために、「引き算バージョン」で説明します。
つまり、割り算の余り＝引くだけ引いてみて、残った数
なので、結果は同じになります。
今回の場合も 18÷12=1...6 と、18-12=6 で、同じ結果になりますね。

さて、18-12 は、言い換えれば、

(6 * 3) - (6 * 2) です。
共通因数の「６」があるので、分配法則が使えます。
つまり、
18 - 12 = 6 * 3 - 6 * 2 = 6 * (3 - 2)
です。
ここで注意すべきことは、分配法則によって、引き算答えは、必ず、
「共通因数（上の式では６）」×「それ以外の因数の差（上の式では 3 - 2）」の形に書けるということです。

１回の引き算の答えと、割り算の余りは、厳密には、「それ以外の引数の差」の部分が異なりますが、「引けるだけ引く」と同じ結果になります。

さて、引き算の結果を見ると、必ず「共通因数」の項が残ります。
つまり、引き算の結果には、「共通因数が保存される」ということですね。さて、共通因数＝どちらの因数でもあるもの（の責ですね、本当は）＝公約数です。

つまり、引き算の結果は、もともとの数の公約数を保存するということになります。
実際には、何回も引き算をするのは大変なので、これと同じ結果となる、割り算の余りを使うわけです。

回答No.5

麻野 なぎ（@AsanoNagi）

互除法の「証明」の基礎として押さえておくべき性質は、

「ａ÷ｂのあまりが０のとき（つまり、割り切れるとき）ｂは、ａの約数」ということです。
ついでにいえば、ｂはｂ自身の約数なので、このとき、ｂは、ａ，ｂの公約数となります。

次に、「ａとｂの公約数は、『ｂと（ａ÷ｂ）のあまり』の公約数でもある」という性質です。
こちらは、少し説明が必要です。

ａ÷ｂの商をｎ、余りをｒとすれば、
ａ＝ｂ×ｎ ＋ ｒ と書けます。これはいいですか？
これを、ａとｂの公約数ｘで割ってみましょう。
ａ÷ｘの余りは０ いいですね？　ｘはａの約数でもありますから。
ｂ÷ｘの余りは同じく０です。
さて、表現を変えて、ａ＝ｂ×ｎ＋ｒ をｘで割ってみましょう。（ここで、ａ÷ｘの余りは０だったことに注意）

前半のｂ×ｎをｘで割ると、割り切れます（ｘはｂの約数）つまり、後半の、ｒもｘで割り切れる必要があります。（ｒがｘで割り切れなければ、ｂ×ｎがｘで割り切れている以上、余りが出てしまう）

つまり、ｒはｘで割り切れることになります。
ここで、
「ａとｂの公約数は、『ｂと（ａ÷ｂ）のあまり』の公約数でもある」が言えました。

この性質を使って、公約数を求めると、

１）ａ と ｂ の公約数が知りたい
２）ｂ と （ａ÷ｂのあまり） の公約数と同じ
３）１）に帰る

つまり、
355 と 113 なら、

１） 355 と 113 の公約数が知りたい
２） 113 と (355÷113 の余り）の公約数だ
３） 113 と 16 の公約数が知りたい
４） 16 と （113÷16 の余り）の公約数だ
５） 16 と 1 の公約数だ
６）　あ、公約数は、１だった（互いに素）

という経路になります。
あと、この方法で、「最大」公約数が求まるというのは、もう少し説明が必要ですが。

あと、互除法のバリエーションとして、「互いに引く」ちうのもあります。
これは、「ａとｂの公約数は、ａと（ａ－ｂ）の公約数と等しい（ただし、引き算は大小関係でうまく方向をあわせる必要がありますが）という性質を使って、割り算をせずに公約数を求める方法です。

ただ、割り算の余りは、「引ききれるだけ引いて、残ったもの」でもあるので、やっていることは同じです。

お礼

ありがとうございます！なんとなくわかりました。
まだ理解できないのは、
たとえば１８と１２の最大公約数は６で、
１８の中に６は３つ、１２の中に６は２つあるわけですが、
それを求めるときになぜ１２で１８を割ってみようという発想になるのかわかりません。

回答No.4

yoikagari

忘れていた
nは正の整数です。

お礼

ありがとうございます！

回答No.3

yoikagari

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はすべて整数です。

お礼

なんとなくわかりました。
ありがとうございました！

回答No.2

yoikagari

私の知っている限り、一番やさしい証明を書いておきます。
多少の文字は覚悟してください。

「
実際に、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は何ですか？

回答No.1

noname#20377

公約数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を約数に持つと※まで戻って見比べてみるのですか？
なにを見比べるのですか？