+ 
+ 
+ 
= 
+
+
+
=
设m为大于1的整数，\( \left( {n,m} \right) = 1 \)，若\[ x^2 \equiv n\left( {\bmod m} \right) \]可解，则称n为对模m的二次剩余，或二次剩余\( \left( {\bmod m} \right) \) 否则，称n为对模m的二次非剩余．
两个二次剩余之积仍为二次剩余．
两个二次非剩余之积为二次剩余．
一个二次剩余与一个二次非剩余之积为一个二次非剩余．
设p为奇素数，则在模p的缩剩余系中，有\( \frac{{p - 1}}{2} \)个二次剩余． \[ 1^2 , \cdots ,\left( {\frac{{p - 1}}{2}} \right)^2 \] 有\( \frac{{p - 1}}{2} \)个二次非剩余\( \left( {\bmod p} \right) \) ．
设p为奇素数，p不能整除n，又设 \[ \left( {\frac{n}{p}} \right) = \left\{ \begin{array}{l} \begin{array}{*{20}c} {1,} & {\left( {当n为二次剩余\bmod p} \right)} \\ \end{array} \\ \begin{array}{*{20}c} { - 1,} & {\left( {当n为二次非剩余\bmod p} \right)} \\ \end{array} \\ \end{array} \right. \] 则\( \left( {\frac{n}{p}} \right) \)称为勒让德符号．
勒让德符号具有下列性质：
1°若\( n \equiv n'\left( {\bmod p} \right) \)，p不能整除n，则\[ \left( {\frac{n}{p}} \right) = \left( {\frac{{n'}}{p}} \right) \] 2°欧拉判别条件：设p为奇素数，则 \[ n^{\frac{{p - 1}}{2}} \equiv \left( {\frac{n}{p}} \right)\left( {\bmod p} \right) \] 3°若p为奇素数，p不能整除mn，则 \[ \left( {\frac{m}{p}} \right)\left( {\frac{n}{p}} \right) = \left( {\frac{{mn}}{p}} \right) \] 4°若p为奇素数，则 \[ \left( {\frac{{ - 1}}{p}} \right) = \left( { - 1} \right)^{\frac{{p - 1}}{8}} \] 5°若p为奇素数，则 \[ \left( {\frac{2}{p}} \right) = \left( { - 1} \right)^{\frac{{p^2 - 1}}{2}} \] 6°高斯互逆定律：设p,q为两个不同的奇素数，则 \[ \left( {\frac{p}{q}} \right)\left( {\frac{q}{p}} \right) = \left( { - 1} \right)^{\frac{{p - 1}}{2}\frac{{q - 1}}{2}} \]
设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) \) ．
设p为素数，次数为p－1的数称为模p的原根．设g为模p的一原根，则\[ 1,g,g^2 , \cdots ,g^{p - 2} \left( {\bmod p} \right) \] 两两互不同余．
任一整数n（p不能整除n），必有一数a使得 \[ n \equiv g^a \left( {\bmod p} \right),0 \le a \le p - 1 \] 此a称为n的指数\( \left( {\bmod p} \right) \) ．记作\[ a = {\mathop{\rm ind}\nolimits} _g n \] 在不易混淆时，简记\( {\mathop{\rm ind}\nolimits} n \)．
指数具有下列性质：
1°若b为满足\[ n \equiv g^b \left( {\bmod p} \right) \] 的任一数，则 \[ b \equiv {\mathop{\rm ind}\nolimits} n\left( {\bmod p - 1} \right) \]
2°\( {\mathop{\rm ind}\nolimits} ab \equiv {\mathop{\rm ind}\nolimits} a + {\mathop{\rm ind}\nolimits} b\left( {\bmod p - 1} \right) \)，p不能整除ab 3°\( {\mathop{\rm ind}\nolimits} a^l \equiv l{\mathop{\rm ind}\nolimits} a\left( {\bmod p - 1} \right) \)，p不能整除a． 4°底数互换公式，设\( g_1 ,g_2 \)为模p的两个不等的原根，且\( g_1 \equiv g^b \left( {\bmod p} \right) \)，则\[ {\mathop{\rm ind}\nolimits} _g n \equiv {\mathop{\rm ind}\nolimits} _g g_1 \cdot {\mathop{\rm ind}\nolimits} _{g_1 } n\left( {\bmod p - 1} \right) \]
设m为一自然数，若有一数g存在，使得 \[ 1,g,g^2 , \cdots ,g^{\pi \left( m \right) - 1} \left( {\bmod m} \right) \] 两两互不同余，则此g称为对模m的原根，模m的原根存在的充分必要条件是：
\( m = 2,4,p^l ,2p^l \) （p为奇素数，l为正整数）．