二次剩余理论

二次剩余理论定义:设$m$是正整数若同余式$$x^2\equiva(mod\p),\(a,p)=1$$有解,则$a$叫做模$p$的二次剩余(或平方剩余);否则,$a$叫做模$p$的二次非剩余。欧拉判别条件:设方程$$x^2\equiva(mod\p),\\(a,p)=1,p为奇素数$$(i)$a$是模$p$的二次剩余的…

大家好,欢迎来到IT知识分享网。二次剩余理论

定义:设 $m$ 是正整数 若同余式

$$x^2 \equiv a(mod \ p),\  (a, p)=1$$

有解,则 $a$ 叫做模 $p$ 的二次剩余(或平方剩余);否则,$a$ 叫做模 $p$ 的二次非剩余。

欧拉判别条件

设方程

$$x^2 \equiv a (mod \ p), \ \ (a,p)=1,p为奇素数$$

(i) $a$ 是模 $p$ 的二次剩余的充分必要条件是

$$a^{\frac{p-1}{2}} \equiv 1(mod \ p)$$

(ii) $a$ 是模 $p$ 的二次非剩余的充分必要条件是

$$a^{\frac{p-1}{2}} \equiv -1(mod \ p)$$

并且当 $a$ 模 $p$ 的二次剩余时,同余式有两个解。

定理1:$x^2 \equiv a(mod \ p)$ 中有 $\frac{p-1}{2}$ 个 $a$ 能使得方程有解

也就说有 $\frac{p-1}{2}$ 的二次剩余。

例如,1,2,4是模7的二次剩余,-1,3,5是模4的二次非剩余。

 勒让德(Lagendre)符号

设 $p$ 是素数,定义如下:

$$\left({n\over p}\right)=\begin{cases}1, \ \ \ \ p不是n的倍数,n是p的二次剩余\\-1, \ \ p不是n的倍数,n是p的二次非剩余(不是二次剩余就是非剩余)\\0, \ \ \ \ p是n的倍数
                                         \end{cases}$$

有定理1知,$p-1$ 中有一半为1,一半为-1.

根据欧拉判别法则,设 $p$ 是奇素数,对任意整数 $a$,

$$(\frac{a}{p}) \equiv a^{\frac{p-1}{2}} (mod \ p)$$

二次互反律:若 $p, q$ 是互素奇素数,则

$$(\frac{q}{p}) = (-1)^{\frac{p-1}{2}\cdot \frac{q-1}{2}}(\frac{p}{q})$$

 

 

参考链接:https://blog.csdn.net/doyouseeman/article/details/52033204

转载于:https://www.cnblogs.com/lfri/p/11511979.html

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/22268.html

(0)

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

关注微信