一般二次同余式

二次同余式的一般形式是 $ax^2+bx+c\equiv0 \pmod m$

即对 $m$ 进行素因子分解，从而可以将上式等式进行转换

平方剩余与平方非剩余

定义1

若同余式 $x^2 \equiv a \pmod m, gcd(a,m)=1$ 有解，则 $a$ 叫 做模 $m$ 的平方剩余或二次剩余，否则称为平方非剩余。

定理1（欧拉判别条件）

设 $p$ 为素数，$gcd(a,p) = 1$，则

1. $a$ 是模 $p$ 的平方剩余等价于 $a^{\frac{p-1}2} \equiv 1 \pmod p$
2. $a$ 是模 $p$ 的非平方剩余等价于 $a^{\frac{p-1}2} \equiv -1 \pmod p$

证明1

• 充分性：
  若存在 $x$，使得 $x^2 \equiv a \pmod p$，且 $\gcd(x,p) \equiv 1$，由费马小定理 $x^{p-1}\equiv 1 \pmod p$，则 $x^{p-1} = (a^{\frac12})^{p-1} = a^{\frac{p-1}2}\equiv 1 \pmod p$

• 必要性：
  从原根的角度出发，设 $g$ 是 $p$ 的一个原根，则 $\lbrace g^1,g^2,\cdots,g^{p-1}\rbrace$ 是模 $p$ 的最即约系，故 $g^j \equiv a \pmod p$，由 $a^{\frac{p-1}2} \equiv 1 \pmod p$ 可得 $g^{\frac {j(p-1)}2} \equiv 1 \pmod p$。
  由费马小定理 $g^{p-1}\equiv 1 \pmod p$，则有 $p-1\mid \frac{j(p-1)}2$，说明 $j$ 为偶数，令 $j=2i$，则有 $(g^i)^2 \equiv a \pmod p$

证明2 将 $x^{p-1}\equiv 1 \pmod p$ 因式分解为 $(a^{\frac{p-1}2}-1)(a^{\frac{p-1}2}+1) \equiv 0 \pmod p$，故 $a^{\frac{p-1}2} \equiv \pm1 \pmod p$， $1$ 为剩余，故$-1$ 为非剩余。

定理2

设 $p$ 为奇素数，则模 $p$ 的简化剩余系中平方剩余与平方非剩余的个数各位 $(p-1)/2$，且 $(p-1)/2$ 个平方剩余与序列 $1^2,2^2,\cdots,(\frac {p-1}2)^2$ 中存在且仅与一个数同余。

证明

• 由定理一，可知平方剩余的个数相当于 $x^{\frac {p-1}2} \equiv 1 \pmod p$ 的解数，$(a^{\frac{p-1}2}-1),(a^{\frac{p-1}2}+1) \pmod p$ 解数相同。（待补充）
• 反证法，设$0 < k_1 < k_2 < \frac{p-1}2,k_1^2\equiv k_2^2 \pmod p$，则有$ (k_1+k_2)(k_1-k_2) \equiv 0 \pmod p$，然而 $1<k_1+k_2<p-1,\frac{p-1}2-1<k1-k2<0$，显然不成立。

勒让德符号

定义1

设 $p$ 是素数，定义勒让德符号如下:

定理1

定理2

以下证明代入公式即可验证

引理1

设 $p$ 为奇素数，$gcd(a,p)=1$。若 $a\cdot1,a\cdot2,\cdots,a\cdot{\frac{p-1}2}$ 中模 $p$ 的最小正剩余大于 $\frac p2$ 的个数是 $m$，则$(\frac ap)=a^{\frac{p-1}2}=(-1)^m$

证明：

1. 设 $a\cdot1,a\cdot2,\cdots,a\cdot{\frac{p-1}2}$ 中模 $p$ 有 $n$ 个小于 $\frac{p-1}2$，其为 $a_1,a_2,\cdots,a_n$，有 $m$ 个大于 $\frac{p-1}2$，其为$b_1,b_2,\cdots,b_m$，故 $m+n=\frac{p-1}2$。
2. 将 $\frac{p-1}2$ 个值连乘得到 $a^{\frac{p-1}2}\cdot \frac{p-1}2!\equiv \prod_{i=1}^na_i \cdot \prod_{j=1}^mb_j \equiv (-1)^m \prod_{i=1}^na_i \cdot \prod_{j=1}^m(p-b_j) \pmod p$
3. 下面需证明 $\lbrace a_1,a_2,\cdots,a_n,(p-b_1),(p-b_2),\cdots,(p-b_m) \rbrace$ 为 $\frac{p-1}2!$
4. 首先证明任意的 $i,j$，当 $i\not=j,a_i\not\equiv a_j \pmod p$，$a_i-a_j=a(i-j)$，由 $\gcd(a,p)=1,i-j\not = kp$，故 $i\not=j,a_i\not\equiv a_j \pmod p$，同理 $i\not=j,b_i\not\equiv b_j,(p-b_i)\not\equiv (p-b_j)\pmod p$。
5. 接下来证明任意 $a_i\not\equiv (p-b_i)\pmod p$，$a_i-(p-b_i)\equiv a(i+j)\pmod p$，由 $\gcd(a,p)=1,1< (i+j)< p-1$，故$a_i-(p-b_i)\not\equiv0 \pmod p$
6. 最后范围上显然是均是属于 $1$ 至 $\frac{p-1}2$，故第三点成立。$a^{\frac{p-1}2}\cdot \frac{p-1}2! $ 与 $(-1)^m \prod_{i=1}^na_i \cdot \prod_{j=1}^m(p-b_j)\equiv (-1)^m\cdot\frac{p-1}2! \pmod p$ 同时消去阶乘部分即得到$(\frac ap)=a^{\frac{p-1}2}\equiv(-1)^m\pmod p$。

二次互反律

若 $p,q$ 是互素奇素数，则

知乎证明：

上式引理中 $T(a,p) = \sum_{j=1}^{(p-1)/2}\lfloor \frac{ja}p\rfloor$，可以将其看作 $y=ja/p$，$T(a,p)$恰好表示了 $y=ja/p$ 下方所有整点的数量，同理$T(a,p)$恰好表示了 $y=jp/a$ 下方所有整点的数量。而这两块区域所有的点数和为 $\frac{p-1}2\cdot\frac{q-1}2$，能够快速算出，从而使得自反率能够成立。

雅可比符号

雅可比符号定义

设 $m=p_1\cdots p_r$ 是奇素数 $p_i$ 的乘积，对任意的整数 $a$，定义雅可比符号为:

雅可比符号是勒让德符号的推广，但是其所蕴含的意义已经不同，雅可比符号的 $1$ 不能用来判断 $a$ 是模 $m$ 的平方剩余。

雅可比-定理1

设 $m$ 是正奇数，则

1. $(\cfrac{a+m}m) = (\cfrac am)$
2. $(\cfrac{ab}m) = (\cfrac am)(\cfrac bm)$
3. $\gcd(a,m)=1\Rightarrow (\cfrac{a^2}{m})= 1$

证明依据定义将其拆开即可

雅可比-引理

设 $m=p_1\cdots p_r$ 是奇素数 $p_i$ 的乘积，则

证明

1. $m\equiv (1+2\cdot\frac{p_1-1}{2}\cdots(1+2\cdot\frac{p_r-1}{2}))\equiv1+2\cdot(\frac{p_1-1}{2}+\cdots+\frac{p_r-1}{2})\pmod4$
2. $m^2\equiv (1+8\cdot\frac{p_1^2-1}{2}\cdots(1+8\cdot\frac{p_r^2-1}{2}))\equiv1+8\cdot(\frac{p_1^2-1}{8}+\cdots+\frac{p_r^2-1}{8})\pmod{16}$

雅可比-定理2

设 $m$ 是正奇数，则

1. $(\cfrac 1m) = 1$
2. $(\cfrac{-1}m) = (-1)^{\frac{m-1}2}$
3. $(\cfrac 2m) = (-1)^{\frac{m^2-1}8}$

雅可比-定理3

当 $p,q$ 均为奇数时候，证明拆开即可

开平方根算法

假设 $x^2\equiv a \pmod p$有解，$p$ 是奇素数，求解$x$。

最终解分析

1. 如果整数 $q$ 为奇数，且 $a^q\equiv 1 \pmod p$，则$(\pm a^{\frac{q+1}{2}})^2\equiv a^{q+1} \equiv a \pmod p$，则立即可以找到 $x$ 的解为 $\pm a^{\frac{q+1}{2}}$
2. 如果上式中符合 $a^q\equiv 1 \pmod p$ 的 $q$ 为偶数，若可以通过构造使得 $a^q=(a^s)^{2^t}$ 中的 $2^t$ 消除并保证新乘上的东西是偶数幂，则可求得解。其中 $s$ 为奇数，$q$ 每消除一个因子 $2$，会乘上一个 $B_i^2$，形成 $B_1^2B_2^2\cdots B_t^2 \cdot a^s$ 的形式，即 $B_1^2B_2^2\cdots B_t^2\cdot a^s \equiv a^q \equiv 1 \pmod p$，这时可得到 $x$ 的解为 $\pm B_1B_2\cdots B_ta^{\frac {s+1}2} \pmod p$

求解过程

此过程为一个构造方法，保证在有解的情况下，一定能求出 $x$

1. 首先根据欧拉定理，有 $a^{p-1}\equiv 1 \pmod p$，$q = p-1$ 可以分解为 $q = 2^t\cdot s$，其中 $s$ 为奇数，令 $A = a^s$
2. 寻找一个 $b$，其是模 $p$ 的一个非二次剩余，则有 $b^{\frac{p-1}{2}} \equiv b^{\frac q2} \equiv (b^s)^{2^{t-1}} \equiv -1 \pmod p$。令 $B \equiv b^s \pmod p$，则有$B^{2^{t-1}}\equiv (b^s)^{2^{t-1}}\equiv -1 \pmod p$
3. 以上准备工作就绪，接下来进行计算过程
4. 当 $t=1$ 时，存在 $A^{2^{t-1}}\equiv A^0 \equiv a^s \equiv 1 \pmod p$，$s$ 为奇数 ，符合第一个最终解情况，

5. 当 $t>1$ 时，$A^{2^{t-1}} \equiv (A^{2^{t-2}})^2\equiv 1 \pmod p$，则 $A^{2^{t-2}}\equiv \pm1 \pmod p$，存在两种情况。通过以下构造

   \[\begin{cases} A^{2^{t-2}} \equiv 1 , &B_1^2=(B^{2^{t-1}})^{m_1=0}\equiv 1 \pmod p\\ A^{2^{t-2}} \equiv -1 \pmod p,& B_1^2=(B^{2^{t-1}})^{m_1=1}\equiv -1 \pmod p \end{cases}\]

6. 可以得到 $A^{2^s-1} \equiv A^{2^{s-2}}B_1^2 = A^{2^{s-2}}(B^{2^{t-1}})^{m_1} \equiv 1 \pmod p$

7. 当 $t=2$ 时，存在 $A^{2^{s-2}}B_1^2 = A^{2^{s-2}}(B^{2^{t-1}})^{m_1} \equiv a^s(B^2)^{m_1} \equiv 1 \pmod p$，符合最终解情况，可得到 $x$ 的解为 $\pm B^{m_1}a^{\frac {s+1}2} \pmod p$

8. 当 $t>2$ 时，$A^{2^{s-2}}B_1^2 = A^{2^{s-2}}(B^{2^{t-1}})^{m_1} \equiv 1 \pmod p$，则 $A^{2^{s-3}}(B^{2^{t-2}})^{m_1} \equiv \pm1 \pmod p$，存在两种情况。通过以下构造

   \[\begin{cases} A^{2^{s-3}}(B^{2^{t-2}})^{m_1} \equiv 1 , &B_2^2=(B^{2^{t-1}})^{m_2=0}\equiv 1 \pmod p\\ A^{2^{s-3}}(B^{2^{t-2}})^{m_1} \equiv -1 \pmod p,& B_2^2=(B^{2^{t-1}})^{m_2=1}\equiv -1 \pmod p \end{cases}\]

9. 可以得到 $A^{2^{s-2}}B_1^2 \equiv A^{2^{s-3}}B_1^2B_2^2= A^{2^{s-3}}(B^{2^{t-2}})^{m_1}(B^{2^{t-1}})^{m_2}\equiv 1 \pmod p$

10. 当 $t=3$ 时，存在 $A^{2^{s-3}}B_1^2B_2^2 = A^{2^{s-3}}(B^{2^{t-2}})^{m_1}(B^{2^{t-1}})^{m_2} \equiv a^s(B^2)^{m_1} (B^4)^{m_2}\equiv 1 \pmod p$，符合最终解情况，可得到 $x$ 的解为 $\pm B^{m_1}B^{2m_2}a^{\frac {s+1}2} \pmod p$

11. 上述过程展示了两次迭代，可以发现每次迭代，每次计算 $q$ 会除去一个 $2$。若不满足要求，继续迭代，最终显然会得到答案。