二次剩余是數(shù)論基本概念之一，它是初等數(shù)論中非常重要的結(jié)果。
什么是二次剩余呢？簡(jiǎn)單來說就是如果存在一個(gè)整數(shù)xxx，使得x2≡n(modp)x^2≡n(mod\ p)x2≡n(mod?p)，那么則稱nnn是模ppp的二次剩余。
有一種很巧妙的辦法，可以得出一個(gè)數(shù)是否是模ppp的二次剩余。這個(gè)辦法是勒讓德符號(hào)(np)(\frac{n}{p})(pn?)。

如果nnn是模ppp的二次剩余，那么(np)=1(\frac{n}{p})=1(pn?)=1；
如果nnn不是模ppp的二次剩余，那么(np)=?1(\frac{n}{p})=-1(pn?)=?1；
如果p∣np|np∣n，則(np)=0(\frac{n}{p})=0(pn?)=0

這里有一個(gè)結(jié)論：(np)=np?12(\frac{n}{p})=n^{\frac{p-1}{2}}(pn?)=n2p?1? （前提是ppp是奇質(zhì)數(shù)）

證明：（不看也無所謂）
①如果nnn是模ppp的二次剩余，那么n\sqrt nn?與ppp互質(zhì)，那么根據(jù)費(fèi)馬小定理(n)p?1≡1(modp)(\sqrt n)^{p-1}≡1(mod\ p)(n?)p?1≡1(mod?p)。
②如果nnn不是模ppp的二次剩余，那么因?yàn)閜pp是奇質(zhì)數(shù)，所以根據(jù)擴(kuò)歐可知對(duì)于i∈[1,p?1]i∈[1,p-1]i∈[1,p?1]，都有一個(gè)j∈[1,p?1]j∈[1,p-1]j∈[1,p?1]使其滿足ij≡n(modp)ij≡n(mod\ p)ij≡n(mod?p)。所以我們可以把1,2……p?11,2……p-11,2……p?1分成p?12\frac{p-1}{2}2p?1?對(duì)，每對(duì)的乘積在模ppp下都是nnn，那么(p?1)!≡np?12(modp)(p-1)!≡n^{\frac{p-1}{2}}(mod\ p)(p?1)!≡n2p?1?(mod?p)，根據(jù)威爾遜定理有(p?1)!≡?1(modp)(p-1)!≡-1(mod\ p)(p?1)!≡?1(mod?p)，所以np?12≡?1(modp)n^{\frac{p-1}{2}}≡-1(mod\ p)n2p?1?≡?1(mod?p)
③如果p∣np|np∣n，那么顯然np?12≡0(modp)n^{\frac{p-1}{2}}≡0(mod\ p)n2p?1?≡0(mod?p)

定理：對(duì)于方程x2≡n(modp)x^2≡n(mod\ p)x2≡n(mod?p)，有p?12\frac{p-1}{2}2p?1?個(gè)不同的nnn,使得該方程有解。

證明：若有兩個(gè)數(shù)uuu和vvv均滿足它們的平方在ppp時(shí)同余，那么必然有p∣(u+v)(u?v)p|(u+v)(u?v)p∣(u+v)(u?v)。由于ppp不可能整除u?vu?vu?v，那么可以得出ppp整除u+vu+vu+v。這個(gè)結(jié)論反過來也是成立的，因此共有p?12\frac{p-1}{2}2p?1?種不同的平方。且每一個(gè)ppp的二次剩余恰好有兩個(gè)解。

那么怎么求一個(gè)二次剩余呢？我們可以按照下面的方法:

在[0,p?1][0,p-1][0,p?1]隨機(jī)挑選一個(gè)數(shù)，稱其為aaa，定義w=a2?nw=a^2-nw=a2?n，若(wp)=?1(\frac{w}{p})=-1(pw?)=?1，那么(a+w)p+12(a+\sqrt w)^{\frac{p+1}{2}}(a+w?)2p+1?就是一組二次剩余。

證明：(a+w)p=∑i=0p(Cpiap?i)(Cpp?i(w)i)(a+\sqrt w)^{p}=\sum_{i=0}^{p}(C_{p}^{i}a^{p-i})(C_{p}^{p-i}(\sqrt w)^{i})(a+w?)p=∑i=0p?(Cpi?ap?i)(Cpp?i?(w?)i)，由于ppp是質(zhì)數(shù)，所以除了Cp0C^{0}_{p}Cp0?和CppC_{p}^{p}Cpp?為111外，所有的Cpi(i∈[1,p?1])C_{p}^{i}(i∈[1,p-1])Cpi?(i∈[1,p?1])模ppp等于000,所以(a+w)p≡ap+wp(modp)(a+\sqrt w)^{p}≡a^p+\sqrt w^p\ (mod\ p)(a+w?)p≡ap+w?p?(mod?p)。
由費(fèi)馬小定理可得ap≡a(modp)a^p≡a(mod\ p)ap≡a(mod?p),又因?yàn)?wp)=?1(\frac{w}{p})=-1(pw?)=?1即wp?12=?1w^{\frac{p-1}{2}}=-1w2p?1?=?1,所以wp=?w\sqrt w^{p}=-\sqrt ww?p=?w?
所以(a+w)p≡ap+wp(modp)≡a?w(modp)(a+\sqrt w)^{p}≡a^p+\sqrt w^p\ (mod\ p)≡a-\sqrt w(mod\ p)(a+w?)p≡ap+w?p?(mod?p)≡a?w?(mod?p)
所以(a+w)p+1≡(a+w)p(a+w)≡(a?w)(a+w)≡a2?w≡n(a+\sqrt w)^{p+1}≡(a+\sqrt w)^{p}(a+\sqrt w)≡(a-\sqrt w)(a+\sqrt w)≡a^2-w≡n(a+w?)p+1≡(a+w?)p(a+w?)≡(a?w?)(a+w?)≡a2?w≡n

有了最后一個(gè)定理，我們就可以通過隨機(jī)選擇a的值來找到一個(gè)滿足條件的解。可以證明找到正解所需的次數(shù)的期望只有2（然而我并不是特別會(huì)證）。所以隨機(jī)取a的值可以很快地找到一個(gè)解。

部分代碼：

struct field{int x,y;field(int a=0,int b=0){x=a;y=b;}
};
field operator*(field a,field b){return field(a.x*b.x%p+a.y*b.y%p*w%p,a.x*b.y%p+a.y*b.x%p);}int ran(){static int seed=23333;return seed=((((((ll)seed^20030927)%p+330802)%p*9410)%p-19750115+p)%p^730903)%p;
}int pows(int a,int b){int base=1;while(b){if(b&1) base=base*a%p;a=a*a%p;b/=2;}return base;
}field powfield(field a,int b){field base=field(1,0);while(b){if(b&1) base=base*a;a=a*a;b/=2;}return base;
}int legander(int x){int a=pows(x,(p-1)/2);if(a+1==p) return -1;return a;
}int surplus(int x){int a;if(legander(x)==-1) return 0;while(1){a=ran()%p;w=((a*a-x)%p+p)%p;if(legander(w)==-1) break;}field b=field(a,1);b=powfield(b,(p+1)/2);return b.x;
}

總結(jié)

以上是生活随笔為你收集整理的浅谈二次剩余的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。