二次剩余定理详解

二次剩余

$$x^2≡n(mod\ p)$$

对于这个方程，求出满足的x。

引理1

首先来看一个符号

$$(\frac{n}{p})$$

这个符号叫做勒让德符号，这个符号里有两个值，一个是n,一个是p。假设p为奇素数，且n无法整除p时，他有以下定义

$$(\frac{n}{p})=n^{\frac{p-1}{2}}$$

当$(\frac{n}{p})=1$时，存在一个x使得n是p的二次剩余
当$(\frac{n}{p})=-1$时，不存在一个x使得n是p的二次剩余
例如，当p=11时。$(\frac{1}{11})=1^{\frac{11-1}{2}}=1(mod 11)$所以1是11的二次剩余
而，$(\frac{3}{11})=3^{\frac{11-1}{2}}=-1(mod 11)$所以3是11的二次非剩余
现在来证明

$$(\frac{n}{p})=n^{\frac{p-1}{2}}$$

这个等式

证明1

假设$(\frac{n}{p})=1$即n为p的二次剩余时，设解为x

根据费马小定理，我们知道$x^{p-1}≡1(mod p)$x显然存在

假设$(\frac{n}{p})=1$即n为p的二次剩余时

此时$x^2≡n(mod p)$无解
此时插入一个引理

若gcd(i,p)=1,且j为整数，则线性同余方程ix≡j(mod p)的有模p的唯一解(这里就不证明了，具体百度线性同余方程)

因此对于i在1~p-1中，对于每个gcd(1,i)=1都存在整数j使得ij≡n(mod p);
因此我们可以把1~p-1中的数分成(p-1)/2对，每对两两相乘=n(根据上面的定理可以自己推)
然后累乘起来得到

$$(p-1)!≡n^{\frac{p-1}{2}}(mod\ p)$$

由威尔逊定理得到$(p-1)!=-1(mod p)$(自行百度搜索威尔逊定理)
综上有

$$(\frac{a}{p})≡a^{\frac{p-1}{2}}(mod\ p)$$

引理2

有了上面的引理，我们来看看如何解这个方程。

首先我们在1~p-1上随机出一个a,然后设$w=a^2-n$，若w是p的二次非剩余，则解为$x=(a+\sqrt{w})^{\frac{p+1}{2}}$

为什么是这样？从末尾出发证明较为简单

证明2

$$\begin{align} &x^2\\ &=(a+\sqrt{w})^{p+1}\\ &=(a+\sqrt{w})^p*(a+\sqrt{w})\\ &=(a^p+{\sqrt{w}}^p)*(a+\sqrt{w})\\ &=(a-\sqrt{w})*(a+\sqrt{w})\\ &=a^2-w\\ &=a^2-(a^2-n)\\ &=n(mod\ p)\\ \end{align}$$

上述之中全都是在模p的意义下的运算，有一步骤可能有点蒙，现在我解释一下这一步
>

$$\begin{align} &=(a+\sqrt{w})^p*(a+\sqrt{w})\\ &=(a^p+{\sqrt{w}}^p)*(a+\sqrt{w})\\ &=(a-\sqrt{w})*(a+\sqrt{w})\\ \end{align}$$

先解释后两个等式，根据费马小定理，$a^{p-1}≡1(mod p)$，所以$a^p≡a(mod\ p)$。
因为w是p的二次非剩余，所以有$w^{\frac{p-1}{2}}≡-1(mod\ p)$,所以$w^{\frac{p}{2}}≡-\sqrt{w}(mod\ p)$

然后解释前两个等式

引理3

$$(a+b)^p = a^p+b^p(mod\ p)$$

证明3

首先，根据二项式定理展开，除了第一项和最后一项之外，都会有一个组合数$\frac{p}{i}$是无法除掉的，所以对p取模都等于0，因此只剩下最后两项。

证毕

你最愿意做的哪件事，才是你的天赋所在