欧拉准则

字数 2984 2025-10-29 11:32:31

欧拉准则

欧拉准则是数论中一个关于二次剩余的基本判别法则，它利用模幂运算来简洁地刻画一个整数在模某个奇素数下的二次剩余性质。

第一步：回顾二次剩余的基本概念

首先，我们需要明确什么是二次剩余。设 \(p\) 是一个奇素数（即 \(p > 2\) 的素数），\(a\) 是一个整数。如果存在某个整数 \(x\) 使得同余方程

\[x^2 \equiv a \pmod{p} \]

有解，那么我们称 \(a\) 是模 \(p\) 的二次剩余。如果该方程无解，则称 \(a\) 是模 \(p\) 的二次非剩余。

一个关键的性质是：在模 \(p\) 的缩系（即从 \(1\) 到 \(p-1\) 这 \(p-1\) 个与 \(p\) 互素的整数）中，恰好有一半的数是二次剩余，另一半是二次非剩余。

第二步：引入欧拉准则的表述

欧拉准则提供了一个直接计算来判断 \(a\) 是否为模 \(p\) 的二次剩余的方法。其陈述如下：

设 \(p\) 是一个奇素数，\(a\) 是一个与 \(p\) 互素的整数（即 \(p \nmid a\)）。那么，

\[a^{\frac{p-1}{2}} \equiv \begin{cases} 1 \pmod{p}, & \text{如果 } a \text{ 是模 } p \text{ 的二次剩余} \\ -1 \pmod{p}, & \text{如果 } a \text{ 是模 } p \text{ 的二次非剩余} \end{cases} \]

第三步：证明欧拉准则（第一部分）

我们首先证明：如果 \(a\) 是模 \(p\) 的二次剩余，那么 \(a^{(p-1)/2} \equiv 1 \pmod{p}\)。

因为 \(a\) 是二次剩余，根据定义，存在整数 \(x\) 使得 \(a \equiv x^2 \pmod{p}\)。
现在计算 \(a^{(p-1)/2} \mod p\)：

\[ a^{\frac{p-1}{2}} \equiv (x^2)^{\frac{p-1}{2}} = x^{p-1} \pmod{p} \]

根据费马小定理，由于 \(p\) 是素数且 \(p \nmid x\)（因为 \(p \nmid a\)，所以 \(p \nmid x^2\)，进而 \(p \nmid x\)），我们有 \(x^{p-1} \equiv 1 \pmod{p}\)。
因此，\(a^{(p-1)/2} \equiv 1 \pmod{p}\)。

第四步：证明欧拉准则（第二部分）

接下来我们证明：如果 \(a^{(p-1)/2} \equiv 1 \pmod{p}\)，那么 \(a\) 是模 \(p\) 的二次剩余。这通常通过考虑一个“原根”来完成，但我们可以用一种不显式依赖原根概念的方法来理解。

考虑多项式 \(f(x) = x^{(p-1)/2} - 1\) 在模 \(p\) 意义下。这是一个次数为 \((p-1)/2\) 的多项式。
根据拉格朗日定理（模素数下的多项式同余方程，其解数不超过它的次数），方程 \(f(x) \equiv 0 \pmod{p}\) 在模 \(p\) 的缩系中至多有 \((p-1)/2\) 个解。
我们在第三步已经证明，所有的二次剩余（共有 \((p-1)/2\) 个）都是这个方程的解（因为对于二次剩余 \(a\)，有 \(a^{(p-1)/2} \equiv 1\)）。
由于二次剩余的个数正好是 \((p-1)/2\)，并且方程 \(f(x) \equiv 0\) 的解数不超过 \((p-1)/2\)，这意味着方程 \(x^{(p-1)/2} \equiv 1 \pmod{p}\) 的解，恰好就是所有的二次剩余。
因此，如果一个数 \(a\) 满足 \(a^{(p-1)/2} \equiv 1 \pmod{p}\)，它必然属于这个解集，即它必须是二次剩余。

第五步：完成证明并得出推论

结合第三和第四步，我们证明了 \(a^{(p-1)/2} \equiv 1 \pmod{p}\) 是 \(a\) 为模 \(p\) 二次剩余的充要条件。

现在，考虑 \(a^{(p-1)/2} \pmod{p}\) 可能的值。根据费马小定理，我们有：

\[(a^{(p-1)/2})^2 = a^{p-1} \equiv 1 \pmod{p} \]

这意味着 \(a^{(p-1)/2}\) 是方程 \(y^2 \equiv 1 \pmod{p}\) 的一个解。在模 \(p\) 下，这个方程只有两个解：\(y \equiv 1 \pmod{p}\) 和 \(y \equiv -1 \pmod{p}\)（因为 \(y^2 - 1 \equiv (y-1)(y+1) \equiv 0 \pmod{p}\)，而 \(p\) 是素数）。

我们已经知道，当且仅当 \(a\) 是二次剩余时，\(a^{(p-1)/2} \equiv 1\)。那么，对于不是二次剩余的数（即二次非剩余），由于 \(a^{(p-1)/2}\) 只能是 \(1\) 或 \(-1\)，并且不能是 \(1\)，所以它必须是 \(-1\)。
即：

\[a^{\frac{p-1}{2}} \equiv -1 \pmod{p} \quad \text{当且仅当} \quad a \text{ 是模 } p \text{ 的二次非剩余} \]

至此，欧拉准则的完整陈述和证明都已完成。

第六步：欧拉准则与勒让德符号的联系

欧拉准则为勒让德符号 \(\left(\frac{a}{p}\right)\) 提供了一个等价的定义。勒让德符号是一个数论函数，其值为：

\[\left(\frac{a}{p}\right) = \begin{cases} 1, & \text{如果 } a \text{ 是模 } p \text{ 的二次剩余} \\ -1, & \text{如果 } a \text{ 是模 } p \text{ 的二次非剩余} \\ 0, & \text{如果 } p \mid a \end{cases} \]

根据欧拉准则，我们可以将其写为：

\[\left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \pmod{p} \]

并且由于等式两边都是整数 \(1\)，\(-1\) 或 \(0\)，所以在整数意义上它们是相等的，而不仅仅是在模 \(p\) 意义下同余：

\[\left(\frac{a}{p}\right) = a^{\frac{p-1}{2}} \bmod p \quad \text{(这里 mod p 表示取模运算后得到代表元 0, 1 或 -1)} \]

这个公式是证明二次互反律等更深层次结果的重要工具。

欧拉准则欧拉准则是数论中一个关于二次剩余的基本判别法则，它利用模幂运算来简洁地刻画一个整数在模某个奇素数下的二次剩余性质。第一步：回顾二次剩余的基本概念首先，我们需要明确什么是二次剩余。设 \( p \) 是一个奇素数（即 \( p > 2 \) 的素数），\( a \) 是一个整数。如果存在某个整数 \( x \) 使得同余方程 \[ x^2 \equiv a \pmod{p} \] 有解，那么我们称 \( a \) 是模 \( p \) 的二次剩余。如果该方程无解，则称 \( a \) 是模 \( p \) 的二次非剩余。一个关键的性质是：在模 \( p \) 的缩系（即从 \( 1 \) 到 \( p-1 \) 这 \( p-1 \) 个与 \( p \) 互素的整数）中，恰好有一半的数是二次剩余，另一半是二次非剩余。第二步：引入欧拉准则的表述欧拉准则提供了一个直接计算来判断 \( a \) 是否为模 \( p \) 的二次剩余的方法。其陈述如下：设 \( p \) 是一个奇素数，\( a \) 是一个与 \( p \) 互素的整数（即 \( p \nmid a \)）。那么， \[ a^{\frac{p-1}{2}} \equiv \begin{cases} 1 \pmod{p}, & \text{如果 } a \text{ 是模 } p \text{ 的二次剩余} \\ -1 \pmod{p}, & \text{如果 } a \text{ 是模 } p \text{ 的二次非剩余} \end{cases} \] 第三步：证明欧拉准则（第一部分）我们首先证明：如果 \( a \) 是模 \( p \) 的二次剩余，那么 \( a^{(p-1)/2} \equiv 1 \pmod{p} \)。因为 \( a \) 是二次剩余，根据定义，存在整数 \( x \) 使得 \( a \equiv x^2 \pmod{p} \)。现在计算 \( a^{(p-1)/2} \mod p \)： \[ a^{\frac{p-1}{2}} \equiv (x^2)^{\frac{p-1}{2}} = x^{p-1} \pmod{p} \] 根据费马小定理，由于 \( p \) 是素数且 \( p \nmid x \)（因为 \( p \nmid a \)，所以 \( p \nmid x^2 \)，进而 \( p \nmid x \)），我们有 \( x^{p-1} \equiv 1 \pmod{p} \)。因此，\( a^{(p-1)/2} \equiv 1 \pmod{p} \)。第四步：证明欧拉准则（第二部分）接下来我们证明：如果 \( a^{(p-1)/2} \equiv 1 \pmod{p} \)，那么 \( a \) 是模 \( p \) 的二次剩余。这通常通过考虑一个“原根”来完成，但我们可以用一种不显式依赖原根概念的方法来理解。考虑多项式 \( f(x) = x^{(p-1)/2} - 1 \) 在模 \( p \) 意义下。这是一个次数为 \( (p-1)/2 \) 的多项式。根据拉格朗日定理（模素数下的多项式同余方程，其解数不超过它的次数），方程 \( f(x) \equiv 0 \pmod{p} \) 在模 \( p \) 的缩系中至多有 \( (p-1)/2 \) 个解。我们在第三步已经证明，所有的二次剩余（共有 \( (p-1)/2 \) 个）都是这个方程的解（因为对于二次剩余 \( a \)，有 \( a^{(p-1)/2} \equiv 1 \)）。由于二次剩余的个数正好是 \( (p-1)/2 \)，并且方程 \( f(x) \equiv 0 \) 的解数不超过 \( (p-1)/2 \)，这意味着方程 \( x^{(p-1)/2} \equiv 1 \pmod{p} \) 的解，恰好就是所有的二次剩余。因此，如果一个数 \( a \) 满足 \( a^{(p-1)/2} \equiv 1 \pmod{p} \)，它必然属于这个解集，即它必须是二次剩余。第五步：完成证明并得出推论结合第三和第四步，我们证明了 \( a^{(p-1)/2} \equiv 1 \pmod{p} \) 是 \( a \) 为模 \( p \) 二次剩余的充要条件。现在，考虑 \( a^{(p-1)/2} \pmod{p} \) 可能的值。根据费马小定理，我们有： \[ (a^{(p-1)/2})^2 = a^{p-1} \equiv 1 \pmod{p} \] 这意味着 \( a^{(p-1)/2} \) 是方程 \( y^2 \equiv 1 \pmod{p} \) 的一个解。在模 \( p \) 下，这个方程只有两个解：\( y \equiv 1 \pmod{p} \) 和 \( y \equiv -1 \pmod{p} \)（因为 \( y^2 - 1 \equiv (y-1)(y+1) \equiv 0 \pmod{p} \)，而 \( p \) 是素数）。我们已经知道，当且仅当 \( a \) 是二次剩余时，\( a^{(p-1)/2} \equiv 1 \)。那么，对于不是二次剩余的数（即二次非剩余），由于 \( a^{(p-1)/2} \) 只能是 \( 1 \) 或 \( -1 \)，并且不能是 \( 1 \)，所以它必须是 \( -1 \)。即： \[ a^{\frac{p-1}{2}} \equiv -1 \pmod{p} \quad \text{当且仅当} \quad a \text{ 是模 } p \text{ 的二次非剩余} \] 至此，欧拉准则的完整陈述和证明都已完成。第六步：欧拉准则与勒让德符号的联系欧拉准则为勒让德符号 \( \left(\frac{a}{p}\right) \) 提供了一个等价的定义。勒让德符号是一个数论函数，其值为： \[ \left(\frac{a}{p}\right) = \begin{cases} 1, & \text{如果 } a \text{ 是模 } p \text{ 的二次剩余} \\ -1, & \text{如果 } a \text{ 是模 } p \text{ 的二次非剩余} \\ 0, & \text{如果 } p \mid a \end{cases} \] 根据欧拉准则，我们可以将其写为： \[ \left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \pmod{p} \] 并且由于等式两边都是整数 \( 1 \)，\( -1 \) 或 \( 0 \)，所以在整数意义上它们是相等的，而不仅仅是在模 \( p \) 意义下同余： \[ \left(\frac{a}{p}\right) = a^{\frac{p-1}{2}} \bmod p \quad \text{(这里 mod p 表示取模运算后得到代表元 0, 1 或 -1)} \] 这个公式是证明二次互反律等更深层次结果的重要工具。