自然数 \(a，\)\(b，\)\(c\) に対して、\(x，\)\(y\) に関する不定方程式 \(ax+by=c\) を考える。このとき、
\(ax+by=c\) が整数解をもつ
\(\Leftrightarrow\ c\) は \(a\) と \(b\) の最大公約数の倍数
※特に、\(c=1\) のとき、
\(ax+by=1\) が整数解をもつ
\(\Leftrightarrow\ 1\) は \(a\) と \(b\) の最大公約数の倍数
\(\Leftrightarrow\ a\) と \(b\) は互いに素
今回は、1次不定方程式の整数解の存在条件について見ていきます。
こちらの1次不定方程式は、素数や、ユークリッドの互除法など、様々な問題と絡めて出題できるため、入試問題としても出題しやすい分野になります。
証明は、少々長くなってしまいますが、ゆっくり丁寧に考えれば、それほど難しいことは言っていませんので、ぜひ、証明問題の練習と思って、お付き合いいただけると幸いです。
それでは始めていきましょう！
解説
具体例
まずは、こちらの命題について、具体例を使って、その意味を確認してみましょう。
自然数 \(a，\)\(b，\)\(c\) に対して、\(x，\)\(y\) に関する不定方程式 \(ax+by=c\) を考える。このとき、
\(ax+by=c\) が整数解をもつ
\(\Leftrightarrow\ c\) は \(a\) と \(b\) の最大公約数の倍数
\(4x+2y=3\)
こちらの方程式では、\(a=4，\)\(b=2\) となるため、その最大公約数は \(2\) です。
一方で、\(c=3\) のため、「\(c\) は \(a\) と \(b\) の最大公約数 \(2\) の倍数」ではありません。
したがって、こちらの1次不定方程式は、整数解をもちません。
※別の見方をしてみると、
- 左辺の係数は、\(4，\)\(2\) なので、必ず、偶数
- 右辺は、\(3\) なので、奇数
となり、偶奇が一致しないことからも、整数解が存在しないことがわかります。
\(2x+7y=3\)
こちらの方程式では、\(a=2，\)\(b=7\) となるため、その最大公約数は \(1\) です。（＝互いに素）
一方で、\(c=3\) のため、「\(c\) は \(a\) と \(b\) の最大公約数 \(1\) の倍数」です。（\(1\times 3=3=c\)）
したがって、こちらの1次不定方程式は、整数解をもちます。
※実際に、\((x，\)\(y)=(-2，\)\(1)\) とすると、\(2\cdot(-2)+7\cdot 1=3\) となり、解を見つけることができます。
※1次不定方程式の整数解は、存在する場合、一般に、無数に存在します。
（この1次不定方程式の解も、\((x，\)\(y)=(7k-2，\)\(-2k+1)\ (k\) は整数\()\) となります。）
具体的な求め方は、こちらのページで解説していますので、併せてご覧ください。
証明
それでは、先ほどの命題を証明してみましょう。
自然数 \(a，\)\(b，\)\(c\) に対して、\(x，\)\(y\) に関する不定方程式 \(ax+by=c\) を考える。このとき、
\(ax+by=c\) が整数解をもつ
\(\Leftrightarrow\ c\) は \(a\) と \(b\) の最大公約数の倍数
※特に、\(c=1\) のとき、
\(ax+by=1\) が整数解をもつ
\(\Leftrightarrow\ 1\) は \(a\) と \(b\) の最大公約数の倍数
\(\Leftrightarrow\ a\) と \(b\) は互いに素
＜証明＞
\(\Rightarrow\)\(，\)\(\Leftarrow\) に分けて証明します。
（\(\Rightarrow\)）
\(ax+by=c\) の整数解（の1つ）を \((x，\)\(y)=(m，\)\(n)\) とすると、
\[am+bn=c・・・①\]
となります。
ここで、\(a，\)\(b\) の最大公約数を \(g\) とすると、整数 \(p，\)\(q\) を用いて、
- \(a=p\cdot g\)
- \(b=q\cdot g\)
と表せます。これを①に代入して、
\[\begin{alignat*}{3}
&am+bn=c \\
\Leftrightarrow\ &(p\cdot g)\cdot m+(q\cdot g)\cdot n=c \\
\Leftrightarrow\ &(p\cdot m+q\cdot n)\cdot g=c
\end{alignat*}\]
ここで、\(m，\)\(n，\)\(p，\)\(q\) はいずれも整数なので、\(p\cdot m+q\cdot n\) も整数であり、\(c\) は \(a\) と \(b\) の最大公約数 \(g\) の倍数であることが示されました。
（\(\Leftarrow\)）
先に、1つ補題を証明します。
＜補題＞
互いに素な自然数 \(s，\)\(t\) に対して、
\[\begin{alignat*}{3}
&s，2s，3s，\dots， \\
&\quad\dots，k\cdot s，\dots，l\cdot s，\dots， \\
&\quad\quad\dots，(t-2)s，(t-1)s
\end{alignat*}\]
を \(t\) で割った余り \({r}_{1}，\dots，{r}_{t-1}\) はすべて異なる（\({r}_{k}\ne{r}_{l}\)）。
そして、\({r}_{k}=1\) となる \(k\ (1\leqq k\leqq t-1)\) が存在する。
＜証明＞
割り算の定義から、一般に、余りは、\(0\) 以上・割る数未満の数となります。（※）
一方で、今、\(s，\)\(t\) は、互いに素な自然数なので、\(1\leqq k\leqq t-1\) である \(k\) に対して、\(ks\) は \(t\) では割り切れません。
したがって、\(ks\) を \(t\) で割った余り \({r}_{k}\) は \(1\) 以上の数であり、（※）と合わせて、
- \(ks=t\cdot {q}_{k}+{r}_{k}\)・・・①
- \(1\leqq {r}_{k} \leqq t-1\)・・・②
となります。（\({q}_{k}\) は割り算の商です）
ここで、\(l\ne k，\)\(1\leqq l\leqq t-1\) である \(l\) を考えると、①式で、\(k\) を \(l\) に置き換えて、
\[ls=t\cdot {q}_{l}+{r}_{l}・・・③\]
となり、③-①より、
\[(l-k)s=t\cdot({q}_{l}-{q}_{k})+({r}_{l}-{r}_{k})\]
という関係式が得られます。
ここで、\({r}_{l}-{r}_{k}=0\) と仮定すると、
\[(l-k)s=t\cdot({q}_{l}-{q}_{k})\]
今、\(s，\)\(t\) は、互いに素な自然数なので、
- \(l-k=t\)・・・④
- \(s={q}_{l}-{q}_{k}\)・・・⑤
となりますが、④から、\(l=t+k\) となってしまい、これは、\(1\leqq l\leqq t-1\) に矛盾します。
したがって、\(k\ne l\) のとき、
\[{r}_{k}-{r}_{l}\ne 0\ \Leftrightarrow\ {r}_{k}\ne{r}_{l}\]
とわかりました。
また、以上の検討より、次の3つがわかっています。
- \(k\) は、\(1\leqq k\leqq t-1\) の \((t-1)\) 個の値をとりえる（\(\because\) 前提）
- 余り \({r}_{k}\) は、\(1\leqq {r}_{k} \leqq t-1\) の \((t-1)\) 個の値をとりえる（\(\because\) ②）
- \(k\ne l\) のとき、\({r}_{k}\ne{r}_{l}\)（\(\because\) 直前の証明）
これら3つのことから、\({r}_{k}=1\) となる \(k\ (1\leqq k\leqq t-1)\) が存在することが示されました。
（証明終了）
改めて、上の補題を用いて、以下の証明を行います。
\(ax+by=c\) が整数解をもつ
\(\Leftarrow\ c\) は \(a\) と \(b\) の最大公約数の倍数
\(a，\)\(b\) の最大公約数を \(g\) とすると、互いに素である整数 \(p，\)\(q\) を用いて、
- \(a=p\cdot g\)
- \(b=q\cdot g\)
と表せます。
\(p，\)\(q\) は互いに素なので、先ほどの補題から、
\(mp\) を \(q\) で割った余りが \(1\) となるような \(m\ (1\leqq m\leqq q-1)\) が存在し、
\(mp=qn+1\)
と書けます。（\(n\) は割り算の商です）
したがって、
\[\begin{alignat*}{3}
&mp=qn+1 \\
&\Leftrightarrow\ pm-qn=1 \\
&\Leftrightarrow\ (p\cdot g)\cdot m-(q\cdot g)\cdot n=g \\
&\Leftrightarrow\ am-bn=g
\end{alignat*}\]
ここで、与えられた条件「\(c\) は \(a\) と \(b\) の最大公約数の倍数」より、\(c=kg\) とすると、
\[\begin{alignat*}{3}
&am-bn=g \\
&\Leftrightarrow\ k\cdot am-k\cdot bn=kg \\
&\Leftrightarrow\ a\cdot(km)+b\cdot(-kn)=c
\end{alignat*}\]
\(k，\)\(m，\)\(n\) はいずれも整数なので、\(km，\)\(-kn\) も整数です。
したがって、\(ax+by=c\) は、整数解 \((x，\)\(y)=\)\((km，\)\(-kn)\) をもつことが示されました。
（証明終了）
※整数（整式ではない）の割り算の定義については、こちらのページで少し言及しています。
おわりに
お疲れさまでした！今回は、1次不定方程式の整数解の存在条件について見てきました。
ひょっとすると気づかれた方もいらっしゃるかもしれませんが、途中で証明したこちらの補題は、あの「フェルマーの小定理」の証明でも現れる、非常に有名なものになります。
＜補題＞
互いに素な自然数 \(s，\)\(t\) に対して、
\[\begin{alignat*}{3}
&s，2s，3s，\dots， \\
&\quad\dots，k\cdot s，\dots，l\cdot s，\dots， \\
&\quad\quad\dots，(t-2)s，(t-1)s
\end{alignat*}\]
を \(t\) で割った余り \({r}_{1}，\dots，{r}_{t-1}\) はすべて異なる（\({r}_{k}\ne{r}_{l}\)）。
そして、\({r}_{k}=1\) となる \(k\ (1\leqq k\leqq t-1)\) が存在する。
「フェルマーの小定理」については、こちらのページで解説していますので、整数問題の更なる得点力UPに向けて、ぜひこちらも参照してみてください！
コメント