【整数問題】ax+by=c型の不定方程式の解き方（裏ワザあり！？ユークリッド互除法、合同式の利用）

今回は、1次不定方程式の解き方について、パターン別に解説していきます。「不定方程式を簡単に解くコツってないの？」という疑問を持っている人向けに、一般的に知らているユークリッド互除法や合同式を利用した解法から、あまり知られていない裏ワザの紹介まで解説しているので、ぜひ最後まで読んでみてください！

• 自分で求めた不定方程式の解が正しいのか確認する方法が知りたい
• ユークリッド互除法を使った不定方程式の解き方が知りたい
• 合同式を使った不定方程式の解き方が知りたい
• 不定方程式を簡単に解ける裏ワザを知りたい

【はじめに】不定方程式とは？

こんにちは。数尾学（かずおまなぶ）です。

どうも！hiroemonです！今回は不定方程式について解説していきます。

今日のテーマの不定方程式ってなんだか難しそうな名前だけど、どんな方程式なの？

じゃあまずは「不定方程式とはなにか」というところから確認していこうか！

そんな優柔不断そうな方程式があるんですか？

まぁ、ちょっと違うけど…。でも、はじめはそんなイメージでokです。

でも、答えが1つに決まらないってどういうこと？

たとえば、カズオくん。この方程式はとけるかな？
\begin{cases}
x+y=3\\
x-y=1\\
\end{cases}

先生、さすがに僕でもこれは解けますよー！答えは\(\small x=2、y=1\)でしょ？

大正解！じゃあこれは？
$$\small 2x+y=1\mathbf{の整数解を求めよ}$$

えっと、連立方程式にしては式が1つ足りないなぁ。先生！問題ミスあります！

これは、問題ミスじゃなくって、本当に式は1つだけだよ！

えっ！？ん…、1つだけじゃ、答えが求められないですよ。

実はこの「\(\small 2x+y=1\)の整数解を求めよ」という問題が不定方程式だね。カズオくんのいう通りこの方程式は答えを1組に絞ることはできない。でも、「こんな条件を満たすものが答えになります！」という候補なら求めることができるんだ！この解の候補を求めることが不定方程式を解くということになるよ。

答えの候補を求めるってどういうことか全然イメージわかないんですけど…。

そしたら、次章以降で不定方程式の具体的なパターンや解き方を一緒に見ていこうか！

【徹底解説】不定方程式の解き方・考え方の基礎

では、ここからは不定方程式の解き方と考え方のコツを解説していきます。

【基本パターン】不定方程式の基礎知識

不定方程式の解き方にはいくつかパターンや解法がありますが、基本は常に1つだけなので、まずはこれを理解しましょう！

（補足）互いに素ってなんだっけ？
「2と5」や「4と15」のように同じ数では割れない数同士のこと。
逆に、「3と9」はどちらも3で割れるし、「15と20」はどちらも5で割れるので、互いに素ではない。

どういうことか、具体的に\(\small 2x=3y\)を例に解説します。この式は「2×□=3×△」が成り立つような□と△に入る数字は？という問題です。答えは無限にあって、「□=3、△=2」や「□=6、△=4」、「□=-9、△=-6」などなど。

ここで□と△に入る数にはある共通点があることに気づきます。それは□は3の倍数、△は2の倍数になるということ。なので、\(\small x=3k\)、\(\small y=2k\)と表せるよ、ということです。

なぜこのようになるのかというと、\(\small 2x=3y\)は、左辺は2の倍数（\(\small 2x\)は2×□の形だから）、右辺は3の倍数ですが、通常、2の倍数と3の倍数はイコールにはなりません。

2の倍数＝\(\small 2,4,\color{blue}6,8,10,\color{blue}{12},\cdots\)
3の倍数=\(\small 3,\color{blue}6,9,\color{blue}{12},\cdots\)

でも、これらが\(\small 2x=3y\)という等式でイコールになるときがあって、それが両辺が\(\small 2 \times 3 =6\)の倍数になるときです。\(\small 2x\)が6の倍数になるということは、\(\small x\)が3の倍数になりますし、\(\small 3y\)が6の倍数になるということは、\(\small y\)が2の倍数になるわけです。

（補足）\(\small a\)、\(\small b\)が互いに素じゃないといけないの？
たとえば、
$$8x=6y$$
のように、\(\small a\)、\(\small b\)が互いに素ではない場合、\(\small x=3, y=4\)のような組み合わせも答えになってしまい、必ずしも\(\small x\)が6の倍数、\(\small y\)が8の倍数ではなくてもよくなってしまいます。そのため、互いに素になっていることが重要です。

（補足）答えは\(\small x=3k\)、\(\small y=2k’\)にはならないの？
よくある質問ですがこれは間違い。理由は、\(\small \color{red}{x=3k}\)とおくと、\(\small y\)の値は\(\small 2x=3y\)に代入することで
\begin{equation}
\begin{split}
2\cdot \color{red}{3k}&=3y\\
2k&=y
\end{split}
\end{equation}
となるので、必ず\(\small y=2k\)となります。

このあと、不定方程式の代表パターンを2つ紹介しますが、いずれもこの基本パターンに帰着させて解く考え方になります。

【パターン1】\(\small ax+by=1\)型の解法のポイント

では具体的な方法を例題で確認していきます。

【例題1】\(\small ax+by=1\)の具体的な解き方

【補足説明】自分の答えが解答と違うときの検算の方法は？

不定方程式の解は、特殊解を何にするかによって解答の表現が変わります。実際には同じ答えを表していても答えの見え方が変わってしまうわけですね。

たとえば、例題1の問題で特殊解として\(\small x=9,y=-5\)を選んだ場合、答えは\(\small \color{red}{x=7k+9,\space y=-4k-5}\)となります。もちろんこれも正解です。

ただ、参考書などの解答は1つしかかかれないので、自分の答えがあっているか不安になりますよね。そんなときは、次の方法で確かめましょう！

たとえば、例題1であれば解答の\(\small x=7k\color{red}{+2},\space y=-4k\color{blue}{-1}\)で\(\small k=0\)とすると、\(\small x=\color{red}{+2}\)、\(\small y=\color{blue}{-1}\)となり、確かに特殊解になっていますね。

\(\small k=1\)のときは、\(\small (x,y)=(9,-5)\)なりますが、問題文左辺に代入すると

\begin{equation}
\begin{split}
(左辺)&=4x+7y\\
&=4\cdot9+7\cdot(-5)\\
&=36-35\\
&=1=(右辺)\\
\end{split}
\end{equation}

となり成り立つので、これで検算完了です。

この検算方法は、今回のパターンに限らずどんな不定方程式のパターンでも使えるのでぜひ活用してみてください！

【パターン2】\(\small ax+by=c\) 型の解法のポイント

【例題2】\(\small ax+by=c\) の具体的な解き方

特殊解が見つけずらい場合の対処法

ここまでで、不定方程式の解き方の基礎固めはできたのでここからはいよいよ実践編に入ります。これまでの例題では特殊解を自力で見つけてきましたが、\(\small x,y\)の係数が大きくなるにつれて特殊解が見つけずらくなります。そんな場合の対処法を身につけましょう！

例題3：特殊解がすぐにわからない不定方程式

ここでは、例題3のような問題に対して自力で特殊解を見つける方法以外に、特殊解が見つけずらい場合の対処方法を3つ紹介します。裏ワザ的方法もあるのでしっかりと理解して使いこなせるようになりましょう。

【対処法1】ユークリッドの互除法の利用

\(\small 155x＋42y＝1\)を満たす特殊解をぱっと見で見つけるのは大変です。そんなときは、ユークリッドの互除法が利用できます。一番よく使われている解法になります。

では、ユークリッドの互除法を利用した解き方を解説します。ユークリッドの互除法とは、一言でいうと『お互いに除（割り算）をしていく方法』です。\(\small x,y\)の係数をお互いに割り算していくことで特殊解を見つけることができます。

ここからの解き方は、パターン1と同じなので簡単に解説します。\(\small 155x+42y=1\)から\(\small 155\cdot(-13)+42\cdot48=1\)を引き算することで\(\small 155(x+13)=-42(y-48)\cdots⑤\)を得るので、\(\small x+13=42k\cdots⑥\)（\(\small k\)は整数）より、\(\small \color{red}{x=42k-13}\)。⑥を⑤に代入することで\(\small \color{red}{y=-155k+48}\)。

（解答）
\(\small \quad \color{red}{x=42k-13,\space y=-155k+48}\)（\(\small k\)は整数）

【対処法2】簡易的互除法の利用

『簡易的互除法』という名前は私が勝手につけてます…（なので覚えなくって大丈夫）。この方法はユークリッドの互除法がベースとなっているのですが、ユークリッドの互除法は関係式を代入しまくって元の式を復元する工程の計算が面倒なので、その手間を簡略化するために編み出された方法です。

やり方は言葉だと説明しにくいので、先のどの例題3を使って解きながら解説します。

まず、ユークリッドの互除法のときみたいにひたすら割り算をしていきます。このときにポイントとして、下のように横に筆算をかいていきます。

次に、下のように左上に「1」（赤丸箇所）をかき、その右に真下の数字をそのまま書きます（今回なら「4」）。

そうしたら、さらにその右側に数字をかいていくのですが、下のように、「右隣りと真下の数字を掛け算して、2つ右隣の数を足した数」を書きます（最初はちょびっと複雑かも…練習して慣らしましょう！）。

これを一番右端に到達するまで繰り返します。

最後に残った右の2つの数字に\(\small \pm\)の符号をつけたものが特殊解の候補になります。今回であれば、\(\small \pm 13, \pm 48\)が特殊解の候補です。

ここで注意したいのが、「特殊解の候補」という点です。「\(\small x\)と\(\small y\)のどちらが13または48なのか？」、「符号はプラスなのかマイナスなのか？」は、問題文の式に代入して確かめる必要があります。

見つけ方にも一応コツがあって、かけ算の1の位だけ計算して問題文の右辺になるかを確認するのがおすすめです。どういうことかというと、今回の例であれば、\(\small 155x+42y=1\)なので、仮に\(\small x=48,y=13\)（一旦符号は置いておこう）だとすると、\(\small 155 \times 48\)の計算結果の1の位は「0」、\(\small 42 \times 13\)の計算結果の1の位は「6」なので足し引きしても絶対に右辺の1になりません。なので、\(\small x=13,y=48\)と決まります。符号は、\(\small 155 \times 13\)の計算結果の1の位は「5」、\(\small 42 \times 48\)は「6」なので、右辺が1になるためには「6-5=1」にならないといけないので、\(\small 155 \times 13\)の計算結果がマイナスになればよく、\(\small x=-13\)、\(\small y=48\)と決まります。

慣れないうちは面倒だと思うかもですが、慣れてしまえばユークリッドの互除法で解くよりも素早く簡単に解けるので覚えておくと便利です（検算にもつかえる）。

特殊解が見つかったのであとの解き方は、ユークリッドの互除法と同じなので割愛します。

【対処法3】合同式の利用

最後は、合同式(mod)を利用した解法です。先に伝えておくと、合同式を使った解法は若干勘頼みな手法なので個人的にはすごく便利というわけではないですが、合同式を使うことで特殊解と合わせて一気に一般解まで求めることができるので知っておいてもよいかと思います。

実際に例題3を合同式を使って解いてみます。

【問題＆解説】不定方程式の演習問題

左辺が1ではないので、パターン2（\(\small ax+by=c\)型）の方針に従ってまずは、\(\small 67x-60y=1\)の特殊解を求める。自力で探すのは難しそうなので、簡易的互除法で特殊解を見つける（ユークリッドの互除法や合同式を使った解法はのちほど）。

\(\small 67 \times 17\)の1の位は「9」、\(\small 60 \times 19\)の1の位は「0」なので「\(\small \color{blue}{(60 \times 19)}-\color{red}{(67 \times 17)}\)」とすれば、計算結果が1になる（1の位の計算は、0-9ではなく、10-9=1と考えるのがポイント）。

よって、

\begin{equation}
\begin{split}
60\cdot19-67\cdot17&=1\\
-67\cdot17+60\cdot19&=1\\
67\cdot(-17)-60\cdot(-19)&=1 \quad (67x-60y=1\mathbf{の形によせる})\\
\end{split}
\end{equation}

となり、\(\small 67x-60y=1\)と比較することで、仮の特殊解\(\small (x,y)=(-17,-19)\)が求まった。両辺を2倍することで

$$67\cdot(-34)-60\cdot(-38)=2$$

となることから、問題文の不定方程式 \(\small 67x-60y=2\)の特殊解は、\(\small (x,y)=(-34,-38)\)となる。

\(\small 67x-60y=2\)から\(\small 67\cdot(-34)-60\cdot(-38)=2\)を引き算することで

\begin{equation}
\begin{split}
67(x+34)-&60(y+38)=0\\
67(x+34)&=60(y+38)\quad \cdots①\\
\end{split}
\end{equation}

60と67は互いに素なので、\(\small x+34=60k\)（\(\small k\)は整数）、これを式①に代入することで

\begin{equation}
\begin{split}
67\cdot \color{red}{60k}&=60(y+38)\\
67k&=y+38\\
\end{split}
\end{equation}

よって、整数解は、\(\small \color{red}{x=60k-34, \space y=67k-38}\)。

（解答）
\(\small \quad \color{red}{x=60k-34, \space y=67k-38}\)（ただし、\(\small k\)は整数）

ユークリッドの互除法の場合も、まずは\(\small 67x-60y=1\)の特殊解から求める。

\begin{equation}
\begin{split}
67&=60\cdot1+7→67-60\cdot1=7\cdots①\\
60&=7\cdot8+4\space\space →60-7\cdot8=4\cdots②\\
7&=4\cdot1+3\space\space →7-4\cdot1=3\cdots③\\
4&=3\cdot1+1\space\space →4-3\cdot1=1\cdots④\\
\end{split}
\end{equation}

④に③～①を順番に代入することで

\begin{equation}
\begin{split}
4-(7-4\cdot1)&=1\quad(\mathbf{③を代入})\\
-7+4\cdot2&=1\\
-7+(60-7\cdot8)\cdot2&=1\quad(\mathbf{②を代入})\\
60\cdot 2-7\cdot17&=1\\
60\cdot 2-(67-60\cdot1)\cdot17&=1\quad(\mathbf{①を代入})\\
-67\cdot17+60\cdot19&=1\\
67\cdot\color{blue}{(-17)}\color{red}-60\cdot\color{red}{(-19)}&=1\\
67\cdot\color{blue}{(-34)}-60\cdot\color{red}{(-38)}&=2\\
\end{split}
\end{equation}

よって、特殊解は\(\small (x,y)=(-34,-38)\)。以降の一般解の求め方は同じなので割愛。

\(\small 67x-60y=1\)の特殊解から考えてもよいが、合同式の場合は、\(\small 67x-60y=2\)の特殊解を直接求めることが可能。\(\small x,y\)の係数である67と-60のうち、絶対値が小さい60を法とした合同式を考える。

問題文から、\(\small 67x=-60y+2\)より、

$$67x \equiv 2 \pmod{60}\quad\cdots①$$

\(\small 60x \equiv 0 \pmod{60}\cdots②\)なので、①-②より、

\begin{equation}
\begin{split}
7x &\equiv 2 \pmod{60}\quad\cdots③\\
70x &\equiv 20 \pmod{60}\quad\cdots④\\
\end{split}
\end{equation}

④-①より

\begin{equation}
\begin{split}
3x &\equiv 18 \pmod{60}\\
6x &\equiv 36 \pmod{60}\quad\cdots⑤\\
\end{split}
\end{equation}

③-⑤より

$$x \equiv -34 \pmod{60}$$

よって、\(\small x=60k-34\)（\(\small k\)は整数）。\(\small 67x+60y=2\)に代入すると（頑張って計算…）

\begin{equation}
\begin{split}
67(60k-34)-60y&=2\\
67\cdot60k-2278-60y&=2\\
-60y=-67\cdot60k&+2280\\
y=67k&-38\\
\end{split}
\end{equation}

よって、、\(\small \color{red}{x=60k-34,\space y=67k-38}\)（\(\small k\)は整数）。

（補足）合同式は割り算に注意
途中式で\(\small 3x \equiv 18 \pmod{60}\)という結果が出てきたときに、全体を3で割って \(\small x \equiv 6 \pmod{60}\)としたくなりますが、これはNG。なぜなら、合同式の性質でも触れたように、modの\(\small 60\)と3は互いに素ではないため割ってはいけないのです。

本記事のまとめ

今回は不定方程式の解き方について解説しました。解き方の流れとコツは以下の通りです。

この流れで考えていけば不定方程式は必ず解けるので、演習を重ねて得意分野にしちゃいましょう！

それでは今回はここまです。お疲れさまでした！