1次不定方程式の解き方4通り

整数不定方程式


1次不定方程式 ax+by=1 の整数解を求める方法を4通り紹介します。
ax+by=1 の解き方を知っていればax+by=c も解けます。
→1次不定方程式を解くときに知っておきたい3つの基本知識

当記事では、次の例題を4通りの方法で解きます。

例題
\(16x+21y=1\)
を満たす整数 \(x,y\) をすべて求めよ。

方法1.特殊解を自力で見つける

例えばx=4, y=-3が解だと自力で探します。
特殊解といっても特別な性質があるわけではないです。無数にある解のうち具体的な1つをどれでも特殊解と呼びます。

解答

\(16x+21y=1 \quad\cdots(1)\)
\(x=4,\,y=-3\) を代入すると
\(16\cdot 4 + 21\cdot (-3)=1\quad\cdots(2)\)
\((1)-(2)\) より
\(16(x-4)+21(y+3)=0\)
\(\Leftrightarrow 21(y+3)=16(4-x)\)
21と16は互いに素だから
\(y+3=16k\)
\(4-x=21k\)
よって
\(\color{red}{x=4-21k}\)
\(\color{red}{y=-3+16k \quad (k\textbf{は整数})}\)


方法2.特殊解をユークリッドの互除法で見つける

自力で特殊解が見つけられなくても, ユークリッドの互除法で確実に特殊解を見つけられます。
16x+21y=1 の特殊解が知りたければ, 係数の16と21に注目して割り算をします。
21÷16=1 余り5
16÷5=3 余り1
というように, 割る数と余りで割り算を続けていきます。 余りが 1 になれば終了です。これらの割り算の式を変形・代入していけば特殊解が求まります。

解答

\(21=1\cdot\color{blue}{16}+\color{blue}{5}\quad\cdots(1)\)
\(\color{blue}{16}=3\cdot \color{blue}{5} +1\quad\,\,\,\cdots(2)\)
\((2)\) に\((1)\) を代入すると
\(16=3\cdot(21-16)+1\)
\(16-3\cdot(21-16)=1\)
\(16\cdot 4 +21\cdot (-3)=1\)
よって, \(16x+21y=1\) の特殊解は
\(x=4,\,y=-3\)
一般解の求め方は方法1と同じ

方法3.分数式で考える

分数に変形して(整数)+(分数)の形にします。
(分数) の部分をさらに(整数)+(分数) の形にします。
これを, 分子の文字の係数が±1になるまで繰り返します。

解答

\(16x=-21y+1\)
両辺を16で割ると,
\(x=\dfrac{-21y+1}{16}\)
\(=\dfrac{(-16-5)y+1}{16}\)
\(=-y+\dfrac{-5y+1}{16} \cdots (1)\)

ここで, \(\dfrac{-5y+1}{16}=z\,\,(z \textbf{は整数})\) とおくと
\(5y=-16z+1\)
両辺を5で割ると,
\(y=\dfrac{-(5\cdot 3 +1)z + 1}{5}\)
\(=-3z+\dfrac{-z+1}{5} \cdots(2)\)
( 分子で \(z\) の係数が±1になった)
(2) が整数のとき
\(\color{blue}{-z+1=5k}\)
\(z=1-5k\,\,(k \textbf{は整数})\) とおける。

\(z\) を(2)に代入すると
\(y=-3(1-5k)+k=\color{red}{-3+16k}\)
\(y,z\) を(1)に代入すると
\(x=-(-3+16k)+(1-5k)\)
\(\color{red}{x=4-21k}\)


方法4.合同式を利用する

与えられた不定方程式を合同式で表します。
xまたはyの係数が±1になるように合同式を変形します。

解答

\(16x+21y=1 \)
以下, 21を法とする合同式\(\pmod{21}\)を考える。
\(16x+21y\equiv 1\)
左辺から\(21y\) を引いて
\(16x\equiv 1\)
両辺を2倍して
\(32x \equiv 2\)
左辺から\(21x\) を引いて
\(11x \equiv 2\)
両辺を2倍して
\(22x \equiv 4\)
左辺から\(21x\) を引いて
\(x\equiv 4 \pmod{21}\)
よって
\(\color{red}{x=4+21k}\)
これを\(16x+21y=1\) に代入して
\(\color{red}{y=-3-16k}\)

方法3までと符号が微妙に違いますが、kを-kでおきかえればよいだけなので全く同じ式です。


関連記事
1次不定方程式を解くときに知っておきたい3つの基本知識