ユークリッドの互除法まとめ（証明・最大公約数・不定方程式）

東大塾長の山田です。
このページでは、「ユークリッドの互除法」について解説します。

ユークリッドの互除法を使う整数問題は、センター試験でも、一般入試でも高い頻度で出題される重要事項です。
つまり、ユークリッドの互除法の使い方はマスターしなければいけません！

今回は「ユークリッドの互除法とは何か？」という基本から、最大公約数の求め方、そして例題を解きながら1次不定方程式への応用方法についても超わかりやすく解説していきます。
ぜひ最後まで読んで、ユークリッドの互除法の使い方をマスターしてください！

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

ユークリッドの互除法を理解していくにあたって、順を追って解説をしていきます。

1.1 割り算と最大公約数の関係

2つの自然数の最大公約数について、次の定理が成り立ちます。

この割り算と最大公約数の定理を使って、2つの自然数の最大公約数を求める方法が、次の ユークリッドの互除法 です。

1.2 ユークリッドの互除法

文字ではわかりづらいところもあると思うので、具体的な数字でやり方をみてみましょう！

1.3 ユークリッドの互除法で最大公約数を求める具体例

8177と3315の最大公約数を、ユークリッドの互除法で求めてみます。

よって、8177と3315の最大公約数は221となります。

このように「（割る数）÷（余り）」を繰り返すと、最後は必ず余りが0になり、そのときの割る数が最大公約数になります！

これがユークリッドの互除法です。

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

ユークリッドの互除法の証明をしていきます。

ユークリッドの互除法の証明は、入試が記述試験の場合は頻出のテーマです。

まずは、このことを証明していきます。

【証明】

条件より　\( a = bq + r \ \cdots ① \)
移行すると　\( r = a – bq \ \cdots ② \)

\( a \) と \( b \) の最大公約数を \( \color{red}{ m } \)，\( b \) と \( r \) の最大公約数を \( \color{red}{ n } \) とします。

\( \color{red}{ m } \) は \( a \) と \( b \) の最大公約数だから、②より、\( \color{red}{ m } \) は \( r \) の約数といえます。
（∵ \( a = ma’, \ b = mb’ \) とすると \( r = ma’ – mb’q = m(a’ – b’q) \)）

よって、\( \color{red}{ m } \) は \( b \) と \( r \) の公約数といえます。

\( b \) と \( r \) の最大公約数は \( \color{red}{ n } \) だから

\( m≦n \ \cdots ③ \)

一方，\( \color{red}{ n } \) は \( b \) と \( r \) の最大公約数だから、①より、\( \color{red}{ n } \) は \( a \) の約数といえます。
（∵ \( b = na’’, \ r = nr’ \) とすると \( a = na’’q + nr’ = n(a’’q + r’) \)）

よって、\( \color{red}{ n } \) は \( a \) と \( b \) の公約数といえます。

\( a \) と \( b \) の最大公約数は \( \color{red}{ m } \) だから

\( n≦m \ \cdots ④ \)

③，④より　\( \color{red}{ m = n } \)

よって、「割られる数と割る数の最大公約数は、割る数と余りの最大公約数と等しい」ことが証明できました。

この操作を繰り返し行うと、余りは割る数より小さいので、この操作は有限回数で終わり、最後は必ず余りが0になり、最終的に最大公約数が求まるといえます。

したがって、ユークリッドの互除法が成り立ちます。

3. ユークリッドの互除法の1次不定方程式への利用

「ユークリッドの互除法は最大公約数を求める手法だ」と解説しましたが、入試でユークリッドの互除法が一番活躍するのは「1次不定方程式」の問題への利用です。

具体的に、どのようにユークリッドの互除法を応用するのかを、順を追って解説していきます。

3.1 1次不定方程式の解き方【基礎】

まずは，1次不定方程式の基本的な解き方を解説します。

【解答】

\( 3x+4y = 1 \ \cdots ① \)

\( x=3, \ y=-2 \)は、①の整数解の1つです。よって

\( 3 \cdot 3 + 4 \cdot (-2) = 1 \ \cdots ② \)

①－②から

\( 3(x-3) + 4(y+2) = 0 \)

∴　\( 3(x-3) = -4(y+2) \ \cdots ③ \)

3と4は互いに素だから、\( x-3 \)は4の倍数といえます。

よって、\( k \) を整数として、\( \color{red}{ x-3 = 4k } \) と表すことができます。

これを③に代入すると

\( 3 \cdot 4k = -4(y+2) \)

∴　\( \color{red}{ y+2 = -3k } \)

したがって、求める解は

\( x=4k+3, \ y=-3k-2 \)（\( k \)は整数）\( \cdots 【答】 \)

3.2 ユークリッドの互除法を使った1次不定方程式の解き方

次はユークリッドの互除法を使って解く、1次不定方程式の問題です。

先ほど同様、適当な1組の解を見つけます。

しかし、係数が大きく解の組を見つけるのが大変です。ここで、今回学んだ ユークリッドの互除法 を利用します！

【解答】

\( 275x+61y = 1 \ \cdots ① \)

よって、\( 275x+61y = 1 \)の整数解の1つは \( x=2, \ y=-9 \) とわかりました。
あとの流れは例題1と同じです。

①－②から

\( 275(x-2) + 61(y+9) = 0 \)

∴　\( 275(x-2) = -61(y+9) \ \cdots ③ \)

275と61は互いに素だから、\( x-2 \) は61の倍数といえます。

よって、\( k \) を整数として、\( \color{red}{ x-2 = 61k } \) と表すことができます。

これを③に代入すると

\( 275 \cdot 61k = -61(y+9) \)

∴　\( \color{red}{ y+9 = -275k } \)

したがって、求める解は

\( x=61k+2, \ y=-275k-9 \)（\( k \)は整数）\( \cdots 【答】 \)

4. ユークリッドの互除法まとめ

以上がユークリッドの互除法の解説です。
ユークリッドの互除法のやり方や、1次不定方程式への応用方法はしっかり理解できましたか？

1次不定方程式への応用では、「余りが1になるまで割っていき、整数解を求める」ことがポイントです。

今回の記事を勉強の参考にして、ユークリッドの互除法をマスターしてください！