一次不定方程式が整数解を持つ条件は…？

本記事の内容

本記事は「一次不定方程式\(ax+by+cz=k\)が整数解を持つ条件」について解説する記事です。

本記事を読むに当たり、最大公約数について知っている必要があるため、以下の記事も合わせてご覧ください。

整数の積=最大公約数×最小公倍数

...

for-spring.com

2023.02.22

一次不定方程式とは？

何よりもまず、一次不定方程式とは何か？という話をしなければなりません。
一次不定方程式というのは、
$$
ax+by+cz=k
$$
のような2つ以上の未知数を含む一つの一次方程式のことを指します。

特に、初等整数論で考察するのは、\(a,b,c,k\in\mathbb{Z}\)のときで、この方程式のすべての整数解を求めるという問題です。

実は、この方程式が整数解を持つならば、無数の整数解が存在します(後でちょっとだけお話します)。
この意味においては、古来からそれを不定方程式と呼んでいました。
別分野の代数的方程式論における不定と区別するために、近年は整数係数の方程式の整数解を求めることをディオファントス(Diophantus)の問題と呼ぶようになりました。
故に、その方程式はディオファントス方程式と呼ばれることもあります。

余談(ディオファントス)

ディオファントスは、西暦約350年頃のアレキサンドリアにいたと言われています。
方程式、特に1次方程式の解法はディオファントスの著書に初めて載せられたものですが、主として有理数、特に整数を取り扱ったものです。

ちょっとだけ踏み込んだ話

“すべての”整数解を求める？

“すべての”整数解を求める、というのはどういう意味でしょうか。
例えば、次の一次不定方程式を考えてみます。
$$
32x+57y-68z=1\tag{1}
$$
「この方程式の”解”は？」と聞かれたらどうでしょうか。
どのようにして解くかは一旦置いておいて、\((x,y,z)=(33,-3,13)\)は(1)の解です。
実際、
\begin{eqnarray}
35\times33=1056,\quad 57\times(-3)=-171,\quad -68\times13=-884
\end{eqnarray}
により、\(1056-171-884=1056-1055=1\)となるからです。
さらに、\(\displaystyle(x,y,z)=\left( \frac{27}{2},-1,\frac{11}{2}\right)\)も(1)の解です。
実際、
\begin{eqnarray}
&&32\times\frac{27}{2}+57\times(-1)-68\times\frac{11}{2}\\
&=&16\times27-57-34\times11\\
&=&432-57-374=432-431=1
\end{eqnarray}
です。

このように、”解”自体は無数にあります。
線型代数を学習している方は、一次不定方程式(1)を
$$
\begin{pmatrix}
32&57&-68
\end{pmatrix}
\left(
\begin{array}{c}
x\\
y\\
z
\end{array}
\right)=1
$$
と捉え、ランクを考えると「確かに、解は一位に定まらないよね」と分かると思います。
故に、解を”すべて”求めるということになるのです。

整数解が存在しないことがあるのか？

あるんです。
例えば、\(2x+4y+6z=1\)という一次不定方程式には、整数解が存在しません。
これは極端な例ではありますが、仮にこの一次不定方程式に整数解\((x_0,y_0,z_0)\)が存在したとすると、
$$
2x_0+4y_0+6z_0=1
$$
を満たすことになります。
しかし、\(2x_0+4y_0+6z_0=2\left( x_0+2y_0+3z_0\right)\)となるため、両辺の偶奇性が一致しません。
したがって、この一次不定方程式には整数解が存在しません。

一次不定方程式\(ax+by+cz=k\)が整数解を持つための必要十分条件

では、本題です。

変数\(x,y,z\)に任意の整数値を与えるとき、一次形式\(ax+by+cz\)が取るところの値を、この一次形式によって表される数といいます。
この用語を使えば、定理1.は

と言い換えることもできます。

定理1.の証明

①\(\Longrightarrow\)の証明

\(0\)は一次形式\(f(x,y,z)\)で表される数です。
実際、例えば\((x,y,z)=(0,0,0)\)または\((x,y,z)=(b,-a,0)\)などとすると、\(f(x,y,z)=0\)です。

また、\(k\in\mathbb{Z}\)が一次形式\(f(x,y,z)\)によって表される数であれば、すなわち\(f(x,y,z)=k\)なる\((x,y,z)\in\mathbb{Z}^3\)が存在すれば、\(-k\)もまた一次形式\(f(x,y,z)\)によって表されます。
実際、\(ax+by+cz=k\)であれば、\(a\cdot(-x)+b\cdot(-y)+c\cdot(-z)=-k\)を満たすからです。

さて、一次形式\(f(x,y,z)=ax+by+cz\)で表される整数の中で、最小の正の整数を\(k_0\)とし、その\(k_0\)が
$$
ax_0+by_0+cz_0=k_0\tag{2}
$$
と表示されたとします。
「そもそもそんな\(k_0\)が存在するのか？」という話ですが、正の整数に限定しているため、最小値が存在します。

また、一次形式\(f(x,y,z)\)によって表される任意の整数を\(k\)として
$$
ax+by+cz=k\tag{3}
$$
と置きます。
すると、\(k\)は\(k_0\)の倍数となっています。
実際、仮に\(k\)が\(k_0\)の倍数ではなかったとしましょう。
ここで次の事実を使います。

定理0.(割り算定理、剰余の定理)の証明は【代数学の基礎シリーズ】初等整数論編 その2を御覧ください。

定理0.(割り算定理、剰余の定理)から、
$$
k=qk_0+r\quad (0\leq r<k_0)
$$
という\(q,k_0\in\mathbb{Z}\)が一意的に存在します。
今、\(k\)が\(k_0\)の倍数ではないので、\(r\neq0\)であるから、
$$
k=qk_0+r\quad (0< r<k_0)
$$
という\(q,k_0\in\mathbb{Z}\)が一意的に存在します。
すると、(2)および(3)から、
\begin{eqnarray}
r&=&k-qk_0\\
&=&ax+by+cz-q\left( ax_0+by_0+cz_0\right)\\
&=&ax+by+cz-aqx_0+bqy_0+cqz_0\\
&=&a\left( x-qx_0\right)+b\left( y-qy_0\right)+c\left( z-qz_0\right)
\end{eqnarray}
となるため、\(r\)も一次形式\(f(x,y,z)\)で表される数です。
しかし、今この\(r\)は\(0<r<k_0\)を満たすため、これは\(k_0\)の最小性に矛盾します(\(k_0\)が最も小さい値だったのに、それよりも小さい値が出てきてしまう)。
したがって、\(k\)は\(k_0\)で割り切れます。

そもそも\(a=a\cdot1+b\cdot0+c\cdot0\)と書くことができるため、\(a\)は一次形式\(f(x,y,z)\)で表される数です。
したがって、先の議論から\(a\)は\(k_0\)で割り切れます。
同様にして\(b\)および\(c\)も\(k_0\)で割り切れます。
すなわち、\(a,b,c\)は共に\(k_0\)で割り切れるため、\(k_0\)は\(a,b,c\)の公約数です。
また、\(a,b,c\)は\(d=\gcd(a,b,c)\)の倍数です。
ここで、次の事実を使います。

定理2.の証明は【代数学の基礎シリーズ】初等整数論編 その2を御覧ください。

定理2.から、\(ax_0+by_0+cz_0\)も\(d=\gcd(a,b,c)\)の倍数です。
すなわち、\(ax_0+by_0+cz_0=k_0\)により、\(k_0\)は\(d=\gcd(a,b,c)\)の倍数です。
一方で、\(k_0\)は\(a,b,c\)の公約数でした。
ここで、次の事実を使います。

定理3.の証明は【代数学の基礎シリーズ】初等整数論編 その3を御覧ください。

したがって、\(k_0\)は\(a,b,c\)の公約数であり、定理3.から\(d=\gcd(a,b,c)\)の約数です。
一方で\(k_0\)は\(d\)の倍数でもあるため、\(k_0=d\)でなければなりません。
今、\(k_0\)は\(ax_0+by_0+cz_0=k_0\)と表されているため、
$$
ax_0+by_0+cz_0=d
$$
となるから、\(d\)も一次形式\(f(x,y,z)\)で表されます。
\(d\)が一次形式\(f(x,y,z)\)で表される数であれば、\(d\)の倍数も\(f(x,y,z)\)によって表される数です。

②\(\Longleftarrow\)の証明

逆に、一次形式\(f(x,y,z)\)によって表される数は再度定理2.から\(d\)の倍数となります。

以上のことから、\(f(x,y,z)=k\)を満たす\(x,y,z\in\mathbb{Z}\)が存在するための必要十分条件は\(k\)が\(\gcd(a,b,c)\)で割り切れることです。

定理1.の証明終わり

“整数解の存在”は分かったが、具体的にどう解くのか？

具体的な問題で確かめてみましょう。

何よりもまず、「そもそも整数解が存在するのか？」ということを確かめます。
定理1.により、\(1\)が\(\gcd(32,57,-68)\)の倍数、すなわち\(\gcd(32,57,-68)=1\)であることを確認します(確認してみよう！)。
今回は\(\gcd(35,57,-68)=1\)であるため、\(32x+57y-68z=1\)には整数解が存在します。

さて、絶対値が最小の係数\(32\)で各係数を割ります。
\begin{eqnarray}
57&=&32\times2-7\\
68&=&32\times2+4
\end{eqnarray}
ここで「んお？割り算定理の形とは違うな？」と思った方、大丈夫です。
先に述べておきますが、割り算定理の形に変形しても解けます。

\begin{eqnarray}
32x+57y-68z&=&32x+(32\times2-7)y-(32\times2+4)z\\
&=&32x+2\times32y+2\times32z-7y-4z\\
&=&32(x+2y-2z)-7y-4z
\end{eqnarray}
ここで、
$$
x^\prime=x+2y-2z\tag{5}
$$とします。
すると、\(y=z=0\)とすることで、\(x^\prime=x\in\mathbb{Z}\)となるため\(x^\prime\)は任意の整数を表します。
このとき、
$$
32x^\prime-7y-4z=1\tag{4\(\ast\)}
$$
となります。

同様にして、
\begin{eqnarray}
32&=&4\times8\\
7&=&4\times2-1
\end{eqnarray}
により、
$$
z^\prime=8x^\prime-2y-z\tag{6}
$$
とおくことで、\((4\ast)\)から
$$
y+4z^\prime=1\tag{\(4\ast\ast\)}
$$
となります。
\((4\ast\ast)\)の一般解として、

を得ます。
これを(6)に代入して
$$
z=8x^\prime+7z^\prime-2
$$
です。
最後に(5)に代入して
$$
x=17x^\prime+22z^\prime-6
$$
となります。
したがって、
$$
\begin{cases}
x=17x^\prime+22z^\prime-6\\
y=1-4z^\prime\\
z=8x^\prime+7z^\prime-2
\end{cases}
$$
が一般解です。

ちなみに、最初に
\begin{eqnarray}
57&=&32\times1+25\\
68&=&32\times2+4
\end{eqnarray}
と変形した場合は、
$$
\begin{cases}
x=17s-46t+11\\
y=1-4t\\
z=8s-25t+6
\end{cases}
$$
となります。

皆様のコメントを下さい！

筆者が修士のとき、とある原理を理解するのに約一ヶ月半かかりました。
そのとき「考える→分からない→考える→やっぱり分からない→でも考える→されど分からない→ふてくされる→一旦考えるのを止める→危機感にかられて考える→分からない→投げ出す→ふとしたときに考えてみる→閃く→分かる→天才だと誤認する」という感じでした。
皆様はどんな感じですか？
ぜひコメントで教えて下さい！

結

今回は、一次不定方程式の整数解の存在について解説しました。
一次不定方程式は”不定”と言っているだけあって、解は一意的にに定まりません。
しかし、どういう整数が解たりえるのかを調べることができます。
そのためには、結局の所\(ax+by+cz=k\)の\(k\)と\(\gcd(a,b,c)\)に注目すればOKということなのです。

次回は素数を導入します。

乞うご期待！
質問、コメントなどお待ちしております！
どんな些細なことでも構いませんし、「定理〇〇の△△が分からない！」などいただければお答えします！
お問い合わせの内容にもよりますが、ご質問はおおよそ１週間以内にお答えします。
(難しかったらもう少しかかるかもしれませんが…)

初等整数論について、以下の書籍をオススメします！