【初学者向け】一次合同式の解全体

2024年7月27日

本記事は数学の徹底解説シリーズに含まれます。

初学者の分かりやすさを優先するため，多少正確でない表現が混在することがあります。もし致命的な間違いがあればご指摘いただけると助かります。

一次合同式の解全体

自然数 $n$ と整数 $a, b$ に対して，一次合同式

\begin{array}{r} (1) & a x \equiv b (\mod n) \end{array}

を考える。 $b$ が $d = gcd (a, b)$ の倍数のとき解の一つを $x_{1}$ とすると，自然数 $k$ および $n^{'} = n / d$ を用いて解の全体は

\begin{array}{r} (2) & x = x_{1} + n^{'} k \end{array}

と表される。このとき， $n$ を法として解の個数は $d$ となる。

式( $1$ )を変形すると，整数 $y$ を用いて

\begin{aligned} (3) & a x + n y & = b \end{aligned}

が得られます。一次不定方程式の解全体より，式( $2$ )が示されました。また，自然数 $k^{'}$ を用いて式( $2$ )とは別の解を考えると，

\begin{aligned} (4) & x_{1} + n^{'} k & \equiv x_{1} + n^{'} k^{'} (\mod n) \\ (5) & n^{'} k & \equiv n^{'} k^{'} (\mod n) \end{aligned}

となりますが， $n^{'}$ の定義より $n$ と $n^{'}$ は互いに素であるから両辺に $n^{'}$ の乗法逆元を掛けることができ，

\begin{array}{r} (6) & k \equiv k^{'} (\mod n) \end{array}

が得られます。つまり， $n$ を法とした $k$ の値が等しければ式( $1$ )の解は等価になるということですので，式( $1$ )の解は $n$ を法として解の個数は $d$ となります。

シェアはこちらからお願いします！