初等数论 第四章 二次剩余

这一章只考虑 $x^2$ 的问题.

集中在判断 $x^2 \equiv a \mod p (p>2)$ 有无解的问题.

原根

设 $p$ 是一个素数。如果存在一个整数 $g$ ，使得模 $p$ 的非零剩余类 $1, 2, 3, \ldots, p-1$都能写成 $g^k \bmod p$ 的形式 $(其中 k = 0, 1, 2, \ldots, p-2)$， 则称这个 $g$ 是模 $p$ 的原根。

性质

1. 模素数 $p$ 一定存在原根。
2. 模 $p$ 的原根的个数是 $\varphi(p-1)$，其中 $\varphi$ 是欧拉函数。
3. 若 $g$ 是模 $p$ 的原根，则 $g^k$ 也是原根，当且仅当 $\gcd(k, p-1) = 1$。

模为素数(p>2)的二次同余方程，解的存在性

$$x^2 \equiv a \pmod p$$

有解，则称 $a$ 是一个模 $p$ 的平方剩余，否则则称$a$ 是一个模 $p$ 的平方非剩余.

这是这一章最重要的东西，我们讨论二次同余方程在 $a$ 的影响下的解的情况.

对于 $p \mid a$ 则 $x^2 \equiv a \pmod p$ 必然有唯一解，不需要讨论

我们讨论的范围是 $(a,p) = 1$

例1 求模11的二次剩余

$$x^2 \equiv a \pmod{11}$$

将 $x$ 取遍 $[1,10]$ 得到 $a \in \{1,3,4,5,9\}$.

定理：Euler 判别法

设$p$是奇素数，则在模$p$的简化剩余系中，恰好有$\frac{p-1}{2}$个模$p$（非）剩余

简化剩余系 $\{1, \dots, p-1\}$ 中可能成为二次剩余的数至多为 $\frac{p-1}{2}$ 个，需要排除他们两两不互余的情况.

证明

完全剩余系 $\{0, 1, \dots, p-1\}$ 包含 0.

$$C = \{-\frac{p-1}{2}, (-\frac{p-1}{2}+1), \dots, \frac{p-1}{2}\}$$

$a^{\frac{p-1}{2}} \equiv 1 \bmod p$ 平方剩余

$a^{\frac{p-1}{2}} \equiv -1 \bmod p$ 非平方剩余

勒让德符号

用于研究模素数的二次剩余问题.

$$\Bigg( \frac{a}{p} \Bigg) = \begin{cases} +1, \quad &a为模p的平方剩余\\ -1, \quad &a为模p的平方非剩余\\ 0, \quad &p \mid a，不考虑的情况 \end{cases}$$