二次剩余的证明改如何着手?看书没有看懂,特来求教p是一个大于2的素数.求证1,2…p-1其中一半是p的二次剩余,另一半是非二次剩余.证明是这样的1,2,…p-1是p的所有余数,设a表示1.2…p-1中任意

Question

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

Answer 1

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