【１次不定方程式】整数解(一般解)を「合同式(mod)」で簡単に求める裏ワザ【練習問題つき】

１次不定方程式の整数解(一般解)を簡単に求める方法を知りたい

ユークリッドの互除法で求めるやり方が苦手だ・・・

合同式(mod)を使うと簡単に解けるって聞いたけど、やり方を分かりやすく教えてほしい！

こんなお悩みを解消します。

このページを読めば、例えば

のような １次不定方程式の整数解（一般解）を求める問題 を 合同式(mod) を使って一瞬で解けるようになります。

ライバルと大きく差をつけられるので、ぜひマスターしましょう！

【１次不定方程式】整数解(一般解)を「合同式(mod)」で求める裏ワザ

１次不定方程式 $ $$ax+by = c$$ $ の整数解（一般解）の求め方（裏ワザ） はこちら。

この手順でやるとスムーズに整数解（一般解）が出せます。

【１次不定方程式】整数解の特殊解・一般解のちがい

１次不定方程式 $ $$ax+by = c$$ $ の整数解 についておさらいです。

不定方程式の整数解には「特殊解」と「一般解」の2種類があります。

例えば

問題文の続きが、どう書いてあるか？によって「特殊解」と「一般解」に分かれます。

特殊解：整数解を1つ（1組）求めよ。

もし問題文に「〜整数解を 1つ（1組）求めよ。」と書いてあったら「特殊解」です。

「特殊解」というのは、例えば

のように、不定方程式にあてはまる「具体的な解」$(x,y)$の組 のことです。

特殊解は、この他にも

など無数にあります。

不定方程式の 特殊解 の求め方についてはこちら。

関連記事

【１次不定方程式】整数解(特殊解)を「合同式(mod)」で一瞬で見つける裏ワザ【練習問題つき】

１次不定方程式の整数解(特殊解)を見つけるときに、ユークリッドの互除法を使うやり方だとよく分からない・・・ 合同式(mod)を使うと簡単に求められるって聞いたけど、やり方を分かりやすく教えてほしい！ こういった要望に応えます。 […]

一般解：整数解をすべて求めよ。

逆に「〜整数解を すべて 求めよ。」と書いてあったら「一般解」を求めます。

「一般解」は

のように、整数 $k$ を使って「どんな解でも自由に表せる形」になっている解のことです。

例えば

こんな感じで、整数 $k$ の値に色んな数を代入することで、すべての整数解 $(x,y)$ を表すことができます。

整数解の求め方 2つ

不定方程式の整数解の求め方は、大きく分けて「合同式（mod）」と「ユークリッドの互除法」の2つあります。

結論から言うと「合同式（mod）」を用いた解法がオススメです。

合同式（mod）を使うメリットは

という感じで、いいこと尽くめです。

一方、教科書に書かれているような「ユークリッドの互除法」を使った解法は

• 特殊解を求める計算がややこしく、計算ミスが起こりやすい
• 特殊解を求めてから一般解を求めるため、時間がかかる

というデメリットがあります。

数学のテストは時間との戦いです。

素早く正確に計算できる「合同式（mod）」を使ったやり方に慣れておくと、圧倒的に有利だと言えます。

【例題1】不定方程式 $5x+3y=1$ をみたす整数解をすべて求めよ。

それでは、実際に問題を通してマスターしていきましょう！

もちろんこれくらいの不定方程式なら、テキトーに整数を代入していけば

のように整数解（特殊解）がすぐ見つかるかもしれません。

ですが、あえて練習として 合同式（mod）を使って、一気に一般解を求めてみます。

① $x,y$ の係数（$5$と$3$）のどちらかで合同式（mod）を考える

$x,y$ の係数（$5$と$3$）のどちらでも答えは出せますが、今回はセオリー通りに小さい方の $\color{red}{3}$ を法とした合同式（mod）を考えてみます。

この合同式（mod）の意味は、簡単に言うと

$ $　$(5x+3y$ を $3$ で割った余り$)=1$

ということ。

さらに、$\color{red}{3}y$ は $3$の倍数（$3$で割り切れる）なので

$ \color{red}{3}y \equiv 0 \pmod 3 $　より、結局

②「$ x \equiv □ \pmod 3 $」の形にする

$ 5x = (\color{red}{3} \cdot 1 + 2)x = \color{red}{3}x + 2x$

つまり「$5x$ を $\color{red}{3}$ で割ると $2x$ 余る」ことに注目して

$\color{red}{3}x$ は $3$の倍数（$3$で割り切れる）なので

両辺を2倍して

③ $x=3k + □$（$k$は整数）とおく

手順② で求めた合同式

は「$x$ を $\color{red}{3}$ で割ると $−1$ 余る」という意味なので

とおけます。

④ 不定方程式に代入して $y$ を求める

手順③ で求めた $x$ の値を、不定方程式に代入して $y$ を求めます。

こんな流れで、合同式を使えば一気に 一般解 が求められます。

ここまでの流れをまとめると以下の通り。

【解答】を見る

【解答】

$5x+\color{red}{3}y=1$ より

$ $　$ 5x + \require{cancel} \bcancel{ \color{red}{3}y } \equiv 1 \pmod {\color{red}{3}} $

$ $　∴ $ 5x \equiv 1 \pmod 3 $ ・・・①

$ $　∴ $ \require{cancel} \bcancel{ \color{red}{3}x } + 2x \equiv 1 \pmod 3 $

$ $　∴ $ 2x \equiv 1 \pmod 3 $

$ $　∴ $ 4x \equiv 2 \pmod 3 $ ・・・②

① $−$ ②より

$ $　$ x \equiv −1 \pmod {\color{red}{3}} $

よって

$ $　$x = \color{red}{3}k −1 $（$k$は整数）

とおける。

これを $5x+3y=1$ に代入して

$ $　$ 5(3k −1) +3y = 1 $

$ $　∴ $ 3y = −15k + 6 $

$ $　∴ $ y = −5k +2 $

以上より

$ $　$x = 3k −1 , \, y = −5k +2 $（$k$は整数）

補足：①の別解

手順①：「$x,y$ の係数（$5$と$3$）のどちらかで合同式（mod）を考える」で mod $3$ のもとで考えましたが、$\color{red}{5}$ を使っても答えが求められます。

（注1）  3 と 5 が互いに素 でないときは、両辺を 3 で割ってはいけません。

不定方程式は、このルールを守らないと 正しい答えが出ない ので要注意！

（注2）はじめの【解答】の
「$x = 3k −1 , \, y = −5k +2 $」と書き方は違いますが、どちらも同じ意味です。

例えば

【解答】：$k=1$ のとき $ \begin{cases}
x = 3 \cdot 1 −1 = 2 \\
\\
y = −5 \cdot 1 +2 = −3 \\
\end{cases}$

【別解】：$k=−1$ のとき $ \begin{cases}
x=−3 \cdot (−1)−1 = 2 \\
\\
y= 5\cdot (−1) + 2 = −3 \\
\end{cases}$

のように、代入する $k$ の値をうまいこと考えると、同じ整数解 $(x,y)$ を表せますね。

補足：②の別解

手順②：「$ 5x \equiv 1 \pmod 3 $」から
「$ x \equiv □ \pmod 3 $」の形にするところは、他にもやり方があります。

$ $　$ \color{green}{5}x \equiv 1 \enspace (\text{mod} \enspace \color{red}{3} ) $

の右辺が 5 の倍数になるまで 3 を足し続けると

$ 5x \equiv 1 + \color{red}{3} \equiv 4 \\
\enspace \enspace \equiv 4 + \color{red}{3} \equiv 7 \\
\enspace \enspace \equiv 7 + \color{red}{3} \equiv 10 \enspace (\text{mod} \enspace \color{red}{3} ) $

よって

5 と 3 は互いに素 なので、両辺を 5 で割ると

と計算してもOK。

この他にも色んなやり方が考えられるので、自分で試してみましょう。

参考：合同式を利用しない解法

参考までに、教科書に載っているような「合同式を利用しない（ふつうの）解法」も書いておきます。

整数解（特殊解）を見つけてから、一般解を求めるまでの手順です。

となります。

問題によっては、こっちの書き方を誘導される場合もあるのでちゃんと理解しておきましょう。

【例題2】不定方程式 $7x−11y=5$ をみたす整数解をすべて求めよ。

今度も 合同式（mod） を使って、一気に 一般解 を求めてみましょう。

① $x,y$ の係数（$7$と$−11$）のどちらかで合同式（mod）を考える

$x,y$ の係数（$7$と$−11$）のどちらでもOKですが、$−11y$ のように係数がマイナスの数は、できれば左辺に残したくない（消去したい）ですね。

そこで、mod $11$ で合同式を作ってみると

②「$ x \equiv □ \pmod {11} $」の形にする

左辺に $11x$ を足すと

右辺に $11$ を足すと

2 と 11 は互いに素 なので、両辺を 2 で割ると

右辺に 11 を足して

2 と 11 は互いに素 なので、両辺を 2 で割ると

③ $x=11k + □$（$k$は整数）とおく

手順② で求めた合同式

は「$x$ を $\color{red}{11}$ で割ると $7$ 余る」という意味なので

とおけます。

④ 不定方程式に代入して $y$ を求める

手順③ で求めた $x$ の値を、不定方程式に代入して $y$ を求めます。

以上です。

ここまでの流れをまとめると以下の通り。

【解答】を見る

【別解】

$7x − \color{red}{11}y=5$ より

$ $　$ 7x − \require{cancel} \bcancel{ \color{red}{11} y } \equiv 5 \pmod { \color{red}{11} } $

$ $　∴ $ 7x \equiv 5 \pmod {11} $ ・・・①

$ $　∴ $ 18x \equiv 5 \pmod {11} $

$ $　∴ $ 18x \equiv 16 \pmod {\color{red}{11}} $

2 と 11 は互いに素 なので、両辺を 2 で割ると

$ $　$ 9x \equiv 8 \pmod {11} $ ・・・②

② $−$ ①より

$ $　$ 2x \equiv 3 \pmod {11} $

$ $　∴ $ 2x \equiv 14 \pmod {\color{red}{11}} $

2 と 11 は互いに素 なので、両辺を 2 で割ると

$ $　∴ $ x \equiv 7 \pmod {11} $

よって

$ $　$x = \color{red}{11}k +7 $（$k$は整数）

とおける。

これを $7x−11y=5$ に代入して

$ $　$7(11k +7)−11y=5$

$ $　∴ $ −11y=−77k−44$

$ $　∴ $ y = 7k +4 $

以上より

$ $　$x = 11k +7 , \, y = 7k +4 $（$k$は整数）

補足：①の別解

手順①：「$x,y$ の係数（$7$と$−11$）のどちらかで合同式（mod）を考える」で mod $11$ のもとで考えましたが、$\color{red}{7}$ を使っても答えが求められます。

こんな感じです。

補足：②の別解

手順②：「$ 7x \equiv 5 \pmod {11} $」から
「$ x \equiv □ \pmod {11} $」の形にするステップの別解です。

$ $　$ \color{green}{7}x \equiv 5 \pmod { \color{red}{11} } $

の右辺が 7 の倍数になるまで 11 を足し続けると

$ 7x \equiv 5 + \color{red}{11} \equiv 16 \\
\enspace \enspace \equiv 16 + \color{red}{11} \equiv 27 \\
\enspace \enspace \equiv 27 + \color{red}{11} \equiv 38 \\
\enspace \enspace \equiv 38 + \color{red}{11} \equiv 49 \pmod { \color{red}{11} } $

よって

7 と 11 は互いに素 なので、両辺を 7 で割ると

と計算してもOK。

【練習問題】１次不定方程式の整数解(一般解)を「合同式(mod)」で求める

ここまで学んだことを活かして、練習問題を解いてみましょう！

【問題】不定方程式 $45x−56y=13$ をみたす整数解をすべて求めよ。

【解答】を見る

【解答】

$45x − \color{red}{56}y=13$ より

$ $　$ 45x − \require{cancel} \bcancel{ \color{red}{56} y } \equiv 13 \pmod { \color{red}{56} } $

$ $　∴ $ 45x \equiv 13 \pmod {56} $

$ $　∴ $ 45x \equiv 69 \pmod {\color{red}{56}} $

$3$ と $\color{red}{56}$ は互いに素なので、両辺を $3$ で割ると

$ $　$ 15x \equiv 23 \pmod {56} $

$ $　∴ $ 15x \equiv 79 \pmod {56} $

$ $　∴ $ 15x \equiv 135 \pmod {\color{red}{56}} $

$15$ と $\color{red}{56}$ は互いに素なので、両辺を $15$ で割ると

$ $　$ x \equiv 9 \pmod {\color{red}{56}} $

よって

$ $　$x = \color{red}{56}k +9 $（$k$は整数）

とおける。

これを $45x − 56y=13$ に代入して

$ $　$45(56k +9) − 56y=13$

$ $　∴ $ 45 \cdot 56k +405 − 56y=13 $

$ $　∴ $ −56y=−45 \cdot 56k −392 $

$ $　∴ $ y=−45k −7 $

以上より

$ $　$x = 56k +9 , \, y=−45k −7 $（$k$は整数）

以上です。お疲れ様でした！

【まとめ】１次不定方程式の整数解(一般解)を「合同式(mod)」で求める裏ワザ

最後に今回のまとめです。

１次不定方程式 $ $$ax+by = c$$ $ の整数解（一般解）の求め方（裏ワザ） は以下の通り。

何度も練習してスムーズに整数解（一般解）が出せるようにしておきましょう！

質問・要望があれば気軽にコメントください👍