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

１次不定方程式の整数解(特殊解)を見つけるときに、ユークリッドの互除法を使うやり方だとよく分からない・・・

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

こういった要望に応えます。

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

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

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

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

１次不定方程式 $ $$ax+by = c$$ $ の整数解（特殊解）の見つけ方（裏ワザ） はこちら。

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

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

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

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

例えば

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

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

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

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

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

特殊解は、この他にも

など無数にあります。

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

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

「一般解」は

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

例えば

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

整数解の求め方 2つ

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

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

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

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

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

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

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

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

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

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

関連記事

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

１次不定方程式の整数解(一般解)を簡単に求める方法を知りたい ユークリッドの互除法で求めるやり方が苦手だ・・・ 合同式(mod)を使うと簡単に解けるって聞いたけど、やり方を分かりやすく教えてほしい！ こんなお悩みを解消します。[…]

【例題1】不定方程式 $5x+3y=1$ をみたす整数解$(x,y)$ の組を$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=□$ が整数解のひとつ

整数解（特殊解）が求められました！

ここまでの流れを一気に書くと以下の通りです。

【解答】を見る

【解答】

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

$ $　$ 5x + \require{cancel} \bcancel{ \color{red}{3}y } \equiv 1 \enspace (\text{mod} \enspace \color{red}{3} ) $

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

$ $　∴ $ \require{cancel} \bcancel{ \color{red}{3}x } + 2x \equiv 1 \enspace (\text{mod} \enspace \color{red}{3} ) $

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

両辺を2倍して

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

① $−$ ②より

$ $　$ x \equiv −1 \pmod 3 $

よって、$ x = −1 $

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

$ $　$5 \cdot (−1) +3y=1$

∴ $y=2$

以上より

$ $　$ x = −1 , \, y = 2 $

補足：①の別解

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

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

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

補足：②の別解

手順②：「$ 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。

参考：「整数解を（すべて）求めよ。」の場合

もし、上記の【例題1】が

だった場合、さっきの $ x = −1 , \, y = 2 $ みたいな具体的な解（特殊解）ではなく、

整数 $k$ を使った 一般解 を答えなければいけません。

「え〜、ここからまだ計算しなきゃいけないの！？」

と思ったそこのキミ、安心してください！

【解法1】合同式を利用する

手順② で「$ x \equiv □ \pmod 3 $」に変形して

この合同式は「$x$ を $3$ で割ると $−1$ 余る」という意味なので

とおけます。

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

【解法2】合同式を利用しない

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

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

となります。

【例題2】不定方程式 $7x−11y=5$ をみたす整数解$(x,y)$ の組を$1$つ求めよ。

今度はすぐには整数解が見つかりそうにないですね。

こんなときは、合同式（mod） を使って求めてみましょう。

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

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

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

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

左辺に $11x$ を足すと

右辺に $11$ を足すと

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

両辺に 3 をかけて

右辺に 11 を足して

③ $x=□$ が整数解のひとつ

以上です。

この流れを一気に書くと以下の通り。

【解答】を見る

【解答】

$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 {11} $

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

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

② $−$ ①より

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

$ $　∴ $ 6x \equiv 9 \pmod {11} $ ・・・③

① $−$ ③より

$ $　$ x \equiv −4 \pmod {11} $

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

よって、$ x = 7 $

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

$ $　$7 \cdot 7−11y=5$

∴ $y=4$

以上より

$ $　$ x = 7 , \, y = 4 $

補足：①の別解

手順①：「$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)」で見つけよう！

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

【問題】不定方程式 $64x−75y=19$ をみたす整数解$(x,y)$ の組を$1$つ求めよ。

【解答】を見る

【解答】

$64x − \color{red}{75}y=19$ より

$ $　$ 64x − \require{cancel} \bcancel{ \color{red}{75} y } \equiv 19 \pmod { \color{red}{75} } $

$ $　∴ $ 64x \equiv 19 \pmod {75} $

$ $　∴ $ 64x \equiv −56 \pmod {75} $

8 と 75 は互いに素なので、両辺を 8 で割ると

$ $　$ 8x \equiv −7 \pmod {75} $

$ $　∴ $ 8x \equiv 68 \pmod {75} $

4 と 75 は互いに素なので、両辺を 4 で割ると

$ $　$ 2x \equiv 17 \pmod {75} $

$ $　∴ $ 2x \equiv 92 \pmod {75} $

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

$ $　$ x \equiv 46 \pmod {75} $

よって、$ x = 46 $

これを $64x−75y=19$ に代入して

$ $　$64 \cdot 46−75y=19$

$ $　∴ $2944 −75y=19$

$ $　∴ $−75y = −2925 $

$ $　∴ $y= 39 $

以上より

$ $　$ x = 46 , \, y = 39 $

（注）$x,y$ の係数（$64$と$−75$）のどちらでもOKですが、$−75y$ のように係数がマイナスの数は、できれば左辺に残したくない（消去したい）ですね。今回は mod $75$ で合同式を作った方が計算がラクになります。

どうでしたか？

この問題がスラスラ解ければ、大学入試で １次不定方程式 の問題が出ても安心です！

【まとめ】１次不定方程式の整数解(特殊解)を「合同式(mod)」で見つける裏ワザ

最後に、１次不定方程式の整数解（特殊解）の見つけ方（裏ワザ） をまとめておきます。

何度も練習してしっかり解けるようにしておきましょう！

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