二次同余式是关于未知数的二次多项式的同余方程。即：是一个二次同余方程。此外，称为最简二次同余式，或称最简二次同余方程。一般的，通过配方，可以把一个一般的二次同余方程转化为一个最简二次同余式接下来只需要讨论最简二次同余式。
2二次剩余2.1 前置概念、定理即证明：若无特殊说明，下面的模运算都是在模p的意义下
1.有正整数n，奇质数p，且(p mid n)，若存在一个正整数x，使得(x^2equiv n(mod p))则称n为p的二次剩余。
2.勒让德符号 (egin{pmatrix}dfrac{n}{p}end{pmatrix})，若n为p的二次剩余，则该值为1，若不是则该值为-1，若(pmid n)，则该值为0
定理1：(egin{pmatrix}dfrac{n}{p}end{pmatrix}equiv n^{frac{p-1}{2}})
证明：1.若p能整除n，那右边明显模p与0同余，故成立。2.若n是p的二次剩余，则根据费马小定理((n^{p-1}equiv1(mod p))其中，p为质数)，有(n^{frac{p-1}{2}} = {sqrt{n}^{p-1}}equiv 1)，故成立3.若n不是p的二次剩余，则根据扩展欧几里得算法，对于(iin[1,p-1])都有唯一的(jin[1,p-1],i eq j且ijequiv n)这样的数一共有(frac{p-1}{2})个，因此(frac{p-1}{2}equiv (p-1)!)根据威尔逊定理)(：当且仅当p为素数时有：(( p -1 )! equiv -1 ( mod p )))，就有(frac{p-1}{2}equiv -1)
证毕
威尔逊定理证明：
我们知道(1 imes1equiv 1(mod p))(,( − 1 ) imes ( − 1 )equiv (mod p))，且仅有这两组的逆元与本身相等。如果(x^2equiv 1(mod p))那么通过移项再因式分解可以得到(x=-1)或(x=1)，除了1，-1这两个数之外，2至p-2中的每一个数都一定有一个对应的逆元（注明：(-1equiv p-1(mod p))）且一定与自己不相等，且每一个数与他的逆元一 一对应。
如果p是2，那威尔逊定理显然成立，如果(p>2) ，那么p一定是一个奇数，从2到p-2一共有偶数个数，且他们两两相乘mod p都是1，在乘上1（mod p为1）和p-1（mod p为-1）两个数，就有((p-1)!equiv -1(mod p)) 需要注意的是，一个数有逆元的充分必要条件是这个数与p互素，上述证明的前提是1到p-1都有逆元，即1到p-1都与p互素，自然，p是一个质数。
上面的证明并不严谨，但能看出，只有质数才能满足威尔逊定理，满足威尔逊定理的也只有是质数，所以，威尔逊定理是质数的充要条件。
证毕
定理1推论：若方程最简二次同余式有解的充要条件是(n^{frac{p-1}{2}}equiv 1(mod p))
定理2.([1,p-1])中有(frac{p-1}{2})个二次剩余。
证明：设(x,yin [1,p-1],x eq y,x^2equiv y^2)，则((x-y)(x+y)equiv 0) 由于有(0=1;}return (res%p+p)%p;}inline ll lrd(ll x){return ksm(x,(p-1)>>1);}struct rode{ll x,y;inline void intt(ll x_,ll y_){x=x_;y=y_;}};inline rode operator * (const rode &a,const rode &b){rode c;c.intt(((a.x*b.x)%p+a.y*b.y%p*w%p)%p,(a.x*b.y%p+a.y*b.x%p)%p);return c;}inline rode operator ^ (rode a,ll b){rode c;c.intt(1,0);while(b){if(b&1) c=c*a;a=a*a;b>>=1;}return c;}inline void solve(ll x){int if_=lrd(x);if(if_==p-1) printf("Hola! ");else if(if_==0) printf("0 ");else{ll q=rand()%p;w=(((q*q)%p-n)%p+p)%p;while(lrd(w)>1);ll ans1=a.x,ans2=p-ans1;if(ans1>ans2) ans1^=ans2,ans2^=ans1,ans1^=ans2;printf("%lld %lld ",ans1,ans2);}}int main(){srand(time(0));scanf("%d",&t);while(t--){scanf("%lld%lld",&n,&p);solve(n);}return 0;}
还记得“每两个不同的数对，它们之间相互不同余”吗？这也说明，对于一个二次剩余(y^2(mod p))来说，它有且只有两个解，(x)和(p-x)。
参考资料1.https://blog.csdn.net/dmt38421/article/details/102018271?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-2.control&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-2.control威尔逊定理证明
2百度百科二次同余式
3.https://www.luogu.com.cn/blog/ILikeDuck/gao-si-zheng-shuo-yu-er-ci-sheng-yu洛谷日报