係数が大きい一次不定方程式の特殊解を求めるが大変。教科書にあるユークリッドの互除法だと混乱してしまう。
このような悩みを解決します。
本記事では以下の順番で、一次不定方程式\(ax+by=1\)の特殊解をストレスなく見つける方法について解説していきます。
✔︎本記事の内容
１．変数のおきかえを使う方法（実践的）
２．合同式を使う方法（スマート）
３．ユークリッド互除法を使う方法（教科書）
ちなみにこの記事を書いている私の経歴は以下の通りです。
◆数学講師歴２０年以上
◆大学院の修士課程終了（専門は情報幾何学）
◆数学検定１級取得
一次不定方程式の特殊解は\(x,\;y\)の係数が大きい場合、すぐには見つかりません。
教科書ではユークリッドの互除法を用いた方法が紹介されていますが、この方法は数字に数字を代入していくため、慣れていないと混乱する可能性があります。
そこで、次のどちらかの方法をおすすめします。
・変数のおきかえをする
・合同式を使う
それでは一次不定方程式の特殊解を求める方法３つを順にご紹介していきます。
変数のおきかえをして一次不定方程式の特殊解を求める
問題
\( 71x+34y=1\) を満たす整数\( x,\; y\)の組を１つ求めなさい
まずは、変数のおきかえをする方法です。この方法が一番実践的な方法だと思います。
本質的にはユークリッドの互除法と同じ方針ですが、変数の置きかえをすることで、式変形の見通しがよくなるのがメリットです。
\(x,\; y\)の係数のうち、大きい方を小さい方で割った商と余りで表します。
\( (34\times2+3)x+34y=1 \)
\( \Leftrightarrow 34\times 2x +3x+34y=1\)
\( \Leftrightarrow 34(2x+y)+3x=1 \cdots ①\)
ここで\(2x+y=m\)とおくと
\(34m+3x=1 \cdots ② \)
この段階で\(m=1,\; x=-11\)を見つけることができれば\(2x+y=m\)に代入して\(y=23\)が求まります。
これより整数解は\((x,\; y)=(-11,\; 23)\)
もし見つからなければ、同じ操作をもう一度行いましょう。
②において34を3で割った商と余りで表すと
\( (3\times 11+1)m+3x=1 \)
\( \Leftrightarrow 3\times 11m+m+3x=1 \)
\( \Leftrightarrow 3(11m+x)+m=1 \)
ここで\(11m+x=n\)とおくと
\( 3n+m=1 \)
ここまで式変形すれば\(n=0,\; m=1\)が見つかるはずです！
\(\quad 11m+x=n\)より, \(x=-11\)
\(\quad 2x+y=m\)より，\(y=23\)
したがって答えは\((x,\; y)=(-11,\; 23)\)
(注) ①で\(x+y=1,\; x=-11\)とするとさらに早いです！
合同式を使って一次不定方程式の特殊解を求める
次は、合同式を用いて特殊解を求める方法です。
問題
\( 71x+34y=1\) を満たす整数\( x,\; y\)の組を１つ求めなさい
合同式を使う方法はとてもスマートで、私が一番好きな解法です。
合同式の式変形については以下の記事に分かりやすく解説しています↓
\(x,\; y\)の係数で小さいほうの34をmodとして式変形をしていきます。
\( 71x+34y\equiv 1 \pmod {34} \)
\( 71x \equiv 1\pmod {34} \cdots ①\)
\( (34\cdot 2+3)x \equiv 1 \pmod {34} \)
\( 3x\equiv 1 \pmod {34} \cdots ②\)
②を24倍して
\( 72x\equiv 24 \pmod {34} \cdots ③\)
③\(-\)①より
\( x\equiv 23 \pmod {34} \)
よって\(k\)を整数とすると
\( x=34k+23 \cdots ③\)
\(k=0\)として、\(x=23\)
これをもとの式に代入して
\( 71\cdot 23 +34 \cdot y=1 \)
\( \Leftrightarrow 34y=1-71\cdot 23 \)
\( \Leftrightarrow 34y=-1632 \)
\(∴y=-48 \)
これより\((x,\; y)=(23,\; -48)\)
合同式を使った解法のメリットは以下の通りです。
・式変形がシンプル
・直接、整数解\((x,\; y)\)を求めることもできる。
具体的には③をもとの式に代入して、\(y=-48+71k\)と求まります。
ユークリッド互除法を用いて一次不定方程式の特殊解を求める
参考までに、教科書で紹介されているユークリッド互除法を用いた解法を紹介しておきます。
問題
\( 71x+34y=1\) を満たす整数\( x,\; y\)の組を１つ求めなさい
\( 71=34\times 2 +3より\)
\( 3=71-34\cdot 2 \cdots ①\)
\( 34=3\times 11 +1より\)
\( 1=34-3\cdot 11 \cdots ②\)
②に①を代入して
\begin{align*}
1&=34-3\cdot 11\\
&=34-(71-34\cdot 2)\cdot 11 \\
&=71\cdot (-11)+34 \cdot 23
\end{align*}
よって\((x,\; y)=(-11,\; 23)\)
先ほどとは違う整数の組が求まりましたが、問題ありません。
今回は、式が①と②の２つだけなので、それほど複雑ではありませんが、式が3つ、4つとなると結構やっかいです。\(a=74,\; b=34\)として解く方法もありますが、複雑さはそれほど変わりません。
結局、一次不定方程式はどの解法を使えばいいのか
今回は、一次不定方程式の解法を３つご紹介しました。
結論としては、合同式に慣れているかいないかでおすすめの解法が異なります。
おすすめ１ おきかえを使う方法
一番、実践的です。私も以前はこの方法を愛用していました。
合同式に慣れていない場合は、この方法がおすすめです！
おすすめ２ 合同式を使う方法
一番スマートな方法です。
合同式の式変形に慣れている場合は、この方法がおすすめです！
特殊解だけでなく、直接整数解を求めることが可能なのでとても便利です。右辺が１でない場合も解くことが可能ですよ！
私自身、最近はこの方法で解くことがほとんどです。
最後に私も実際に使った、整数問題攻略のための「おすすめの問題集」をご紹介しておきます。
解説が丁寧で詳しいのでおすすめです。難関大まで対応可能です。
合同式やおきかえを使って一次不定方程式を解く方法はありませんが、著者独自の視点が非常に面白い！
私は１章を何度もくり返し勉強しました。
おきかえを使った解説や合同式の基本についての記述があります。
整数は例題１８題、演習１８題のみですが、良問揃いで力をつけるのには最適です。
最後まで、お読みいただき、ありがとうございました。
