【数学】一次不定方程式の整数解を一瞬で見つける！

一次不定方程式を解くときは、特殊解を見つけないといけませんよね。

でも係数が大きい時は見つけるのが大変です。

教科書ではユークリッドの互除法を使って特殊解を見つけると書いてありますがとても面倒です。

そこでユークリッドの互除法を使わずに一次不定方程式の特殊解を一瞬で見つける方法を教えます。

以下の方法を紹介する場合はぜひこのサイトを紹介してくれると嬉しいです。

例題1

2016年岩手大学で出題された問題です。

問題

解答

整数解を簡単に求める方法を説明します。

1. まずは不定方程式の係数の一の位を四捨五入します。

問題	89	\(\times\)	\(x\)	+	29	\(\times\)	\(y \)	=	1
手順1	90				30					係数を四捨五入する

2. 次に\(x\)と\(y\)に具体的な値を入れて\(=0\)になるようにします。各係数の最小公倍数になるように\(x\)と\(y\)を定めれば簡単に\(=0\)になります。

問題	89	\(\times\)	\(x\)	+	29	\(\times\)	\(y \)	=	1
手順1	90				30					係数を四捨五入する
手順2	90	\(\times\)	1	+	30	\(\times\)	-3	=	0	右辺を0にする

3. 前のステップで代入した値を四捨五入前の式に代入して計算する。

問題	89	\(\times\)	\(x\)	+	29	\(\times\)	\(y \)	=	1
手順1	90				30					係数を四捨五入する
手順2	90	\(\times\)	1	+	30	\(\times\)	-3	=	0	右辺を0にする
手順3	89	\(\times\)	1	+	29	\(\times\)	-3	=	2	元の方程式に代入する

\(x=1, y=-3\)の時は\(89x + 29y =2\)になることが分かりました。

ここで\(x\)の値を1増やしたり1減らしたりすると、右辺の値は89増えたり89減ったりします。また、\(y\)の値を1増やしたり1減らしたりすると、右辺の値は29増えたり29減ったりします。

つまり、\(x, y\)を変えることで、右辺には\(+89, -89, +29, -29\)の計算を自由に行うことが出来ます。

よって右辺の値を\(90(90-89=1)\)や\(30(30-29=1)\)などにすることを目標にします。\(=-1\)の形になる数字でもOKです。

基本的には元の一次不定方程式の係数の内小さい方(今回は29)に対して、右辺が\(\pm(29\pm 1)\)になることを目標とするといいでしょう。

\(\pm(29\pm 1)=\pm 30, \pm 28\)で今、右辺は2なので2を15倍して30を作ることが出来ます。(2を14倍して28を作ってもいいです。)

4. 式全体を何倍かして右辺が係数の\(\pm\)1になるようにする。

問題	89	\(\times\)	\(x\)	+	29	\(\times\)	\(y \)	=	1
手順1	90				30					係数を四捨五入する
手順2	90	\(\times\)	1	+	30	\(\times\)	-3	=	0	右辺を0にする
手順3	89	\(\times\)	1	+	29	\(\times\)	-3	=	2	元の方程式に代入する
手順4	89	\(\times\)	15	+	29	\(\times\)	-45	=	30	式全体を何倍かする

右辺を15倍したので左辺の\(x\)と\(y\)もそれぞれ15倍します。

5. の\(x\)または\(y\)を調整して右辺が1になるようにする。

\(y\)を1減らすと右辺は29減るので右辺\(=1\)を作ることが出来ます。

問題	89	\(\times\)	\(x\)	+	29	\(\times\)	\(y \)	=	1
手順1	90				30					係数を四捨五入する
手順2	90	\(\times\)	1	+	30	\(\times\)	-3	=	0	右辺を0にする
手順3	89	\(\times\)	1	+	29	\(\times\)	-3	=	2	元の方程式に代入する
手順4	89	\(\times\)	15	+	29	\(\times\)	-45	=	30	式全体を何倍かする
手順5	89	\(\times\)	15	+	29	\(\times\)	-46	=	1	\(x\)または\(y\)を調整

これでこの不定方程式の特殊解が\(x=15, y=-46\)だと分かりました。

手順は多く感じるかもしれませんが、慣れるともっと短縮して書くことが出来ます。

次の例題では短縮バージョンで解いてみます。

例題2

2020年富山大学で出題された問題です。

問題

解答

今回は整数解を1つ求める所までやります。

私が解くときのノートは下のような感じです。

97	\(\times\)	\(x\)	+	17	\(\times\)	\(y \)	=	1
100				20
		1				-5
	97		+		-85		=	12
		8				-40		96
		7				-40		-1
		-7				40		1

これでこの不定方程式の特殊解が\(x=-7, y=40\)だと分かりました。

この問題では手順5が終わった時に右辺が-1になったので、最後に式全体を-1倍しています。

数字をポンポン入れるだけでパズルみたいなので楽しいです笑。

どうしても分からないことなどがあればコメントにお願いします。返信したり、修正したりします！

この方法を紹介する場合はぜひこのサイトを紹介してくれると嬉しいです。