黄博士网: 在线数学手册软件,电化学虚拟实验室,虚拟电化学工作站,电化学软件 关于 | 科学 | 数学 | 手册 | 软件 | 计算器 | 电化学 | 虚拟实验室 | 帮助 | 论坛 | 联系 | English

二次剩余

二次剩余与二次非剩余

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. \)

对模m的次数

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) \] 两两互不同余.

任一整数np不能整除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的原根

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为正整数).




参阅