1次不定方程式で知っておきたい3つの基本知識

整数不定方程式


1次不定方程式 ax+by=c を解く際に知っていると便利な基本知識を3つ紹介します。
関連:1次不定方程式の解き方4通り
以下、特に断らないかぎり文字は全て整数とします。

ax+by=cの解はax+by=1から求まる

\(ax+by=\color{red}{c}\) の特殊解は\(ax+by=\color{red}{1}\) の特殊解を \(c\) 倍すれば求まる

証明

\(ax+by=1\) の特殊解が
\(x=p,\,y=q\) であるとすると
\(ap+bq=1\)
両辺を\(\,c\,\)倍すると
\(a(cp)+b(cq)=c\)
よって
\(x=cp,\,y=cq\) は
\(\,ax+by=c\,\)の特殊解

例: \(7x+13y=5\) の特殊解
\(7x+13y=1\) の特殊解は
\(x=2,y=-1\)
よって \(7x+13y=5\) の特殊解は
\(\color{red}{x=10,y=-5}\)

\(ax+by=c\) の特殊解が見つけられない時は \(ax+by=1\) の特殊解を探して \(c\) 倍すればよいです。


互いに素のとき必ず整数解を持つ

\(a\) と \(b\) が互いに素のとき \(ax+by=c\) は必ず整数解を持つ

\(a\) と \(b\) が互いに素であれば「解なし」という答えはあり得ないです。
出題者側目線で考えても、 \(a\) と\(b\) が互いに素であることさえ確認すれば「整数解が存在しない」という出題ミスが起こらないのは有難いことかもしれないですね。

一方, \(a\) と \(b\) が互いに素でないときは, 整数解を持つとは限りません。
例えば、\(a,b\) がどちらも3の倍数なら
\(a=3a^{\prime},\,b=3b^{\prime}\) と書けます。このとき
\(ax+by=3(a^{\prime}x+b^{\prime}y)\) は3の倍数なので、
\(ax+by=5\) のように、右辺が3の倍数でないときは整数解を持ちません。


答えが模範解答と違ってもよい

自分の答えと模範解答が一見違うことがあります。
自分の見つけた特殊解が模範解答の特殊解と違うときによく起こります。

例:\(7x+13y=5\) の一般解

略解1
特殊解\(x=10,\,y=-5\) から一般解は
\(x=10+13k\)
\(y=-5-7k\)

略解2
特殊解\(x=-3,\,y=2\) から一般解は
\(x=-3+13k\)
\(y=2-7k\)

というように、見つけた特殊解によって見た目が違うことがあります。
略解1で \(k\) を \(k-1\) と置き換えれば
\(x=10+13(k-1)=-3+13k\)
\(y=-5-7(k-1)=2-7k\)
となり、略解2と同じ形にできます。

また\(k\) を \(-k\)と置き換えて
\(x=10+13(-k)=10-13k\)
\(y=-5-7(-k)=-5+7k\)
も正解です。

模範解答と自分の答えが違う場合は \(k\) を微調整して一致するか確認してください。