本記事は数学の徹底解説シリーズに含まれます。
初学者の分かりやすさを優先するため，多少正確でない表現が混在することがあります。もし致命的な間違いがあればご指摘いただけると助かります。
目次
一次合同式の解全体
自然数$n$と整数$a,b$に対して，一次合同式
\begin{align}
ax \equiv b\pmod{n}\label{主題1}
\end{align}
ax \equiv b\pmod{n}\label{主題1}
\end{align}
を考える。$b$が$d{=}\gcd(a,b)$の倍数のとき解の一つを$x_{1}$とすると，自然数$k$および$n^{\prime}{=}n/d$を用いて解の全体は
\begin{align}
x = x_{1}+n^{\prime}k\label{主題2}
\end{align}
x = x_{1}+n^{\prime}k\label{主題2}
\end{align}
と表される。このとき，$n$を法として解の個数は$d$となる。
証明
式($\ref{主題1}$)を変形すると，整数$y$を用いて
\begin{align}
ax + ny &= b\label{一次不定方程式}
\end{align}
ax + ny &= b\label{一次不定方程式}
\end{align}
が得られます。一次不定方程式の解全体より，式($\ref{主題2}$)が示されました。また，自然数$k^{\prime}$を用いて式($\ref{主題2}$)とは別の解を考えると，
\begin{align}
x_{1}+n^{\prime}k &\equiv x_{1}+n^{\prime}k^{\prime}\pmod{n}\\[0.7em]
n^{\prime}k &\equiv n^{\prime}k^{\prime}\pmod{n}
\end{align}
x_{1}+n^{\prime}k &\equiv x_{1}+n^{\prime}k^{\prime}\pmod{n}\\[0.7em]
n^{\prime}k &\equiv n^{\prime}k^{\prime}\pmod{n}
\end{align}
となりますが，$n^{\prime}$の定義より$n$と$n^{\prime}$は互いに素であるから両辺に$n^{\prime}$の乗法逆元を掛けることができ，
\begin{align}
k \equiv k^{\prime}\pmod{n}
\end{align}
k \equiv k^{\prime}\pmod{n}
\end{align}
が得られます。つまり，$n$を法とした$k$の値が等しければ式($\ref{主題1}$)の解は等価になるということですので，式($\ref{主題1}$)の解は$n$を法として解の個数は$d$となります。
コメント