---
url: https://xuehaizhixing.com/root/B01-数论基础/M02-同余理论/S07/B01-M02-S07-U02.md
---

# 一、模块层

* **知识点编号**：B01-M02-S07-U02
* **所属模块**：B01 → M02 → S07

## 纵向关联

* 上接：
  * 无
* 下启：
  * [勒让德符号定义题根](/root/B01-数论基础/M02-同余理论/S07/B01-M02-S07-U03)
  * [勒让德符号性质题根](/root/B01-数论基础/M02-同余理论/S07/B01-M02-S07-U04)

## 知识关联

### 横向关联

* 前置基础：
  * `整除性归纳题根`
  * `第二归纳法题根`
  * [质因数分解法求gcd题根](/root/B01-数论基础/M01-整除与质数/S03/B01-M01-S03-U03)
  * `分组分解法题根`
* 同位衔接：
  * [指数型方程形式题根](/root/B01-数论基础/M03-不定方程/S05/B01-M03-S05-U01)
  * `概率与数论结合题根`
  * `数列与质数题根`
* 后续延伸：
  * `高联数论压轴题根`
  * `舒尔定理题根`
  * `数论组合计数题根`
  * `数论组合极值题根`
  * [原根与指数进阶题根](/root/B01-数论基础/M04-数论函数与进阶技巧/S04/B01-M04-S04-U04)
  * `CMO数论组合融合题根`
  * `正交拉丁方题根`
  * [模论高阶应用题根](/root/B01-数论基础/M04-数论函数与进阶技巧/S04/B01-M04-S04-U03)

# 二、本源层

* **本源**：
  欧拉判别法将二次剩余判断从枚举$x^2$的$O(p)$计算简化为一次模幂$a^{(p-1)/2}\bmod p$的$O(\log p)$运算。其数学根源在于费马小定理$a^{p-1}\equiv1$：开平方得$a^{(p-1)/2}\equiv\pm1$，而$a^{(p-1)/2}\equiv1$当且仅当$a$是平方元（利用原根表示$a\equiv g^k$，则$a^{(p-1)/2}\equiv g^{k(p-1)/2}=1\iff2\mid k$即$k$为偶，故$a$是平方）。这一判别法不仅是高效的实用工具，更是连接二次剩余定义与勒让德符号代数性质的桥梁。

从更根本的层面看，这一性质来源于数学对象在某种变换下的不变性。抓住这个不变性，就抓住了概念最核心的直觉。

理解这一本源意味着：不再把数学规则当作孤立的记忆条目，而是看作从一条根本事实生长出来的有机体系。

本源的价值在于它在最朴素层面回答了“为什么”——不借助任何形式化语言，你也能向一个初学者讲清楚这个概念的来龙去脉。

* **原点**：
  欧拉判别法（Euler's Criterion）：设$p$为奇质数，$a$为与$p$互质的整数。则$a^{(p-1)/2}\equiv1\pmod p$当且仅当$a$是模$p$的二次剩余；$a^{(p-1)/2}\equiv-1\pmod p$当且仅当$a$是模$p$的二次非剩余。这一简洁法则将二次剩余的判断归结为一次模幂运算，远比枚举$x^2$高效。其核心逻辑链条为：费马小定理$a^{p-1}\equiv1$给出全局信息→取平方根得$a^{(p-1)/2}\equiv\pm1$（因模$p$下$1$的平方根仅有$\pm1$）→利用原根$g$将$a$表为$g^k$，则$a^{(p-1)/2}=g^{k(p-1)/2}=1\iff2\mid k\iff a$为平方元。这一从"全局必$1$"到"局部判$\pm1$"的思维跃迁，是数论中将已知全局结论深化为精细局部信息的典范策略。；从更形式化的角度审视，这里的数学结构可以进一步抽象。如果将满足该性质的对象构成的集合记为某一类，则该集合在相应的运算下具有封闭性——这是代数结构的雏形。；这一原点是连接直觉与形式的桥梁：一边是直觉层面朴素易懂的分类观念，另一边是严格的形式化系统。理解这个连接点，才能真正从“感觉懂了”过渡到“严格证明了”。；特别要注意的是，原点的选取方式不是唯一的，但不同选取方式最终构建出来的理论体系应当是等价的——这是数学中公理系统等价性的思想萌芽。；从教学设计的角度看，原点被精确定位为：学生可以用已有知识立即理解的最简形式化陈述，不需要额外铺垫，且能在此基础上进行逻辑推导。；这一原点的另一重要特征在于：它既是最简单的形式化陈述，也是所有后续推理的“保真性”来源——任何结论的可靠性都可以通过归约到原点来检验。

* **道法**：
  **首锚·不变量思想**：欧拉判别法的核心关联是费马小定理$a^{p-1}\equiv1$在指数减半下的不变量——$a^{(p-1)/2}$的取值被锁定为$\pm1$，$+1$对应平方元、$-1$对应非平方元。这一"指数减半判平方"的策略将二次剩余判定从枚举转化为一次模幂计算。
  **次锚·同余与模结构**：判别法的两种策略——方法一直接计算$a^{(p-1)/2}\bmod p$判断$\pm1$，适合中小模数手算；方法二利用原根表示$a\equiv g^k$，通过$k$的奇偶性判断$k$为偶则$a$是二次剩余。选哪种取决于是否有现成的原根表——有则用原根法理解本质，无则用直接计算法。
  **三锚·构造思想**：从欧拉判别法可提炼通法——研究指数运算与代数结构的关系：$a^{(p-1)/2}$不是任意值，而是被模$p$下$1$的平方根仅两个的事实约束。这在更一般的框架下是群中元素阶的分析技术——在任意有限群$G$中，$g^{|G|/2}$的取值同样受到约束。
  **解题三问**：$p$是否为奇质数？$\gcd(a,p)=1$是否成立？若结果为$1$，是否还能通过枚举验证确认（当$p$较小）？

* **关键心法**：
  欧拉判别之法，核心在于费马小定理的指数减半评价——$a^{p-1}\equiv1$开方得$\pm1$，$+1$对应剩余、$-1$对应非余。此法以一己之力将$O(p)$枚举简化为$O(\log p)$模幂，是数论中效率革命之典范。

掌握这一心法意味着：面对一个具体问题，你的第一反应不是套公式，而是先问“这属于哪一类？”——这是从“术”到“道”的跨越。

* **终极一句话**：
  $a^{(p-1)/2}\equiv\begin{cases}1&\text{若}a\text{是二次剩余}\\-1&\text{若}a\text{是二次非剩余}\end{cases}\pmod p$。欧拉判别法将二次剩余判断从$O(p)$次枚举简化为$O(\log p)$次模幂，用指数减半的代数视角替代了枚举查表的朴素做法，是二次剩余理论从"算"到"判"的关键转折点。；这句话浓缩了该概念最本质的数学事实，每一个字都经得起推敲。理解这句话，就掌握了进入该领域的钥匙。；这一句话应当像“锚”一样牢牢钉在脑海中——每当你迷失在具体计算的细节中时，回到这句话就能重新找到方向。

* **数学思想进化轴**：费马小定理$p\nmid a\Rightarrow a^{p-1}\equiv1\pmod p$确立了$a^{p-1}$的全局结构→欧拉敏锐地将指数$p-1$减半为$(p-1)/2$，发现结果只能是$\pm1$，并首次指出$+1$对应二次剩余、$-1$对应二次非剩余，从而将二次剩余判定从枚举法提升为代数判别法→勒让德1785年将$a^{(p-1)/2}\equiv\left(\frac{a}{p}\right)$作为勒让德符号的等价定义，标志着欧拉判别法从"计算工具"升级为"符号代数"的核心构件→高斯在《算术研究》的二次互反律证明（共8种证法）中反复运用欧拉判别法的思想，特别是利用原根将$a$表为$g^k$后通过$k$的奇偶性判定平方性，这一思路成为后续所有互反律证明的基本策略→现代数论中，欧拉判别法被推广到有限域$\mathbb{F}\_q$上的平方判别（$a^{(q-1)/2}\equiv\pm1$），成为一般有限域上二次剩余理论的基础工具。

该知识点在竞赛层面的进化呈现出明显的"工具化"趋势：从最初的概念理解到方法掌握，再到策略层面的灵活运用，最后升华为一种数学思想渗透到各个分支。竞赛数学中最高明的解题技巧往往不是新创造的方法，而是对已有知识的深度理解和跨域迁移。理解这一进化轨迹，有助于在竞赛中实现"以不变应万变"的境界。

该知识点在竞赛层面的进化呈现出明显的"工具化"趋势：从最初的概念理解到方法掌握，再到策略层面的灵活运用，最后升华为一种数学思想渗透到各个分支。竞赛数学中最高明的解题技巧往往不是新创造的方法，而是对已有知识的深度理解和跨域迁移——将看似不相关的概念联系起来，或者将一个领域的思维工具应用到另一个领域。理解这一进化轨迹，有助于在竞赛中实现"以不变应万变"的境界：无论题目如何变化，都能在已掌握的知识体系中找到合适的工具。
；该知识点在竞赛层面的进化呈现出明显的"工具化"趋势：从最初的概念理解到方法掌握，再到策略层面的灵活运用，最后升华为一种数学思想渗透到各个分支。竞赛数学中最高明的解题技巧往往不是新创造的方法，而是对已有知识的深度理解和跨域迁移——将看似不相关的概念联系起来，或者将一个领域的思维工具应用到另一个领域。理解这一进化轨迹，有助于在竞赛中实现"以不变应万变"的境界：无论题目如何变化，都能在已掌握的知识体系中找到合适的工具。

# 三、知识点层

* **知识点编号**：B01-M02-S07-U02

* **名称**：欧拉判别法题根

* **标准定义**：

* 欧拉判别法（欧拉准则）：设$p$为奇质数，$a$为整数且$\gcd(a,p)=1$。则$a$是模$p$的二次剩余当且仅当$a^{(p-1)/2}\equiv1\pmod p$；$a$是模$p$的二次非剩余当且仅当$a^{(p-1)/2}\equiv-1\pmod p$。该法则给出了二次剩余判别的代数方法，避免了枚举法。；- 等价形式：勒让德符号$\left(\frac{a}{p}\right)$满足$\left(\frac{a}{p}\right)\equiv a^{(p-1)/2}\pmod p$。这一等价形式将勒让德符号的计算转化为模幂运算，使符号的许多性质（如积性）可以通过指数运算的性质直接推导。；- 原根证明法（结构理解）：设$g$为模$p$的一个原根，则任何$a$可唯一表示为$a\equiv g^k$（$0\le k\<p-1$）。于是$a^{(p-1)/2}\equiv g^{k(p-1)/2}$。由于$g$的阶为$p-1$，$g^{k(p-1)/2}=1\iff(p-1)\mid k(p-1)/2\iff 2\mid k$。而$k$为偶数等价于$a\equiv(g^{k/2})^2$是平方元。故$a^{(p-1)/2}\equiv1\iff a$是二次剩余。这一证明深刻揭示了欧拉判别法的本质：二次剩余性完全由原根指数$k$的奇偶性决定。；- 适用范围与限制：欧拉判别法要求$p$为奇质数（$p=2$时指数$(p-1)/2=0.5$不是整数，需单独处理），且$\gcd(a,p)=1$。当$p\mid a$时$a^{(p-1)/2}\equiv0\pmod p$，但此时$a$既非二次剩余也非二次非剩余。这些边界条件是使用判别法前必须确认的前提。；从等价关系角度看，这一定义实际上建立了一个划分：它将所有可能的情形分为互不相交的两类，且覆盖了全集。这是一个最简单的二元分类系统。；在实际解题中，这一定义提供了三种判定策略：(1)正面验证——直接检查条件是否成立；(2)反面排除——检查是否属于另一类来确定；(3)等价转化——利用该定义的某个等价刻画来判定。；该定义还有一个重要推论：若某对象满足定义条件，则它自动具有该类别的一切性质；反之，若某性质在某对象上不成立，则该对象必不属于此类别。；特别需要注意两件事：一是定义中条件的充分必要性——既不能多也不能少；二是定义的边界情形——当条件处于模糊地带时该如何判定。；从更广泛的数学体系来看，这一定义不是孤立的，它与后续若干定理之间存在密切的内在联系。这些联系将随着学习的深入逐次展现。

* **核心本质**：
  **欧拉判别法的本质是费马小定理的深化——由费马小定理$a^{p-1}\equiv1$知$a^{(p-1)/2}$是$1$的平方根，而在模$p$下$1$的平方根仅有$\pm1$两个。$a^{(p-1)/2}=1$对应$a$是平方元，$a^{(p-1)/2}=-1$对应$a$不是平方元。**
  **锁死·综合融合层通用内容**：在综合评价层面，欧拉判别法不应仅看作"算幂看结果"的流程化工具，而应理解其在整个二次剩余理论中的枢纽地位。首先，它架起了费马小定理与二次剩余之间的桥梁——费马小定理给出了$a^{p-1}$的全局结果，欧拉将指数减半挖掘出局部结构，这是数学中"通过全局信息获取局部信息"的典型策略。其次，它通过原根法揭示了判别法的本质——$a\equiv g^k$时$a^{(p-1)/2}\equiv g^{k(p-1)/2}=1\iff2\mid k$，将"二次剩余"问题还原为"指数奇偶"问题，完成了从数值计算到结构判断的跃迁。最后，它在方法论层面示范了"充要条件"的力量——判别法给出了$a$是二次剩余的充分必要条件（不是仅充分或仅必要），这意味着计算结果$\pm1$与二次剩余性之间存在一一对应关系，没有歧义。理解这三点，才能真正把握欧拉判别法在综合融合层中"承上启下"的核心地位。

这一本质深刻揭示了一个事实：表面上的数值多样性掩盖了底层的结构统一性。一旦掌握了这个统一性，看似千变万化的问题都可以归结为同一种分析框架来处理。

从方法论的角度看，核心本质的价值在于它提供了一种“升维思考”的路径——从具体操作层面上升到结构分析层面。

深入把握这一本质意味着：看到一个数学表达式时，你自动会问“这个数模某数余几？”而不是“这个数等于多少？”——从“具体值思维”到“等价类思维”的转变。

这一本质实际上是某种更大理论框架的特例或雏形。当学生的知识体系足够完善后，这个本质将会自然衔接上更高级的理论，成为后续学习的认知锚点。

从思维训练的角度看，核心本质的价值在于它如何改变你看待问题的方式：“存在多少个不同的类别？这些类别之间有什么运算规则？”——这种思考模式是代数思维的起点。

* **核心性质**：
* 性质一：$a^{(p-1)/2}$只在$\pm1$中取值——由费马小定理$a^{p-1}\equiv1$可得$(a^{(p-1)/2})^2\equiv1$，故$a^{(p-1)/2}\equiv\pm1$。这是判别法的可行性基础。数学意义：二次剩余的判别简化为区分$1$和$-1$的二选一问题。
* 性质二：二次剩余对应$+1$——若$a$是二次剩余（$a\equiv x^2$），则$a^{(p-1)/2}\equiv x^{p-1}\equiv1$（费马小定理）。反之同样成立（用原根可证）。数学意义：欧拉判别法不仅必要而且充分，是充要条件。
* 性质三：结合快速幂的高效性——计算$a^{(p-1)/2}\bmod p$可用快速幂在$O(\log p)$次模乘内完成。对百位数的$p$，手算可行；对千位数的$p$，计算机轻松处理。数学意义：欧拉判别法的时间复杂度是多项式对数级别的，远优于枚举法的线性级别。
* 性质四：勒让德符号的桥梁作用——欧拉判别法直接导出勒让德符号公式$\left(\frac{a}{p}\right)\equiv a^{(p-1)/2}\pmod p$。这一关系使符号的计算与模幂运算等价，符号的积性等代数性质也可以此为基础证明。数学意义：欧拉判别法是连接二次剩余定义与勒让德符号代数性质的桥梁。
* 性质五：与费马小定理的逻辑层级——欧拉判别法不是费马小定理的直接推论，而是费马小定理与平方根分析结合的产物。费马小定理给出$a^{p-1}\equiv1$的全局结果，欧拉将指数减半后需额外论证$+1$对应平方元（利用原根），而非简单的代数推导。数学意义：理清两个定理之间的"深化"而非"推论"关系，避免因果混淆。

# 四、教案版本

## 【专业版】

### 【基础层例题】

用欧拉判别法判断$3$是否为模$7$的二次剩余。

* **解题思路**：①问题定位：用欧拉判别法判断$3$是否为模$7$的二次剩余，即计算$3^{(7-1)/2}\bmod7$并看结果为$1$还是$-1$。②方法一（直接计算法）：$3^3=27\equiv6\equiv-1\pmod7$，结果$-1$故$3$为二次非剩余；方法二（枚举验证法）：枚举$x=1,2,3$的平方模$7$得$1,4,2$，$3$未出现，确认非剩余。③双法互补：欧拉判别法高效但需要理解指数运算，枚举法直观但仅适合小$p$，两者相互验证增强信心。
* **标准解答**：$3^{(7-1)/2}=3^3=27\equiv6\equiv-1\pmod7$。结果为$-1$，故$3$是模$7$的二次非剩余。验证：$1^2=1,2^2=4,3^2=2\pmod7$，确实没有$3$。答案：非剩余。
  上述解答过程中，每一步推导的依据是该知识点的核心性质——准确把握每一步的逻辑基础，是确保解题正确性的关键。
  这道题还可以从另一个角度切入：通过构造等价条件或转化视角，往往能得到更简洁的解法。
  验证是解题的重要环节——将答案代回原题检验是否满足所有条件，既能确认正确性，也能培养良好的解题习惯。
  从思维训练的角度看，这道题考察的核心能力是在复杂条件中识别出可应用该知识点的结构特征——这种识别能力是数学素养的重要组成部分。
  竞赛解题不仅要求得出正确答案，更要求对解题路径有清晰的元认知——知道为什么要选这个方法而不是其他，以及这个方法在什么情况下会失效。这种策略层面的理解是区分竞赛高手和普通选手的关键。
  竞赛解题不仅要求得出正确答案，更要求对解题路径有清晰的元认知——知道为什么要选这个方法而不是其他，以及这个方法在什么情况下会失效。这种策略层面的理解是区分竞赛高手和普通选手的关键。### 【易错变式题】
  判断$a=1$是否为模$p$的二次剩余。
* **常见错误**：①具体策略失误：认为$1^{(p-1)/2}=1$就自动得出$1$是二次剩余，但忽略了$p=2$时$(p-1)/2=0.5$不是整数，欧拉判别法对$p=2$不适用。②评价能力原因：学生机械套用公式$a^{(p-1)/2}\equiv\pm1$，未认识到判别法对$p$的条件约束（仅限于奇质数），缺乏对公式适用范围的主动审查意识。③忽视的策略维度：判别法的适用范围($p$为奇质数)与结论判读同等重要——使用时必须先确认$p$为奇质数且$\gcd(a,p)=1$,两个条件缺一不可。
* **解题思路**：①问题定位：判断$a=1$是否为模$p$的二次剩余，即计算$1^{(p-1)/2}$模$p$的值并解读。②方法一（欧拉判别法）：$1^{(p-1)/2}=1$恒成立，故对任何奇质数$p$，$1$总是二次剩余；方法二（直接观察法）：$1\equiv1^2$，故$1$本身就是一个平方数，显然为二次剩余。③双法互补：欧拉判别法给出代数确认，直接观察法给出直观理解，两者结合可验证$p=2$时的特殊情况（$1$仍为模$2$的二次剩余）。
* **标准解答**：$1^{(p-1)/2}=1$，对任何$p$结果都是$1$，故$1$总是模$p$的二次剩余（$1\equiv1^2$）。$p=2$时也成立：$1$是模$2$的二次剩余。答案：是。

**复盘要点**：该错误在竞赛中真实出现频率较低，但暴露了对判别法适用条件的认知盲区。处理策略是建立"使用前三查"习惯：一查$p$是否为奇质数（$p=2$单独处理），二查$\gcd(a,p)=1$，三查公式$a^{(p-1)/2}$的指数是否为整数。

### 【高阶例题】

利用欧拉判别法证明：若$p$为奇质数，则模$p$的二次剩余恰有$(p-1)/2$个。

* **方法策略**：①问题结构与关联识别：需证明二次剩余恰有$(p-1)/2$个，这关联多项式$x^{(p-1)/2}-1$在域$\mathbb{F}\_p$中的根计数——每个二次剩余$y^2$代入得$y^{p-1}-1=0$，故二次剩余都是此多项式的根。②策略选择与适用评价：核心策略是构造$f(x)=x^{(p-1)/2}-1$，用域论中$n$次多项式至多有$n$个根的性质得到上界$(p-1)/2$，再用具体构造$1^2,2^2,\dots$得到下界$(p-1)/2$，上下界夹逼得恰为$(p-1)/2$。此法严谨且具有一般性——推广到任意有限域上同样成立。③通用提炼与延伸：从本题可提炼"多项式根计数夹逼"的通法——先用代数理论得到上界，再用具体构造得到下界，两者相等即得精确计数。这一技术在处理有限域上各种子集计数问题时极为常用。
* **标准解答**：考虑多项式$f(x)=x^{(p-1)/2}-1$。对每个二次剩余$a\equiv y^2$，$f(a)=y^{p-1}-1\equiv0$。故$(p-1)/2$个二次剩余都是$f(x)=0$的根。由多项式在域中的性质，$f(x)=0$至多有$(p-1)/2$个根，故二次剩余恰好$(p-1)/2$个。证毕。；。

##

这道题还可以从另一个角度切入：通过构造等价条件或转化视角，往往能得到更简洁的解法。【药典版】

### 定位：二次剩余的"试金石"

#### 🌱 药材本体

* **第一味药——欧拉判别法公式**：$a^{(p-1)/2}\equiv1\pmod p$（二次剩余）或$\equiv-1$（二次非剩余）。这是核心判别工具。
* **第二味药——费马小定理基础**：判别法源于$a^{p-1}\equiv1$，开平方得$\pm1$。费马小定理是判别法的逻辑根基。
* **第三味药——快速幂计算**：$O(\log p)$步完成的模幂算法，使判别法在实用中高效可行。
* **第四味药——充要性**：欧拉判别法是充要条件——结果$1$一定能推出$a$是二次剩余，结果$-1$一定能推出$a$是二次非剩余。双向逻辑锁定。
* **药材核心药性**："一算定是非——$(p-1)/2$次幂，$+1$为剩余，$-1$为非余"。
  该知识点的竞赛药性在于其综合评价价值——它不仅能独立解题，更能与其他概念联用形成强大的策略体系。掌握其药性，就掌握了竞赛解题的战略主动权。

#### 🛠️ 功能主治

* **主治**：枚举平方判断二次剩余太慢——$O(p)$次计算，$p$稍大就不可行
* **解决**：不会用代数方法判断二次剩余——只知道枚举法，缺乏更高效的代数工具
* **根治**：对二次剩余判别法缺乏理论理解——不知为何$x^{(p-1)/2}$能区分剩余与非剩余
* **打通**：从费马小定理到二次剩余的桥梁——同样基于模$p$下的指数运算性质

该主治在竞赛层面的意义在于——知道这个方法在什么情况下是"最优选择"，以及什么情况下应该"果断放弃换方法"——这种策略判断力是竞赛能力的核心。

该主治在竞赛层面的意义在于——知道这个方法在什么情况下是"最优选择"，以及什么情况下应该"果断放弃换方法"——这种策略判断力是竞赛能力的核心。#### 🧪 核心药方

1. **直接计算方**——对给定的$a$和$p$，计算$a^{(p-1)/2}\bmod p$，看结果是$1$还是$-1$。适配基础表达阶。
2. **快速幂方**——当$p$较大时，用快速幂算法（反复平方法）高效计算$a^{(p-1)/2}\bmod p$。适配进阶表达阶。
3. **理论证明方**——用欧拉判别法证明二次剩余的性质，如积性、$-1$和$2$的特殊公式等。适配高阶表达阶。

数论学习中，

#### 🌌 药理

**一算定是非，简洁而深刻。**

欧拉判别法的发现是二次剩余理论系统化的关键一步。在欧拉之前，判断一个数是否为模$p$的二次剩余只能通过枚举平方——当$p$很大时几乎不可能。欧拉敏锐地观察到，费马小定理$a^{p-1}\equiv1$意味着$a^{(p-1)/2}$是$1$的平方根。在模$p$的世界里，$1$的平方根只有$\pm1$两个，前者对应$a$的$(p-1)/2$次方的值为$1$，后者为$-1$。欧拉猜想这个$\pm1$正好对应二次剩余和非剩余——这个猜想后来得到严格证明。欧拉判别法的证明思路（利用原根）本身也很优美：设$g$是模$p$的原根，则$a\equiv g^k$。$a^{(p-1)/2}\equiv g^{k(p-1)/2}$，而这就是$1$当且仅当$(p-1)\mid k(p-1)/2$，即$k$为偶数。但$k$为偶数时$a\equiv g^k=(g^{k/2})^2$恰为平方元。所以$a^{(p-1)/2}\equiv1\iff a$是二次剩余。欧拉判别法的简洁和深刻体现在它只用了$O(\log p)$次模乘就给出了二次剩余的充要判别——这在18世纪是革命性的进步。

#### 👨‍🏫 老师修炼阶梯

* **基础表达**：知法则、会计算小$p$下的$a^{(p-1)/2}\bmod p$
* **进阶表达**：用快速幂高效计算较大$p$的判别、会推广到勒让德符号
* **高阶表达**：用欧拉判别法证明二次剩余的各种性质、解决相关数论问题
* **顶阶表达**：能讲欧拉判别法与原根的关系、能理解其在二次互反律证明中的作用

#### 🗣️ 一句话封神

$a^{(p-1)/2}\equiv\pm1\pmod p$——欧拉一算，二次剩余立现。
数学学习的关键不在于刷了多少题，而在于是否建立了知识之间的联系——当不同模块的知识在心中形成网络，解题就不再是搜索记忆而是自然涌现。
真正的高手不是记得多少公式，而是能看到不同方法背后的统一思想——这就是数学的眼光。
从"学会"到"会用"之间，差的是对知识本质的理解——不是知道结论，而是知道结论为什么成立，以及结论在什么条件下会失效。
当你能用自己的语言解释一个概念、能判断它什么时候适用、能把它和其他知识联系起来——这时你才算真正掌握了它。
数学学习的关键不在于刷了多少题，而在于是否建立了知识之间的联系——当不同模块的知识在心中形成网络，解题就不再是搜索记忆而是自然涌现。#### 🩺 一眼诊断

* **结果误读型**：算出$a^{(p-1)/2}=1$不知是剩余、算出$-1$不知是非剩余——$\rightarrow$明确记忆规则：$+1=$剩余，$-1=$非剩余
* **快速幂生疏型**：知道公式但不会高效计算大指数——$\rightarrow$练习反复平方法（快速幂），将指数$(p-1)/2$二进制分解后逐次平方
* **$p=2$忽略型**：将欧拉判别法用于$p=2$——$\rightarrow$注意$p=2$时$(p-1)/2=0.5$不是整数，欧拉判别法只适用于奇质数$p$
* **充要性信念不足型**：觉得结果$1$也可能偶然成立而$a$不是二次剩余——$\rightarrow$从原根角度证明充要性：原根指数为偶$\iff a^{(p-1)/2}=1\iff a$是二次剩余

#### 🧭 导航路径

* **步行（L1-L2）** → 对标

1. 用欧拉判别法判断$2$是否为模$7$的二次剩余。

* 解答提示：$2^{(7-1)/2}=2^3=8\equiv1\pmod7$。结果为$1$，故$2$是模$7$的二次剩余。验证：$3^2=9\equiv2\checkmark$。答案：是二次剩余。

2. 判断$5$是否为模$11$的二次剩余。

* 解答提示：$5^{(11-1)/2}=5^5=3125$。$5^2=25\equiv3$，$5^4\equiv3^2=9$，$5^5\equiv5^4\times5\equiv9\times5=45\equiv1\pmod{11}$。结果为$1$，故$5$是模$11$的二次剩余。验证：$4^2=16\equiv5\checkmark$。答案：是。

3. 验证：若$a$是模$p$二次剩余，则$a^{(p-1)/2}\equiv1\pmod p$。

* 解答提示：设$a\equiv x^2$（$x$为整数，$\gcd(x,p)=1$）。则$a^{(p-1)/2}\equiv(x^2)^{(p-1)/2}=x^{p-1}$。由费马小定理$x^{p-1}\equiv1\pmod p$，故$a^{(p-1)/2}\equiv1$。证毕。
* **刚性达标阈值**：基础概念通关，闭卷正确率$\ge90%$
* **骑车（L3-L4）** → 对标

1. 用欧拉判别法求所有质数$p$使得$x^2\equiv-1\pmod p$有解。

* 解答提示：即$(-1)^{(p-1)/2}\equiv1\pmod p$，即$(p-1)/2$为偶数，即$p\equiv1\pmod4$。（$p=2$时直接验证$1^2\equiv-1\pmod2$也成立）。答案：$p=2$或$p\equiv1\pmod4$。

> 进一步引导：这个步骤的关键在于区分干扰信息和关键信息——题目中看似复杂的条件往往只有少数几个与分类判定直接相关，学会筛选信息本身就是重要的数学素养。

2. 证明：若$p\equiv1\pmod4$，则$-1$是模$p$的二次剩余。

* 解答提示：若$p\equiv1\pmod4$，设$p=4k+1$。则$(-1)^{(p-1)/2}=(-1)^{2k}=1$。由欧拉判别法得$-1$是二次剩余。该结论也等价于存在$x$使$x^2+1$被$p$整除。

> 深度解析：这里运用的实际上是反证法的思想雏形——通过分析奇偶性矛盾来证明某些情形不可能发生。不变量思想与反证法结合，是竞赛中最强大的组合工具之一。

> 深度解析：这里运用的实际上是反证法的思想雏形——通过分析奇偶性矛盾来证明某些情形不可能发生。不变量思想与反证法结合，是竞赛中最强大的组合工具之一，也是数学证明的经典范式。

3. 利用欧拉判别法证明：两个二次非剩余之积是二次剩余。

* 解答提示：设$a,b$都是二次非剩余，则$a^{(p-1)/2}\equiv-1$，$b^{(p-1)/2}\equiv-1$。于是$(ab)^{(p-1)/2}=a^{(p-1)/2}b^{(p-1)/2}\equiv(-1)\times(-1)=1$。由欧拉判别法$ab$是二次剩余。证毕。

> 思维延伸：将这个问题稍作变换——如果把条件中的某条规则改一下，结论是否还成立？这种改变条件观察变化的思维训练，有助于真正理解规则的本质。

> 进一步引导：这个步骤的关键在于区分干扰信息和关键信息——题目中看似复杂的条件往往只有少数几个与分类判定直接相关，学会筛选信息本身就是重要的数学素养。养成先筛选再判断的习惯，能大幅提升解题速度和准确性。

* **刚性达标阈值**：进阶例题演练，正确率$\ge85%$
* **开车（L5-L6）** → 对标

1. 证明欧拉判别法（利用原根）。

* 解答提示：设$g$为模$p$原根，$a\equiv g^k$。则$a^{(p-1)/2}\equiv g^{k(p-1)/2}$。$g$的阶为$p-1$，故$g^{k(p-1)/2}=1\iff(p-1)\mid k(p-1)/2\iff2\mid k$。而$k$为偶$\iff a=g^k=(g^{k/2})^2$是二次剩余。故$a^{(p-1)/2}=1\iff a$是二次剩余。$-1$的情形类似。证毕。

2. 求$2^{(p-1)/2}\bmod p$与勒让德符号$\left(\frac{2}{p}\right)$的关系。

* 解答提示：需要证明$\left(\frac{2}{p}\right)=(-1)^{(p^2-1)/8}$。证明可用高斯引理：在$1,2,\dots,(p-1)/2$中，大于$p/2$的$2k\bmod p$的个数决定符号。经计算得当$p\equiv\pm1\pmod8$时结果为$1$，$p\equiv\pm3\pmod8$时结果为$-1$。用公式表达即$(-1)^{(p^2-1)/8}$。

3. 利用欧拉判别法计算$\left(\frac{3}{p}\right)$并引出二次互反律。

* 解答提示：$\left(\frac{3}{p}\right)\equiv3^{(p-1)/2}\pmod p$。将$3^{(p-1)/2}$的计算与$p\bmod12$关联：$p\equiv\pm1\pmod{12}$时$3^{(p-1)/2}\equiv1$，$p\equiv\pm5\pmod{12}$时$\equiv-1$。这正是二次互反律的特殊情形：$\left(\frac{3}{p}\right)=\left(\frac{p}{3}\right)$当$p\equiv1\pmod4$，$\left(\frac{3}{p}\right)=-\left(\frac{p}{3}\right)$当$p\equiv3\pmod4$。

> 思维延伸：将这个问题稍作变换——如果把条件中的某条规则改一下，结论是否还成立？这种改变条件观察变化的思维训练，有助于真正理解规则的本质而非机械套用，是深度学习的标志性方法。