二次剩余的证明改如何着手?看书没有看懂,特来求教 p是一个大于2的素数.求证1,2…p-1其中一半是p的二次剩余,另一半

二次剩余的证明改如何着手?
看书没有看懂,特来求教 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任意两个数不同余,还是我的想法有问题.
skybaby1020 1年前 已收到1个回答 举报

我要飘飘 幼苗

共回答了21个问题采纳率:95.2% 举报

假设 1x^2 = y^2 mod p(y+x)(y-x) = 0 mod p由于 p 是质数,所以要不 x + y = 0 mod p,要不 y - x = 0 mod p,由假设这两者都是不可能的.

1年前

9
可能相似的问题
Copyright © 2024 YULUCN.COM - 雨露学习互助 - 16 q. 0.024 s. - webmaster@yulucn.com