公約数の性質を考える上でとても有用なユークリッドの互除法について考えを深めていきましょう。
ユークリッドの互除法
互除法の主張は次のようです。
$a,b,q,r$ を整数とする。
$a=bq+r$ のとき、
$a$ と $b$ の最大公約数は $b$ と $r$ の最大公約数と等しい。
具体的には例えば、
$70=28×2＋14$ なので、
$70$ と $28$ の最大公約数は
$28$ と $14$ の最大公約数と等しい
というような主張です。
$70$（割られる数）を $28$（割る数）で割ると商が $2$、余りが $14$ です。
元の2数の最大公約数と、割る数と余りの最大公約数が等しいと言っているのです。
なぜ成り立つかはよく分かっていないですけど、いつも使っています。
次のようです。
互除法の拡張
互除法は、より強い主張もしています。
$a=bq+r$ のとき、
$a$ と $b$ の公約数全体の集合は、$b$ と $r$ の公約数全体の集合と等しい。
先ほどの例でいえば、
$70$ と $28$ の公約数は $1,2,7,14$
$28$ と $14$ の公約数は $1,2,7,14$
となって、集合として等しくなるという主張です。
確かに同じになっていますね…
同じになるのは最大公約数に限らないってことですか？
そうです。最大公約数だけでなく、全ての公約数が一致します。
証明は驚くほど簡単です。
証明
$a=bq+r$ のとき、
(ⅰ) 自然数 $p$ が $a$ と $b$ の公約数なら、$p$ は $r$ の約数でもある。
(ⅱ) 自然数 $p$ が $b$ と $r$ の公約数なら、$p$ は $a$ の約数でもある。
(ⅰ),(ⅱ)より示された。（証明おわり）
…ええ！？これって…
定理の内容をそのまま言っているだけじゃないですか！？
本当に証明ですか？
順番に見ていきましょう。
(ⅰ)の意味するところはこうです。
「$a$ も $b$ も自然数 $p$ で割り切れるとすると、$r$ も $p$ で割り切れる。」
式 $a=bq+r$ に注目しながら考えてください。
$a$ も $b$ も自然数 $p$ で割り切れるとすると…
(ⅱ) 「$b$ も $r$ も自然数 $p$ で割り切れるとすると、$a$ も $p$ で割り切れる。」
「$a，b$ を共に割り切る数は、$b，r$ を共に割り切る。
$b，r$ を共に割り切る数は、$a，b$ を共に割り切る。」
「$a$ と $b$ の公約数は、$b$ と $r$ の公約数でもある。
$b$ と $r$ の公約数は、$a$ と $b$ の公約数でもある。」
$a$ と $b$ の公約数全体の集合は、 $b$ と $r$ の公約数全体の集合と一致する。
さらなる拡張
例えば、$70=28×1＋42$ とすると「余り $42$」って意味にはならないですけど、$28$ と $42$ の公約数はちゃんと $1,2,7,14$ になりますよね…
互除法って、式の形が $a=bq+r$ にさえなっていれば、割り算になっている必要はないんですか？
もっと言えば、$70=28×3-14$ のように $r$ を負にしてしまっても同じ議論は成立しますよ。
「$r$ が $p$ の倍数」である事と 「$-r$ が $p$ の倍数」である事は同じですから。
より一般的な主張
先ほどは互除法が言及しているものが最大公約数だけでないということを言いましたが、式変形の仕方においてより自由であるということもわかったのです。
$a=bq+r$ のとき、
$a$ と $b$ の公約数は $b$ と $r$ の公約数は集合として等しい。
（このときの $q$ は商である必要はないし、$r$ は余りである必要はない。
$a=bq+r$ という式の形さえあればいい。）
$a$ から $b$ を引けるだけ引くのが割り算ですが、実際は $a$ から $b$ を「好きな回数」引いていいのです。
演習問題
互除法を利用して問題を解いてみましょう。
自然数 $m,n$ に対して、$x=8m+n,y=5m+2n$ とおく。
$x,y$ の最大公約数を $d$ とする。
(1) $m,n$ が互いに素ならば、$d=1$ または $d=11$ であることを示せ。
(2) $m=2$ のとき、$d=11$ となる最小の自然数 $n$ を求めよ。
（学習院大）
解答
(1)
$5m+2n=2(8m+n)-11m$
と変形できるので、$x$ と $y$ の最大公約数 $d$ は、$8m+n$ と $11m$ の最大公約数である。
ここで $m,n$ が互いに素なので、$8m+n$ と $m$ も互いに素である。
よって $8m+n$ と $11m$ の最大公約数は $1$ か $11$ である。
題意は示された。
(2)
$m=2$ のとき
$x=n+16$
$y=2n+10$
となる。
$2n+10=2(n+16)-22$
より、$d$ は $n+16$ と $22$ の最大公約数。
$d=11$ となるのは
$n+16$ が $11$ の倍数かつ奇数であるときなので、
最小の $n$ は $n+16=33$ となるときで
$n=17$ （解答おわり）
解説
おっしゃる通り互除法はどちらからどちらを何個引いてもいいのですが、ここでは変数を消すことを考えました。
$m$ は消しにくいので、$n$ を消したということです。
「ここで $m,n$ が互いに素なので、$8m+nとm$ も互いに素である。」
$8m+n$ も $m$ も $p$ の倍数となりますが、これでは矛盾が発生してしまいますね。
ですが、$(8m+n)$ も $(8m)$ もどちらも $p$ の倍数なので…
「$8m+n$ と $11m$ の最大公約数は $1$ か $11$ である。」
$8m+n$ と $11m$ がどちらも $1$ と $11$ 以外で割り切れるのなら、$8m+n$ と $m$ がともにその数で割り切れることになります。
(2)
「$2n+10=2(n+16)-22$ より、$d$ は $n+16$ と $22$ の最大公約数。」
「$d=11$ となるのは $n+16$ が $11$ の倍数かつ奇数であるときなので」
かといって、$22$ の倍数になると最大公約数が $22$ になってしまうので…
もう一度解答を見てみましょう。
今度はよく読めると思いますよ。
もう一度、解答
(1)
$5m+2n=2(8m+n)-11m$
と変形できるので、$x$ と $y$ の最大公約数 $d$ は、$8m+n$ と $11m$ の最大公約数である。
ここで $m,n$ が互いに素なので、$8m+n$ と $m$ も互いに素である。
よって $8m+n$ と $11m$ の最大公約数は $1$ か $11$ である。
題意は示された。
(2)
$m=2$ のとき
$x=n+16$
$y=2n+10$
となる。
$2n+10=2(n+16)-22$
より、$d$ は $n+16$ と $22$ の最大公約数。
$d=11$ となるのは
$n+16$ が $11$ の倍数かつ奇数であるときなので、
最小の $n$ は $n+16=33$ となるときで
$n=17$ （解答おわり）
