二次剩余
当 $x^2\equiv a \pmod{n}$ 有解，称 $a$ 是模 $n$ 的二次剩余，以下大多讨论 $n$ 是奇素数（$\mathbb{P}_{odd}$）时的情况。
对于 $n \in \mathbb{P}_{odd}$，$1$ 到 $n-1$ 中正好有 $\frac{n-1}{2}$ 个二次剩余。
对于 $n \in \mathbb{P}_{odd}$，设 $a$，$b$ 为模 $n$ 的二次剩余，$i$，$j$ 不是模 $n$ 的二次剩余，则 $ab$，$ij$ 是二次剩余，而 $ai$ 不是二次剩余。证明过程要用到一点群论知识，$\mathbb{Z}^{+}_n$ 关于乘法成群，符合重排定理；易证两二次剩余之积为二次剩余，则 $a$ 的陪集中有一半（$a$ 与二次剩余的积）为二次剩余，剩下一半（$a$ 与非二次剩余的积）为非二次剩余，同理 $i$ 的陪集中有一半为非二次剩余，剩下的是二次剩余。
欧拉准则
对于 $n \in \mathbb{P}_{odd}$，$a$ 是一个模 $n$ 的二次剩余当且仅当 $$ a^{(n-1)/2}\equiv 1 \pmod{n} $$
勒让德（Legendre）符号
$p \in \mathbb{P}_{odd}$，定义 $$ \left(\frac{a}{p}\right)=\left{ \begin{array}{ll} 0 & a=0 \pmod{n} \\ 1 & a\ 是模\ n\ 的二次剩余 \\ -1 & a\ 不是模\ n\ 的二次剩余 \end{array} \right. $$
对于 $n \in \mathbb{P}_{odd}$，有定理： $$ \left(\frac{a}{n}\right)\equiv a^{(n-1)/2} \pmod{n} \tag{$\ast$} $$
但等式成立时 $n$ 不一定为素数。
雅可比（Jacobi）符号
设 $n$ 为正奇数，且 $n$ 的因式分解为： $$ n = \prod_{i=1}^{k} p_i^{e_i} $$ 那么雅可比符号定义为： $$ \left(\frac{a}{n}\right) = \prod_{i=1}^{k}\left(\frac{a}{p_i}\right)^{e_i} $$ 右边为勒让德符号。
重要区别：
- 勒让德符号是定义性的，只能用于奇素数；雅可比符号是计算性的，可以用于任何正奇数。
- 雅可比符号下 $\left(\frac{a}{n}\right)$ 为 1 并不能保证 $a$ 是 $n$ 的二次剩余。 设 $p$，$q$ 为素数，$a$ 是 $n=pq$ 的二次剩余，则 $a$ 必定也是 $p$ 和 $q$ 的二次剩余，因为 $(a-x^2)|n \Rightarrow (a-x^2)|p$，对 $q$ 同理，然而由雅可比符号定义可知，$a$ 同时是 $p$ 和 $q$ 的非二次剩余时，$\left(\frac{a}{n}\right)=(-1)\times(-1)=1$。
二次同余方程的解
$x^2\equiv n \pmod{p}\ , p \in \mathbb{P}_{odd}$ 的解为 $x\equiv (a+\sqrt{\omega})^{\frac{p+1}{2}}$，其中 $\omega=a^2-n$ 是 $p$ 的非二次剩余，$a$ 可随机选取，期望次数为 2。
注意到 $\omega$ 虽然是非二次剩余，但只要 $n$ 的确是二次剩余，在最终计算结果中 $\sqrt{\omega}$ 就会消去，就像虚数一样。
密码学应用
用勒让德符号计算 $(\ast)$ 时，等式不成立则 $n$ 一定是合数，等式成立 $n$ 却不一定是素数，但是会增加 $n$ 是素数的概率。这样就有了区别于费马小定理的素数判别方法。
求解二次同余方程的算法可用于 Rabin 公钥密码系统。
雅可比符号计算方法及欧拉拟素数的讨论见《计算机安全与保密》（清华大学出版社，2013 年 2 月第 1 版）第 61 页。