同余方程 \[ a_1 x_1 + \cdots + a_n x_n \equiv b\left( {\bmod \ m} \right) \] 有解的充分必要条件是: \[ \left( {a_1 , \cdots ,a_n ,m} \right)|b \] 当满足此条件时,其解数(对模m的不同余者)为 \[ m^{n - 1} \left( {a_1 , \cdots ,m} \right) \]
一元一次同余方程\[ ax + b \equiv 0\left( {\bmod \ m} \right) \] 有解的充分必要条件是:\( \left( {a,m} \right)|b \),若有解则共有\( \left( {a,m} \right) \)个互不同余的解\( \left( {\bmod \ m} \right) \)解法如下:
设\( \left( {a,m} \right) = d \),\( d|b \),则原方程化为 \[ \frac{a}{d}x + \frac{b}{d} \equiv 0\left( {\bmod \frac{m}{d}} \right),\left( {\frac{a}{d},\frac{m}{d}} \right) = 1 \] 记作 \[ a'x' + b' \equiv \left( {\bmod \ m'} \right),\left( {a',m'} \right) = 1 \] 首先由辗转相除法\( x_0 ,y_0 \),使得\[ a'x_0 + m'y_0 = 1 \] 则 \[ x' = - b'x_0 \] 是同余方程的解,最后得到 \[ x = x' + m't,t = 0,1, \cdots ,d - 1 \] 为原方程的解\( \left( {\bmod \ m} \right) \) .即有d个解 \[ x',x' + \frac{m}{d},x' + \frac{{2m}}{d}, \cdots ,x' + \frac{{\left( {d - 1} \right)m}}{d} \] 对模m不同余.
设l>0,p不能整除n,若p为奇素数,则二次同余式\[ x^2 \equiv n\left( {\bmod \ p^l } \right) \] 的解数为\( 1 + \left( {\frac{n}{p}} \right) \)
当p=2时,l=1时有一解.
\(l= 2时\left\{ {\begin{array}{*{20}c} {有二解,当n\equiv 1\left( {\bmod \ 4} \right)} \\ {无解,当n\equiv 3\left( {\bmod \ 4} \right)} \\ \end{array}} \right. \) .
\(l> 2时\left\{ {\begin{array}{*{20}c} {有四解,当n \equiv 1\left( {\bmod \ 8} \right)} \\ {无解,当n\equiv 3,5,7\left( {\bmod \ 8} \right)} \\ \end{array}} \right. \)
设h为一整数,\( \left( {m,h} \right) = 1 \),满足\[ h^l \equiv 1\left( {\bmod \ m} \right) \] 的最小正整数l称为h对模m的次数,或h的次数\( \left( {\bmod \ m} \right) \) .
若\( h^n \equiv 1\left( {\bmod \ m} \right) \),则\( l|n \),这里l为h的次数\( \left( {\bmod \ m} \right) \) .