本記事は数学の徹底解説シリーズに含まれます。
初学者の分かりやすさを優先するため，多少正確でない表現が混在することがあります。もし致命的な間違いがあればご指摘いただけると助かります。
目次
一次合同式の解の存在
自然数$n$と整数$a,b$に対して，一次合同式
\begin{align}
ax \equiv b\pmod{n}\label{主題}
\end{align}
ax \equiv b\pmod{n}\label{主題}
\end{align}
が整数解をもつための必要十分条件は，$b$が$d{=}\gcd(a,n)$の倍数となることである。ただし，$a\neq 0$とする。
証明
式($\ref{主題}$)を変形すると，整数$y$を用いて
\begin{align}
ax + ny &= b\label{一次不定方程式}
\end{align}
ax + ny &= b\label{一次不定方程式}
\end{align}
が得られます。一次不定方程式の解の存在より，式($\ref{一次不定方程式}$)が解をもつための必要十分条件は$b$が$d$の倍数となることであるため，題意は示されました。
コメント