ユークリッドの互除法の証明と別表現について

ユークリッドの互除法とは

　このページでは，$a$ と $b$ の最大公約数を $(a，b)$ と表します。

（例）$966$ と $667$ の最大公約数

$966$ $=$ $667$ $\cdot$ $1$ $+$ $299$ より $(966，667)=(667，299)$

$667$ $=$ $299$ $\cdot$ $2$ $+$ $69$ より $(667，299)=(299，69)$

$299$ $=$ $69$ $\cdot$ $4$ $+$ $23$ より $(299，69)=(69，23)$

$69$ $=$ $23$ $\cdot$ $3$ $+$ $0$ より $(69，23)=(23，0)$

よって，

$(966，667)=(23，0)=23$

∴ $966$ と $667$ の最大公約数は $23$

$a$ を $b$ で割ったときの商を $q$，余りを $r$ として立式していく感じですね。

次のような表現もあるので押さえておきましょう。

（例）$966$ と $667$ の最大公約数

$\begin{align} (966，667) &= (299，667) \\ &=(299，368) \\ &=(299，69) \\ &=(230，69) \\ &=(161，69) \\ &=(92，69) \\ &=(23，69) \\ &=(23，46) \\ &=(23，23) \\ &=(23，0) \\ &=23 \end{align}$

∴ $966$ と $667$ の最大公約数は $23$

繰り返し $(\text{大きい方})-(\text{小さい方})$ としていく感じですね。

別物に見えますが，$a=bq+r$ において $q=1$ （商を $1$）としただけのものです。

$q=1$ のとき $r=a-b$ となるので，

$a$ $=$ $b$ $\cdot$ $1$ $+$ $a-b$

これで基本表現のユークリッドの互除法を用いることで

$(a，b)=(b，a-b)$

が得られますね。入試ではこちらの表現もよく出てくるので，慌てなくても済むように押さえておきましょう。

ユークリッドの互除法の証明

ユークリッドの互除法（基本表現）の証明

$(a，b)=g_1$，$(b，r)=g_2$ とおいたとき，目標は

$g_1=g_2$

です。この「等しい」ことを証明するだけですが，ユークリッドの互除法の証明は特殊で，

$g_1≦g_2$ かつ $g_1≧g_2$

を示す方針で進めます。「以上 かつ 以下」を証明するんですね。これは知らないと無理です。

最大公約数を設定したときの扱いも知っておきましょう。（他の問題でも必要になります）

$(a，b)=g_1$，$(b，r)=g_2$ とするとき，

$\begin{cases} a=a_{1} g_1 \\ b=b_1 g_1\end{cases}\cdots \text{ ①}$ ($a_1$，$b_1$ は互いに素な自然数)

$\begin{cases} b=b_2 g_2 \\ r=r_2 g_2 \end{cases}\cdots \text{ ②}$ ($b_2$，$r_2$ は互いに素な自然数)

と表せます。（今回は最小公倍数は関係ないので，これだけでOKです。[2] の式は不要。）

さて，どうやって

$g_1≧g_2$ かつ $g_1≦g_2$

を示すかですが，(最大・・公約数) $≧$ (公約数)という事実を利用します。ここから少しややこしくなるので気合を入れてください。

【$g_1≧g_2$ の証明】

まず $g_1$ は $a$ と $b$ の最大公約数です。

ということは，$g_2$ が $a$ と $b$ の公約数であることが言えれば，

(最大・・公約数) $≧$ (公約数)

より，

$g_1$ $≧$ $g_2$

ですね。ここまで大丈夫ですか？

よって，「$g_2$ が $a$ と $b$ の公約数（すなわち $g_2$ が $a$ の約数かつ $b$ の約数） 」であることを示せば良いのですが，$g_2$ は $b$ と $r$ の最大公約数なので，$g_2$ は $b$ の約数であることは言えていますね。

したがって，$g_2$ が $a$ の約数であることを示せばOKということになります。…ここまで大丈夫？

よって，

$a=g_2×\left(\text{整数}\right)$

が目標です。$g_2$ が顔を出す式は$$\begin{cases} b=b_2 g_2 \\ r=r_2 g_2 \end{cases}\cdots \text{ ②}$$なので，これと$$a=bq+r \space \cdots (\text{☆})$$を使って示します。

$\begin{align} a &= bq+r \space \cdots (\text{☆}) \\ &= b_2g_2+r_2g_2 \enspace \text{[②を代入]} \\ &= g_2(b_2+r_2) \\ &= g_2×(\text{整数}) \end{align}$

∴ $g_2$ は $a$ の約数

はい，これでいいですね。証明の書き方は解答を参考にしてもらうと良いですが，次のような流れになります。

流れ	コメント
$g_2$ が $a$ の約数であることを示す	ここをとにかく頑張る！
$g_2$ は $b$ の約数でもあるので $a$ と $b$ の公約数	$g_2$ は $b$ と $r$ の最大公約数より
$g_1$ は $a$ と $b$ の最大・・公約数なので $g_1$ $≧$ $g_2$	(最大・・公約数) $≧$ (公約数)

あとは，同様にして $g_1≦g_2$ を示します。ほとんど同じですが，念のため流れを確認しておきます。

【$g_1≦g_2$ の証明】

まず $g_2$ は $b$ と $r$ の最大公約数。

よって，$g_1$ が $b$ と $r$ の公約数であることが言えれば，

(公約数) $≦$ (最大・・公約数)

より，

$g_1$ $≦$ $g_2$

よって，「$g_1$ が $b$ と $r$ の公約数（すなわち $g_1$ が $b$ の約数かつ $r$ の約数） 」であることを示せば良いが，$g_1$ は $a$ と $b$ の最大公約数なので，$g_1$ は $b$ の約数であることは言えている。

したがって，$g_1$ が $r$ の約数であることを示せばOK。よって，

$r=g_1×\left(\text{整数}\right)$

が目標。$g_1$ が顔を出す式は$$\begin{cases} a=a_{1} g_1 \\ b=b_1 g_1\end{cases}\cdots \text{ ①}$$なので，これと$$a=bq+r \space \cdots (\text{☆})$$を使って示す。

$\begin{align} a &= bq+r \space \cdots (\text{☆}) \\r &= a-bq \enspace \text{[移項]} \\ &= a_1g_1-b_1g_1q \enspace \text{[①を代入]} \\ &= g_1(a_1-b_1q) \\ &= g_1×(\text{整数}) \end{align}$

∴ $g_1$ は $r$ の約数

はい，できました！実際の証明の流れは，次のようになります。

流れ	コメント
$g_1$ が $r$ の約数であることを示す	ここをとにかく頑張る！
$g_1$ は $b$ の約数でもあるので $b$ と $r$ の公約数	$g_1$ は $a$ と $b$ の最大公約数より
$g_2$ は $b$ と $r$ の最大・・公約数なので $g_1$ $≦$ $g_2$	(公約数) $≦$ (最大・・公約数)

ユークリッドの互除法（別表現）の証明

　方針は基本表現の場合と同じです。計算は少し変わりますが，方針（流れ）は同じであることの理解が重要です。一度、自分の手で証明してみましょう。単に真似するのではなく，

・「以上 かつ 以下」を証明

・(最大公約数) $≧$ (公約数) を利用

この 2 つのことを意識して自分なりに答案を作りましょう。

入試においての扱い

　ユークリッドの互除法の証明は大学入試でたびたび出題されます。経験がなければまず無理なので，定石として押さえておくのが良いでしょう。注意としては証明を「丸暗記」するのではなく，

・「以上 かつ 以下」を証明

・(最大公約数) $≧$ (公約数) を利用

という部分を定石として覚えておき，それ以外はその場で考えることです。証明の流れも変わることはないので，全体の流れも覚えてしまうのも良いでしょう。

　ユークリッドの互除法は，さまざまな表現で出題されます。今回は頻出の 2 パターンを扱いましたが，設定を加えればいくらでも表現を変えることができます。これらすべてを「丸暗記」するわけにはいきませんが，今回の定石を覚えておけば必ず対応できます。今後の学習でユークリッドの互除法の証明をする場面があれば「定石をもとに答案を作り上げる」ことを意識すると良いでしょう。

まとめ

（参考）$(a，b)=g_1$，$(b，r)=g_2$ とするとき，$g_1$ $≧$ $g_2$ を示すときの流れ

流れ（$g_1$ $≧$ $g_2$ の証明）	コメント
$g_2$ が $a$ の約数であることをなんとかして示す！	ここをとにかく頑張る！
$g_2$ は $b$ の約数でもあるので $a$ と $b$ の公約数	$g_2$ は $b$ と $r$ の最大公約数より
$g_1$ は $a$ と $b$ の最大・・公約数なので $g_1$ $≧$ $g_2$	(最大・・公約数) $≧$ (公約数)