二次剩余的证明改如何着手?

看书没有看懂,特来求教
p是一个大于2的素数。求证1,2…p-1其中一半是p的二次剩余,另一半是非二次剩余。
证明是这样的
1,2,…p-1是p的所有余数,设a表示1.2…p-1中任意一整数
构造一个序列1^2, 2^2, 3^2 …(p-1)^2,其余数必定是1,2…p-1其中之一。当整数大于p时,余数是这个数列的反复,因为(a+np)^2 ≡ a^2 mod p.
则有a^2 ≡ (p - a)^2 mod p
这是因为(p - a)^2=p^2-2ap+a^2 ≡ a^2 mod p
到这一步我都看明白,后面就不明白了
因此数列1^2,2^2…(p-1)^2是成对同余的。所以他们的余恰好是p所有余数的一半,可以得到1,2,…p-1有一半是二次剩余。
我不理解的是假如1^2,2^2…[(p-1)/2]^2之间如果有两个数同余,虽然1^2,2^2…(p-1)^2是成对同余的,余数不就一定是一半了。是这个证明没有1^2,2^2…[(p-1)/2]^2任意两个数不同余,还是我的想法有问题。

推荐  (0) | 1人关注关注
2个答案
3 0

假设 1 <= x < y <= (p-1)/2
x^2 = y^2 mod p
(y+x)(y-x) = 0 mod p

由于 p 是质数,所以要不 x + y = 0 mod p, 要不 y - x = 0 mod p,由假设这两者都是不可能的。

0 0

任何数除以P的余数是P-1个。例如:任何数除以7的余数是1到6共6个。

现在这个计算结果是成对同余,2个数计算后除以P才产生1个余数,所以余数数量是任何数直接除以P的一半,即(P-1)/2。例如:除以7后只有3个相同的余数,另3个就不是这种计算的余数了。

查看更多

添加回答

登录 后回答问题,你也可以用以下帐号直接登录

相关问答

关于我们 加入果壳 媒体报道 帮助中心 果壳活动 家长监控 免责声明 联系我们 移动版 移动应用

©果壳网    京ICP证100430号    京网文[2018] 6282-492号    新出发京零字第朝200003号     京公网安备11010502007133号

违法和不良信息举报邮箱:jubao@guokr.com    举报电话:18612934101    网上有害信息举报专区    儿童色情信息举报专区