プログラマ専用SNS ミクプラ

Ｃ言語とは直接関係なく申し訳ないのですが、よろしくおねがいします。

互除法は、最大公約数を求めるのに最短な方法だということなので、
多少プログラミングにも関係あるということで許していただけたら幸いです。


本題ですが、互除法の仕組みがよく分かりません。。。
（数II+βまで割と新鮮な記憶で勉強済みです。）

塾でも教えてもらってもよく分からないほど、つぼってしまいましたorz
なお、ウェブ上での検索と解説サイトをいくつか読みましたが、ちょっと理解できませんでした。

*具体的な質問
画像を添付しました。
この例題で、塾の先生が言うには　x^2-x-2 に因数に最大ＡとＢの公約数が含まれている可能性があるとのことなんですが、そこから理解ができません。
なぜ、Ａ/Ｂの余りの因数に最大公約数が含まれている可能性があるのでしょうか？


おすすめの解説ページの紹介でもかまいませんので、よろしくお願いいたします。


*追記
wikipedia より、ユークリッドの互除法のページより転載

2 つの自然数（または整式） a, b (a ≧ b) について、a の b による剰余を r とすると、
 	a と b との最大公約数は b と r との最大公約数に等しいという性質が成り立つ。

この性質にすんなり頷けません・・・。

ここの解説なんかどうでしょうか。
http://www.cwo.zaq.ne.jp/bfaby300/math/gojyo.html

>softyaさん

たすかりました。
＞【かんたんユークリッドの互除法】
これのおかげで、３０分悩んでいたのが一発で分かりました！

この考え方を、利用して類題等といていってみます。
ありがとうございました。

すでに解決されたようですが、
aとbの最大公約数がbとrの最大公約数に等しいことを
どうやって説明すればよいのか考えてみました。

aをbでわるとき、その商をn、あまりをrとすると
a=bn+rとなります。
このaをbの約数で割ることを考えると、
右辺のbnはbの約数であるならばどんな数でも割り切ることができます。
ということは、rを割り切ることができるbの約数ならば、aも割り切ることができるということになります。
そのため、a、bの最大公約数はrを割り切ることのできるbの約数のうち最大のもの、
すなわち、b、rの最大公約数に等しくなります。

>Tatu さま

おお、すごくわかりやすいです！！
塾よりわかりやすかったです、ありがとうございます！
なるほど、だから r　に最大公約数の因数が隠れていた訳ですね。
助かりました。