平方剩余(二次剩余)

作者:Chenglin_Yu

时间:2019年4月8日

来源:https://chenglinyu.blog.csdn.net/article/details/89081707

1.1 举个例子

1.定义

设p是奇素数(大于2的),如果二次同余式 x^2 = a(mod\ p), (a, p) = 1  有解,则称a为模p的平方剩余(一个数的平方模p的余数),否则a称模p的平方非剩余。平方剩余和平方非剩余又称为二次剩余和二次非剩余。

请求出11的所有二次剩余。

在解决这个问题之前,首先我们要清楚11的一个剩余系为0,1,2,3,…,10。所以11的二次剩余只可能来源于这些数。为了决定哪些整数是11的二次剩余,我们计算整数1,2,3,…,10的平方(有同学可能就要问了,为什么只计算这10个数的平方呢?因为《初等数论及其应用》中的引理11.1提到了同余方程或者无解或者有两个模p不同于的解,所以我们只需要找这10个数就可以了,那有可能同学又要问了,怎么把0给漏掉了,因为(a,p) = 1,可以打消疑虑了吧。),得到

1^2 \equiv 10^2 \equiv 1 (mod \ 11)
2^2 \equiv 9^2 \equiv 4 (mod \ 11)
3^2 \equiv 8^2 \equiv 9(mod\ 11)
4^2 \equiv 7^2 \equiv 5(mod \ 11)
5^2 \equiv 6^2 \equiv 3 (mod \ 11)

因此,11的二次剩余是1,3,4,5,9,二次非剩余是2,6,7,8,10.

2.平方剩余和平方非剩余的个数

设p是奇素数,在模p的简化剩余系中,有\frac {p-1}{2}个平方剩余,\frac {p-1}{2}个平方非剩余。

这个定理很有用:以后我们求模p的平方剩余时,就可以只计算下列数了

1^2, 2^2,…,(\frac {p-1} {2})^2 (mod\ p)

3.欧拉判别法

欧拉判别法可以判断一个数是不是模p的平方剩余

设p是奇素数,(a,p) = 1。a是模p平方剩余的充分必要条件是

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

a是模p的平方非剩余的充分必要条件是
a^{\frac {p-1}{2}} \equiv -1 (mod \ p)

3.1 例1

判断3是不是模17的平方剩余?

根据欧拉判别法,

a = 3, p = 17, 所以

\frac {p-1}{2} = 8

我们需要得到

3^8 \equiv 1(mod \ 17)

或者

3^8 \equiv -1(mod \ 17)

我们的计算方式是”从底层起”

因为

3^2 \equiv 9 (mod\ 17 )

所以

3^4 \equiv 81\equiv -4 (mod\ 17)

方程同时平方得

3^8 \equiv 16 (mod \ 17)\equiv -1 (mod \ 17)

所以3是模17的平方非剩余

3.2 例2

7是不是模29的平方剩余

\frac {p-1}{2} = 14

 7^{14} 是我们的目标。老办法,从底层起

7^2 = 49 \equiv -9 (mod\ 29)

7^4 \equiv (-9)^2 \equiv 81\equiv -6 (mod 29)

7^8 \equiv (-6)^2 \equiv 36 \equiv 7 (mod \ 29)

所以

7^{14} = 7^8 \times 7^4\times 7^2 \equiv 1 (mod \ 29)

所以7是模29的平方剩余。

相关文章:

发表评论

您的电子邮箱地址不会被公开。