欧拉准则

在数论中，二次剩余的欧拉判别法（又称欧拉准则）是用来判定给定的整数是否是一个质数的二次剩余。

叙述

若 $p$ 是奇质数且 $p$ 不能整除 $d$ ，则：

d

是模

p

的二次剩余当且仅当：

d^{\frac {p-1}{2}}\equiv 1{\pmod {p}}

d

是模

p

的非二次剩余当且仅当：

d^{\frac {p-1}{2}}\equiv -1{\pmod {p}}

以勒让德符号表示，即为： $d^{\frac {p-1}{2}}\equiv \left({\frac {d}{p}}\right){\pmod {p}}$

举例

例子一：对于给定数，寻找其为二次剩余的模数

令 $a=17$ 。对于怎样的质数 $p$ ，17是模 $p$ 的二次剩余呢？

根据判别法里给出的准则，我们可以从小的质数开始检验。

首先测试 $p=3$ 。我们有： $17^{\frac {3-1}{2}}=17^{1}\equiv 2{\pmod {3}}\equiv -1{\pmod {3}}$ ，因此17不是模3的二次剩余。

再来测试 $p=13$ 。我们有： $17^{\frac {13-1}{2}}=17^{6}\equiv 1{\pmod {13}}$ ，因此17是模13的二次剩余。实际上我们有： $17\equiv 4{\pmod {13}}$ ，而 $2^{2}=4$ .

运用同余性质和勒让德符号可以加快检验速度。继续算下去，可以得到：

对于质数

p=13,19,\cdots ,{\frac {17}{p}}=+1

（也就是说17是模这些质数的二次剩余）。

对于质数

p=3,5,7,11,23,\cdots ,{\frac {17}{p}}=-1

（也就是说17是模这些质数的二次非剩余）。

例子二：对指定的质数p，寻找其二次剩余

哪些数是模17的二次剩余？

我们可以手工计算：

1^{2}=1

2^{2}=4

3^{2}=9

4^{2}=16

5^{2}=25\equiv 8{\pmod {17}}

6^{2}=36\equiv 2{\pmod {17}}

7^{2}=49\equiv 15{\pmod {17}}

8^{2}=64\equiv 13{\pmod {17}}

于是得到：所有模17的二次剩余的集合是 $\{1,2,4,8,9,13,15,16\}$ 。要注意的是我们只需要算到8，因为 $9=17-8$ ，9的平方与8的平方模17是同余的： $9^{2}=(-8)^{2}=8^{2}\equiv 13{\pmod {17}}$ .（同理不需计算比9大的数）。

但是对于验证一个数是不是模17的二次剩余，就不必将所有模17的二次剩余全部算出。比如说要检验数字3是否是模17的二次剩余，只需要计算 $3^{\frac {17-1}{2}}=3^{8}\equiv 81^{2}\equiv (-4)^{2}\equiv -1{\pmod {17}}$ ，然后由欧拉准则判定3不是模17的二次剩余。

欧拉准则与高斯引理以及二次互反律有关，并且在定义欧拉-雅可比伪素数（见伪素数）时会用到。

证明

首先，由于 $p$ 是一个奇素数，由费马小定理， $d^{p-1}\equiv 1{\pmod {p}}$ 。但是 $p-1$ 是一个偶数，所以有

(d^{\frac {p-1}{2}}-1)\cdot (d^{\frac {p-1}{2}}+1)\equiv 0{\pmod {p}}

$p$ 是一个素数，所以 $d^{\frac {p-1}{2}}-1$ 和 $d^{\frac {p-1}{2}}+1$ 中必有一个是 $p$ 的倍数。因此 $d^{\frac {p-1}{2}}$ 模 $p$ 的余数必然是1或-1。

证明若 $d$ 是模 $p$ 的二次剩馀，则 $d^{\frac {p-1}{2}}\equiv 1{\pmod {p}}$

若 $d$ 是模 $p$ 的二次剩馀，则存在 $x^{2}\equiv d{\pmod {p}}$ ， $p$ 跟 $d,x$ 互质。根据费马小定理得：

d^{\frac {p-1}{2}}\equiv x^{p-1}\equiv 1{\pmod {p}}

证明若 $d^{\frac {p-1}{2}}\equiv 1{\pmod {p}}$ ，则 $d$ 是模 $p$ 的二次剩馀

$p$ 是一个奇素数，所以关于 $p$ 的原根存在。设 $a$ 是 $p$ 的一个原根，则存在 $1\leq j\leq p-1$ 使得 $d=a^{j}$ 。于是

a^{j{\frac {p-1}{2}}}\equiv 1{\pmod {p}}

$a$ 是 $p$ 的一个原根，因此 $a$ 模 $p$ 的指数是 $p-1$ ，于是 $p-1$ 整除 ${\frac {j(p-1)}{2}}$ 。这说明 $j$ 是一个偶数。令 $i={\frac {j}{2}}$ ，就有 $(a^{i})^{2}=a^{2i}=d$ 。 $d$ 是模 $p$ 的二次剩余。