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

【勉強法はこちら】

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

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

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

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

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

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

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

割り算と最大公約数

2つの自然数 \( a, \ b \) について,\( a \) を \( b \) で割ったときの商を \( q \),余りを \( r \) とすると

「\( a \) と \( b \) の最大公約数」は,「\( b \) と \( r \) の最大公約数」に等しい

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

 

1.2 ユークリッドの互除法

ユークリッドの互除法

次のように2つの自然数 \( a, \ b \) の最大公約数を求める方法を ユークリッドの互除法,または単に互除法という。

  1. \( a \) を \( b \) で割り,余り \( r \) を求める
  2. \( b \) を①で求めた余り \( r \) で割り,その余り \( r_1 \) を求める
  3. \( r \) を②で求めた余り \( r_1 \) で割り,その余り \( r_2 \) を求める…
    \( \cdots \cdots \)
  4. この操作を繰り返すと余りが必ず0になる(割り切れる)。余りが0になったときの割る数が,求める最大公約数になる

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

 

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

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

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

 

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

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

 

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

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

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

2つの自然数 \( a, \ b \) について,\( a \) を \( b \) で割ったときの商を \( q \),余りを \( r \) とすると

「\( a \) と \( b \) の最大公約数」は,「\( b \) と \( r \) の最大公約数」に等しい

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

【証明】

条件より \( 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’, \ n = 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次不定方程式の基本的な解き方を解説します。

例題1

次の方程式の整数解をすべて求めよ。
 \( 3x+4y = 1 \)

1次不定方程式を解く方針

整数解をすべて求めるには、まず「方程式の適当な1組の解」を見つける

【解答】

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

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

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

①-②から

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

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

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

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

これを③に代入すると

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

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

したがって、求める解は

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

 

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

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

例題2

次の方程式の整数解をすべて求めよ。
 \( 275x+61y = 1 \)

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

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

【解答】

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

①の整数解の1つを見つけるために、ユークリッドの互除法を利用します。

275と61に互除法の計算を行うと

\( 275 = 61 \cdot 4 + 31 \ \Rightarrow \ 31 = 275 – 61 \cdot 4 \)

\( 61 = 31 \cdot 1 + 30 \ \Rightarrow \ 30 = 61 – 31 \cdot 1 \)

\( 31 = 30 \cdot 1 + 1 \ \Rightarrow \ 1 = 31 – 30 \cdot 1 \)

一番下の式に、上の式を順に代入して整理していくと

\( \begin{align}
\color{red}{ 1 } & = 31 – 30 \cdot 1 \\
\\
& = 31 – (61 – 31 \cdot 1) \cdot 1 \\
\\
& = 31 \cdot 2 + 61 \cdot (-1) \\
\\
& = (275 – 61 \cdot 4) \cdot 2 + 61 \cdot (-1) \\
\\
& \color{red}{ = 275 \cdot 2 + 61 \cdot (-9) }
\end{align} \)

ゆえに

\( \color{red}{ 275 \cdot 2 + 61 \cdot (-9) = 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になるまで割っていき、整数解を求める」ことがポイントです。

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

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です