c++ 5种情况求x^2≡a(mod p)

来源：深圳童程童美信息学培训学校时间：2023/4/16 12:00:01

　　5种情况求x^2≡a(mod p)

　　(1) p是奇数质数 k是正整数 求x^2≡p^2(mod p^k)有多少解?

　　(2) a是一个整数的完全平方 p是质数 求x^2≡a(mod p)有多少解?

　　(3) 证明如果x^2≡a(mod p)只有两个解 那么 x^2≡a(mod p^k)只有两个解(k是整数)

　　(4) 找出10个奇数质数p满足p|x^2+5 (x是整数) 另：能对这些质数做一个推断吗

　　(5)找出10个奇数质数p满足p|x^2+1 (x是整数) 另：能对这些质数做推断吗

　　(1) p是奇数质数 k是正整数 求x^2≡p^2(mod p^k)有多少解?

　　k=1,有一个解x≡0(mod p)

　　k=2,有一个解x≡0(mod p)

　　k>2,显然正负p是两个不同的解,如果A是另一个不同的解,则(A^2,p^k)=(p^2,p^k)=p^2,

　　所以A^2=z^2*p^2,(z,p)=1,A=z*p

　　则A^2-p^2=(z^2-1)p^2=mp^k,(m,p)=1,(z-1)(z+1)=m*p^(k-2),z-1与z+1只有一个可能是p的倍数

　　所以z=n*p^(k-2)+/-1 m=n(np^(k-2)+/-2),显然(n,p)=1

　　取n=0,1,2,3,...p-1,p+1,p+2,.2p-1,2p+1,2p+2,...3p-1.(p^2-1)*p -1

　　共计2+(p-1)*2*(p^2-1)个解

　　(2) a是一个整数的完全平方 p是质数 求x^2≡a(mod p)有多少解?

　　(3) 证明如果x^2≡a(mod p)只有两个解 那么 x^2≡a(mod p^k)只有两个解(k是整数)

　　(4) 找出10个奇数质数p满足p|x^2+5 (x是整数) 另：能对这些质数做一个推断吗

　　(5)找出10个奇数质数p满足p|x^2+1 (x是整数) 另：能对这些质数做推断吗

　　————————————————

　　版权声明：本文为CSDN博主「dllglvzhenfeng」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。

　　原文链接：https://blog.csdn.net/dllglvzhenfeng/article/details/123047938

尊重原创文章，转载请注明出处与链接：http://www.peixun360.com/2476/news/613486/违者必究！ 以上就是深圳童程童美信息学培训学校 小编为您整理 c++ 5种情况求x^2≡a(mod p)的全部内容。