coloringname.com
ユークリッドの互除法の1次不定方程式への利用 「ユークリッドの互除法は最大公約数を求める手法だ」と解説しましたが、入試でユークリッドの互除法が一番活躍するのは「1次不定方程式」の問題への利用です。 具体的に、どのようにユークリッドの互除法を応用するのかを、順を追って解説していきます。 3. 1 1次不定方程式の解き方【基礎】 まずは,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.
今回は、「 ユークリッドの互除法 」を用いた最大公約数の求め方や、 \(49x-23y=1\) のような不定方程式の解き方について、 なるべくわかりやすいように解説しています。 第3章では、「ユークリッドの互除法」の証明もしています。 興味のある人はぜひご覧ください。 1. ユークリッドの互除法 「ユークリッドの互除法」とは 「ユークリッドの互除法」はいつ使うか 「 ユークリッドの互除法 」は、最大公約数を求めるときに使います。 例えば、「\(24\)と\(36\)の最大公約数」は簡単に求めることができると思います。 \(24\)の約数は、\(\{1, 2, 3, 4, 6, 12, 24\}\) \(36\)の約数は、\(\{1, 2, 3, 4, 6, 9, 12, 18, 36\}\) なので、「\(24\)と\(36\)の最大公約数」は\(12\)です。 では、「\(1638\)と\(2100\)の最大公約数」はいくつでしょうか? 先程のように約数を全て求めるというのはなかなか大変だと思います。 そこで登場するのが「ユークリッドの互除法」です。 「ユークリッドの互除法」は数が大きくなっても、 簡単に最大公約数を求めることができます。 では、次は「ユークリッドの互除法」の使い方を学んでいきしょう。 「ユークリッドの互除法」の意味 次の定理が「 ユークリッドの互除法 」です。 ユークリッドの互除法 \(a, b\)を自然数とし、\(a>b\)とする。 \(a, b\) の最大公約数は、次のようにして求めることができる。 \(a\) を \(b\) で割った余り \(r_1\) を求める \(b\) を \(r_1\) で割った余り \(r_2\) を求める \(r_1\) を \(r_2\) で割った余り \(r_3\) を求める 以下同様に繰り返し、\(r_{n-1}\) を \(r_n\) で割った余り \(r_{n+1}\) が \(0\) となるとき、\(r_n\) は \(a, b\) の最大公約数に等しい。 何言ってるか全然わかんないよ!! という人のために、もう少しわかりやすく考えてみましょう。 \(a\)を\(b\)で割った商が\(q_1\)、余りが\(r_1\)のとき、 $$a=b\times q_1 + r_1$$ という関係式が成り立ちますね?
東大塾長の山田です。 このページでは、 「 ユークリッドの互除法 」について解説します 。 ユークリッドの互除法を使う整数問題は、センター試験でも、一般入試でも高い頻度で出題される重要事項です 。 つまり、 ユークリッドの互除法の使い方はマスターしなければいけません! 今回は「ユークリッドの互除法とは何か?」という基本から、最大公約数の求め方、そして例題を解きながら1次不定方程式への応用方法についても超わかりやすく解説していきます。 ぜひ最後まで読んで、ユークリッドの互除法の使い方をマスターしてください! 1. ユークリッドの互除法とは? ユークリッドの互除法を理解していくにあたって、順を追って解説をしていきます。 1. 1 割り算と最大公約数の関係 2つの自然数の最大公約数について、次の定理が成り立ちます。 割り算と最大公約数 この割り算と最大公約数の定理を使って、2つの自然数の最大公約数を求める方法が、次の ユークリッドの互除法 です。 1. 2 ユークリッドの互除法 ユークリッドの互除法 文字ではわかりづらいところもあると思うので、具体的な数字でやり方をみてみましょう! 1. 3 ユークリッドの互除法で最大公約数を求める具体例 8177と3315の最大公約数を、ユークリッドの互除法で求めてみます。 よって、 8177 と3315 の最大公約数は 221 となります。 このように 「(割る数)÷(余り)」を繰り返すと、最後は必ず余りが0になり、そのときの割る数が最大公約数になります! これがユークリッドの互除法です。 2.
ユークリッドの互除法と不定方程式 ユークリッドの互除法を使うことで、次のような不定方程式を解くこともできます。 例題2 次の方程式の整数解\(x, y\)を一つ求めよ。 $$49x-23y=1$$ 2019年のセンター試験の問題だよ! 例題2の解説 まず、\(49\)と\(23\)にユークリッドの互除法を使います。 すると、次のようになります。 \(49=23\times 2 +3\) \(23=3\times 7 +2\) \(3=2\times 1 + 1\) 3回目で余りが\(1\)となり、不定方程式の右辺と等しくなりました。 そしたら今度は、ユークリッドの互除法で得た式を、左辺が余りの項だけになるように移行します。 例えば、「\(3=2\times1 +1\)」は、余り\(1\)についての式に変形すると、 $$1=3-2\times 1$$ になります。 他の2式についても同様の操作をすると、 \(1=3-2\times 1\) \(2=23-3\times 7\) \(3=49-23\times 2\) という3つの式が得られます。 そしたら、順番に代入していきましょう。 まず「\(1=3-2\times 1\)」に「\(2=23-3\times 7\)」を代入すると、 $$1=3-(23-3\times 7)\times 1$$ 整理すると、 $$1=3\times 8 -23$$ となります。 ここで、\(3\times 8\)は計算せずにそのままにしておこう! 次に「\(3=49-23\times 2\)」を代入します。 すると、 $$1=(49-23\times 2)\times 8 -23$$ となります。 式を整理しますが、\(49\)と\(23\)は計算せずに、そのまま残しておくようにしましょう。 すると、 $$1=49\times 8 -23\times 16 -23$$ すなわち、 $$1=49\times 8 -23\times17$$ となります。 よって、 $$x=8, y=17$$ は不定方程式 $$49x-23y=1$$ の整数解\(x, y\)の一つであることがわかりました! 例題2では、 $$49x-23y=1$$ の解の一つとして、 $$x=8, y=17$$ を得ることができましたが、実際には解は無数にあります。 では、解を全て求めるためにはどうすれば良いのでしょうか?