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

# 一、模块层

* **知识点编号**：B01-M02-S04-U01
* **所属模块**：B01 → M02 → S04

## 纵向关联

* 上接：
  * 无
* 下启：
  * [欧拉定理降幂题根](/root/B01-数论基础/M02-同余理论/S04/B01-M02-S04-U03)
  * [φ(n)积性应用题根](/root/B01-数论基础/M02-同余理论/S04/B01-M02-S04-U02)

## 知识关联

### 横向关联

* 前置基础：
  * [枚举法求lcm题根](/root/B01-数论基础/M01-整除与质数/S04/B01-M01-S04-U01)
  * [整除的可乘性题根](/root/B01-数论基础/M01-整除与质数/S05/B01-M01-S05-U03)
* 同位衔接：
  * `有理根定理题根`
  * `整除性归纳题根`
  * [定理条件判断题根](/root/B01-数论基础/M03-不定方程/S04/B01-M03-S04-U01)
* 后续延伸：
  * [τ(n)计算题根](/root/B01-数论基础/M04-数论函数与进阶技巧/S01/B01-M04-S01-U01)
  * [模分析题根](/root/B01-数论基础/M03-不定方程/S06/B01-M03-S06-U02)
  * [同余式组解的结构题根](/root/B01-数论基础/M03-不定方程/S04/B01-M03-S04-U05)
  * [μ(n)定义与性质题根](/root/B01-数论基础/M04-数论函数与进阶技巧/S01/B01-M04-S01-U03)
  * [非互质模化简题根](/root/B01-数论基础/M03-不定方程/S04/B01-M03-S04-U03)
  * `数列与同余题根`
  * [数论组合计数题根](/root/B01-数论基础/M04-数论函数与进阶技巧/S03/B01-M04-S03-U01)
  * `数论综合题根`

# 二、本源层

* **三锚**：
* **What（是什么）**：同余与模结构——欧拉函数 $\varphi(n)$ 计算不超过 $n$ 且与 $n$ 互质的正整数个数，其核心是在模 $n$ 的剩余系中筛选出与 $n$ 互质的剩余类。
* **Why（为什么）**：枚举思想——$\varphi(n)$ 的定义是“逐一枚举并筛选”，而公式 $\varphi(n)=n\prod(1-1/p)$ 将枚举过程压缩为乘积计算。
* **How（怎么做）**：整体与部分——先用质因数分解将 $n$ 拆为质数幂的乘积，再用积性和质数幂特例分别计算，最后合并。
* **本源**：欧拉函数 $\varphi(n)$ 是互质计数的精确数学工具——$\varphi(n)=n\prod\_{p\mid n}(1-1/p)$ 将容斥原理压缩为乘积形式。从 $n$ 中扣除各质因子倍数的比例，剩余的就是与 $n$ 互质的整数比例。这一公式是数论中第一个以封闭乘积形式出现的计数函数，其简洁性掩盖了背后深刻的分类计数思想：质因数分解后将筛选过程乘积化。
* **原点**：
* **约 1760 年**：欧拉研究等分圆周问题时引入 $\varphi$ 函数，从几何问题中发现互质计数的数学意义。
* **1763 年**：欧拉在欧拉定理中系统阐述 $\varphi(n)$ 定义及计算公式，首次将 $\varphi$ 与模幂周期联系起来。
* **1801 年**：高斯在《算术研究》中大量使用 $\varphi$ 函数表述数论结果，包括 $\varphi$ 的积性证明和和函数性质 $\sum\_{d\mid n}\varphi(d)=n$。
* **1830 年**：勒让德将 $\varphi(n)$ 纳入标准数论教科书体系，使之成为数论教学的基本函数。
* **1837 年**：狄利克雷引入狄利克雷卷积，将 $\varphi$ 函数纳入积性函数的一般理论框架。
* **现代**：$\varphi$ 函数成为可乘函数原型，在 RSA 加密算法、初等数论教学和解析数论中持续发挥核心作用。
* **道法**：
* **首锚·同余与模结构**：要解决 $\varphi(n)$ 公式计算问题，关键是先对 $n$ 做完整质因数分解，再套用乘积公式 $n\prod(1-1/p)$ 逐项化简——质因子“筛”掉不互质的比例，剩余就是互质个数在模结构下的精确值。
* **次锚·枚举思想**：题目没写但必须用到的是质因子不可遗漏也不可重复——漏一个因子结果全偏；分类时注意质因子 $p_i$ 与质数幂 $p_i^{a_i}$ 的区别，后者只需取一次 $p_i$ 而非重复乘。
* **三锚·整体与部分**：方法一是直接套 $\varphi(n)=n\prod(1-1/p)$，适合标准分解已知的情形；方法二是拆成质数幂后用 $\varphi(p^k)=p^k-p^{k-1}$ 分别计算再相乘，适合分步验算和纠错。
* **解题三问**：
* 问：这道题已知 $n$ 的质因数吗？答：若未知，先做完整质因数分解；分解的完整性是首要保证。
* 问：我是否把每个不同质因子都乘进去了一次？答：乘积中的 $p$ 取遍 $n$ 的所有不同质因子，指数信息已包含在 $n$ 这一系数中，不能再单独乘一次。
* 问：算完后能用特例快速验算吗？答：质数应得 $\varphi(p)=p-1$，质数幂应得 $\varphi(p^k)=p^k-p^{k-1}$。
* **关键心法**：先拆质因子、再套乘积式——拆全不同质因子是关键一步，错一个全盘皆输；比对质数特例可快速纠偏。拆因→套式→验算，三步闭环稳拿 $\varphi$ 值。
* **终极一句话**：$\varphi(n)=n\prod\_{p\mid n}(1-1/p)$——质因数分解将互质计数从逐一枚举降维为乘积计算，分解一道互质立得。理解这一公式的本质在于看透“筛法代数化”：每个质因子 $p$ 对应比例 $(1-1/p)$，所有比例的乘积恰好描述“全部未被筛掉的数所占比例”。这一乘积形式是容斥原理的终极压缩形态，让原本需要集合运算的计数过程简化为纯代数计算。
* **数学思想进化轴**：欧拉（约 1760 年）研究等分圆周问题时引入 $\varphi$ 函数 → 欧拉（1763 年）在欧拉定理中系统阐述定义与公式 → 高斯（1801 年）在《算术研究》中大量使用 $\varphi$ 函数 → 勒让德（1830 年）纳入标准教科书体系 → 狄利克雷（1837 年）引入狄利克雷卷积纳入积性函数理论框架 → 现代数论中 $\varphi$ 函数成为可乘函数原型，在 RSA 加密算法、初等数论教学和解析数论中持续发挥核心作用。

# 三、知识点层

* **知识点编号**：B01-M02-S04-U01
* **名称**：φ(n)公式计算题根
* **标准定义**：
* 欧拉函数 $\varphi(n)$：对于正整数 $n$，$\varphi(n)$ 定义为不超过 $n$ 且与 $n$ 互质的正整数个数。特别地，$\varphi(1)=1$。$\varphi(n)$ 的核心特性是其计算只依赖于 $n$ 的质因子集合而非质因子的具体指数——指数信息仅通过 $n$ 本身带入公式的系数部分。
* 计算通式：若 $n$ 的标准质因数分解为 $n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$，则
  $$
  \varphi(n)=n\prod\_{i=1}^k\left(1-\frac1{p_i}\right).
  $$
  此公式由容斥原理推导而来，将“筛除非互质数”的复杂过程压缩为简洁的乘积运算。推导线索：从 $n$ 中减去所有 $p_1$ 倍数的个数 $n/p_1$，减去所有 $p_2$ 倍数的个数 $n/p_2$……加回同时是 $p_1$ 和 $p_2$ 倍数的个数 $n/(p_1p_2)$，最终整理得
  $$
  \varphi(n)=n-\sum\frac{n}{p_i}+\sum\frac{n}{p_ip_j}-\cdots=n\prod\left(1-\frac1{p_i}\right).
  $$
* 等价理解（群论视角）：$\varphi(n)$ 等于模 $n$ 的单位群 $\mathbb{Z}\_n^\times$ 的阶，即模 $n$ 下所有可逆剩余类的个数。例如 $\varphi(8)=4$ 对应 $\mathbb{Z}\_8^\times={1,3,5,7}$。
* 关键提醒：公式中的 $p_i$ 取遍 $n$ 的所有**不同**质因子，而非所有质数幂因子。例如 $n=12=2^2\times3$，不同质因子为 $2$ 和 $3$，故
  $$
  \varphi(12)=12\times\left(1-\frac12\right)\times\left(1-\frac13\right)=4.
  $$
  质因子指数 $a_i$ 仅通过因子 $n$ 体现，不单独出现在乘积因子中，这是初学者最容易出错的地方。
* **核心本质**：**欧拉函数计算公式的本质是容斥原理的乘法化封装——用质因子逐个剔除非互质数，最终以乘积形式给出与 $n$ 互质的数的精确计数结果。其数学表达 $\varphi(n)=n\prod\_{p\mid n}(1-1/p)$ 将基于集合运算的容斥过程转化为纯代数乘积，实现了从“逐一枚举筛选”到“分解后直接计算”的方法论飞跃。**
* **核心性质**：
* 性质一：**质数特例**——若 $p$ 为质数，则 $\varphi(p)=p-1$。因为所有小于 $p$ 的正整数都与 $p$ 互质，没有例外。**数学意义**：质数的 $\varphi$ 值就是“矮一”，是理解 $\varphi$ 函数最直观的切入点，也是验算的便捷工具。
* 性质二：**质数幂公式**——若 $p$ 为质数，则
  $$
  \varphi(p^k)=p^k-p^{k-1}=p^{k-1}(p-1).
  $$
  与 $p^k$ 不互质的数恰是 $p$ 的倍数：$p,2p,\dots,p^{k-1}\cdot p$，共 $p^{k-1}$ 个。**数学意义**：质数幂的 $\varphi$ 值可直接用幂次差计算，不需重复使用通式。
* 性质三：**积性**——若 $\gcd(m,n)=1$，则 $\varphi(mn)=\varphi(m)\varphi(n)$。这是欧拉函数最核心的运算性质，由中国剩余定理保证。**数学意义**：积性将大数 $\varphi$ 值的计算拆解为互质因子的乘积，大幅简化了合数的 $\varphi$ 计算。
* 性质四：**和函数**——$\sum\_{d\mid n}\varphi(d)=n$。所有正因数的 $\varphi$ 值之和等于 $n$ 本身。证明核心是按最大公因数将 $1$ 到 $n$ 分类。**数学意义**：揭示了 $\varphi$ 函数与整数结构的深层联系，是“部分和等于整体”的数论之美。
* **解题思路三段式**：
* ① **识别任务结构**：这个任务可以拆成三个部分——质因数分解、乘积套用、特例验算。
* ② **写出步骤框架**：第一步分解 $n$ 得全部不同质因子 $p_i$；第二步将每个 $p_i$ 代入 $(1-1/p_i)$ 与 $n$ 连乘；第三步用质数特例 $\varphi(p)=p-1$ 快速验算结果。
* ③ **标注关键步骤**：最关键的是第一步完整分解，因为漏一个质因子直接导致结果错误；而质因子重复列乘不影响最终值（$(1-1/p)$ 乘多次不变），因此“分解完整”比“分解正确”更具挑战性。
* **常见错误三段式**：
* ① **具体分析失误**：套公式时忘记 $\varphi(1)=1$ 的特殊规定，或计算质数 $p$ 的 $\varphi$ 值时误得 $\varphi(p)=p$ 而非 $p-1$。
* ② **分析能力原因**：停留在“背公式套公式”的机械层面，未从定义出发理解特例来源——$\varphi(p)=p-1$ 是因为所有小于 $p$ 的数都与 $p$ 互质这一简单事实。
* ③ **忽视的深层结构**：忽视 $\varphi$ 函数定义中“互质”条件对质数的特殊含义——质数的所有小于自身的正整数都与其互质，无例外，因此 $\varphi(p)=p-1$ 是最自然的特例验证工具。
* **方法策略三段式**：
* ① **问题结构分析**：这是一个“给出整数 $n$，计算与其互质的数的个数”的结构化计算问题，属于套公式即可解决的标准化任务。
* ② **分析策略与路径选择**：标准解是分解质因数后套用乘积公式直接计算；面对大数可先用积性将 $n$ 拆为互质因数的乘积再分别计算，降低单步计算复杂度。
* ③ **拆解框架与验证**：分解→套式→验算，三步框架。验算需利用质数特例 $\varphi(p)=p-1$ 和质数幂特例 $\varphi(p^k)=p^k-p^{k-1}$，确认结果是否为整数是基本初步验证。

# 四、教案版本

## 【专业版】

### 【基础层例题】

计算 $\varphi(12)$。

* **解题思路**：分解质因数 $12=2^2\times3$，套用公式 $\varphi(n)=n\prod(1-1/p)$ 直接计算。
* **标准解答**：$12=2^2\times3$。
  $$
  \varphi(12)=12\times\left(1-\frac12\right)\times\left(1-\frac13\right)
  \=12\times\frac12\times\frac23=4.
  $$
  验算：与 $12$ 互质的正整数为 $1,5,7,11$ 共 $4$ 个，结果正确。答案：$4$。

### 【易错变式题】

计算 $\varphi(1)$ 和 $\varphi(2)$，并说明 $\varphi(1)=1$ 的意义。

* **常见错误**：认为 $\varphi(1)=0$（因为 $1$ 与 $1$ 的最大公因数为 $1$，易误以为不互质），或认为 $\varphi(2)=2$（忘记 $2$ 本身不与 $2$ 互质）。
* **解题思路**：严格按定义——不超过 $n$ 且与 $n$ 互质的正整数个数。逐一枚举 $1$ 到 $n$，检查每个数是否与 $n$ 互质。
* **标准解答**：$\varphi(1)=1$（$1$ 与 $1$ 互质，定义规定 $\varphi(1)=1$）；$\varphi(2)=2\times(1-1/2)=1$（仅有 $1$ 与 $2$ 互质）。$\varphi(1)=1$ 是数学规定，保证了 $\sum\_{d\mid n}\varphi(d)=n$ 在 $n=1$ 时成立，也使积性在平凡情形下一致。答案：$\varphi(1)=1$，$\varphi(2)=1$。

### 【高阶例题】

求所有满足 $\varphi(n)=6$ 的正整数 $n$。

* **方法策略**：分质数和合数讨论。若 $n$ 为质数 $p$，则 $\varphi(p)=p-1=6$；若 $n$ 为合数，利用 $\varphi$ 公式和积性在较小范围内搜索。
* **标准解答**：
  ① **质数解**：若 $n=p$ 为质数，则 $\varphi(p)=p-1=6\Rightarrow p=7$，故 $n=7$。
  ② **合数解**：设 $n=2^a m$（$m$ 为奇数）。
  * 若 $m=1$，则 $n=2^a$，$\varphi(2^a)=2^{a-1}=6$，无整数解。
  * 若 $m=3$，则 $\varphi(n)=\varphi(2^a)\cdot\varphi(3)=2^{a-1}\cdot2=2^a$，令 $2^a=6$ 无解。
  * 若 $m=9$，则 $\varphi(2^a\cdot9)=\varphi(2^a)\cdot6=2^{a-1}\cdot6$。当 $a=1$ 时得 $n=18$，$\varphi(18)=\varphi(2)\cdot\varphi(9)=1\times6=6$。
  * 若 $m=7$，则 $\varphi(n)=\varphi(2^a)\cdot6$。当 $a=1$ 时得 $n=14$，$\varphi(14)=1\times6=6$。
  * 若 $m=3\times7=21$，则 $\varphi(n)=\varphi(2^a)\cdot2\times6=12\varphi(2^a)\ge12>6$，无解。
    故 $n=9,14,18$。
    综上，$n\in{7,9,14,18}$。
    验证：$\varphi(7)=6$，$\varphi(9)=6$，$\varphi(14)=6$，$\varphi(18)=6$，全部成立。

## 【药典版】

### 定位：互质计数的“万能公式”

#### 🌱 药材本体

* **第一味药——质因数分解法**：将 $n$ 分解为标准质因数乘积 $n=p_1^{a_1}\cdots p_k^{a_k}$。这是计算 $\varphi(n)$ 的第一步，分解的完整性和正确性直接影响后续计算——遗漏质因子将导致结果错误。
* **第二味药——乘积公式**：$\varphi(n)=n\prod(1-1/p_i)$。将 $n$ 乘以每个质因子对应的 $(1-1/p_i)$，从总数中逐次扣除不互质的比例，最终得到互质数的精确个数。
* **第三味药——特例速算法**：$\varphi(p)=p-1$，$\varphi(p^k)=p^k-p^{k-1}$。这些特例是公式的直接推论，也是快速验算的工具。
* **第四味药——积性简化法**：利用 $\varphi(mn)=\varphi(m)\varphi(n)$（$\gcd(m,n)=1$）将大数拆解为互质因数分别计算。
* **药材核心药性**：“分解质因数，套乘积公式，$\varphi$ 值立现”。

#### 🛠️ 功能主治

* 主治「不知如何计算互质数的个数」——面对大整数不知如何求 $\varphi(n)$，只能逐一枚举。
* 解决「不理解 $\varphi(n)$ 公式的容斥本质」——只会死记硬背公式不会灵活运用特例。
* 根治「不会将数论函数计算与质因数分解联系起来」——两者本是同一问题的不同侧面。
* 打通「从 $\varphi(n)$ 公式到数论函数一般计算方法」的思维通道——所有可乘性数论函数都遵循类似的计算模式。

#### 🧪 核心药方

1、公式套用方——先分解质因数，再代入 $\varphi(n)=n\prod(1-1/p_i)$ 直接计算，适合初学阶段建立基本计算能力。适配基础表达阶。
2、特例速算方——对质数直接用 $\varphi(p)=p-1$，对质数幂用 $\varphi(p^k)=p^k-p^{k-1}$ 快速求解，不需展开通式。适配进阶表达阶。
3、方程求解方——已知 $\varphi(n)$ 的值反求 $n$，需分质数解和合数解两种情况讨论，结合 $\varphi$ 值的单调性和质因数分解缩小搜索范围。适配高阶表达阶。

#### 🌌 药理

**分解见质，乘积计数。**

欧拉函数公式的诞生是数论走上独立学科之路的重要一步。欧拉在 18 世纪中叶研究等比数列的周期问题时，敏锐地发现“与 $n$ 互质的数的个数”这一量具有深刻的数学意义。他最初并非从容斥原理出发，而是通过具体数值归纳得出公式的雏形——对 $n=1$ 到 $30$ 逐一计算 $\varphi(n)$，发现其值总可以写成 $n$ 乘以各质因子 $(1-1/p)$ 的形式。数论史家认为，$\varphi$ 函数的引入标志着数论从零散命题向系统理论的转折：这是第一个以简洁封闭形式出现的数论计数函数。$\varphi(n)$ 公式背后的数学直觉极其朴素——在 $1$ 到 $n$ 中，去掉所有 $p_1$ 的倍数、$p_2$ 的倍数……加回重复扣除的部分——但欧拉的天才之处在于将这一过程压缩为乘积形式，使得计算复杂度与质因子个数呈线性关系而非与 $n$ 的大小相关。更深一层，$\varphi$ 函数是可乘函数（积性函数）的原型——狄利克雷卷积、默比乌斯反演等高级数论工具都以 $\varphi$ 函数为重要例证。理解 $\varphi(n)$ 公式，就是握住数论函数世界的一把钥匙。

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

* **基础表达**：对标 L2.2-L3.1——会分解质因数、会套公式计算 $\varphi(n)$，能处理 $100$ 以内的数。教学重点是设计“分解—套式—验算”三步闭环的识别型练习，达成基础概念通关正确率≥90%。
* **进阶表达**：对标 L3.1-L3.2——懂特例速算（质数、质数幂），会用积性简化大数的 $\varphi$ 计算。教学重点是设计含积性分解的综合型练习，达成进阶变式题正确率≥85%。
* **高阶表达**：对标 L3.2-L4.2——能解 $\varphi(n)$ 的反问题（已知 $\varphi(n)$ 求 $n$），能利用 $\varphi$ 函数证明简单数论结论。教学重点是设计反问题与和函数性质的变式练习，达成高阶综合运用正确率≥80%。
* **顶阶表达**：对标 L4.2→L5.1 过渡——能讲 $\varphi$ 函数在一般数论函数理论中的位置，能与狄利克雷卷积衔接。

#### 🗣️ 一句话封神

**$\varphi(n)=n\prod\_{p\mid n}(1-1/p)$——分解一道，互质立得。**

#### 🩺 一眼诊断

* 分解卡顿型：面对大整数不知如何分解质因数。**处方**：对标 L2.2-L3.1——强化质因数分解训练，从 $100$ 以内数开始逐步提升，掌握试除法和平方根法。
* 公式套用模糊型：知道 $\varphi(n)=n\prod(1-1/p)$ 但不知 $p$ 取哪些。**处方**：对标 L3.1-L3.2——抓住“$p$ 是 $n$ 的所有不同质因子”，强调质因子不可重复也不可遗漏。
* 特例混淆型：混淆 $\varphi(p)=p-1$ 与 $\varphi(p^k)=p^k-p^{k-1}$ 的适用场景。**处方**：对标 L3.2-L4.2——明确区分：单个质数用 $p-1$，质数的幂用 $p^k-p^{k-1}$。
* 积性断裂型：不知 $\varphi$ 可分解为互质因数的乘积。**处方**：对标 L3.2-L4.2——强调 $\gcd(m,n)=1$ 是积性的前提，结合中国剩余定理讲解积性的深层原因。

#### 🧭 导航路径

* **步行（L1-L2 入门基础）**
* 必练例题：

1. 计算 $\varphi(20)$、$\varphi(36)$、$\varphi(100)$。
2. 求 $\varphi(2^k)$ 的公式。
3. 求 $\varphi(1)$ 到 $\varphi(10)$ 的值。

* 解答提示：

1. $\varphi(20)=20\times(1-1/2)\times(1-1/5)=20\times1/2\times4/5=8$；$\varphi(36)=36\times(1-1/2)\times(1-1/3)=36\times1/2\times2/3=12$；$\varphi(100)=100\times(1-1/2)\times(1-1/5)=100\times1/2\times4/5=40$。验证：$20$ 的互质数有 $1,3,7,9,11,13,17,19$ 共 $8$ 个。
2. $2^k$ 的质因子只有 $2$，由公式 $\varphi(2^k)=2^k\times(1-1/2)=2^{k-1}$。验证：$\varphi(2)=1$，$\varphi(4)=2$，$\varphi(8)=4$，$\varphi(16)=8$，符合 $\varphi(2^k)=2^{k-1}$。
3. $\varphi(1)=1$，$\varphi(2)=1$，$\varphi(3)=2$，$\varphi(4)=2$，$\varphi(5)=4$，$\varphi(6)=2$，$\varphi(7)=6$，$\varphi(8)=4$，$\varphi(9)=6$，$\varphi(10)=4$。注意 $\varphi(2)=1$ 意味着与 $2$ 互质的数即为所有奇数。

* 刚性达标阈值：基础概念通关，闭卷正确率≥90%

* **骑车（L3-L4 进阶应用）**

* 必练例题：

1. 求满足 $\varphi(n)=8$ 的所有 $n$。
2. 证明：若 $n>2$，则 $\varphi(n)$ 为偶数。
3. 利用积性求 $\varphi(2024)$。

* 解答提示：

1. 质数解：$p-1=8\Rightarrow p=9$ 非质数，故无质数解。合数解：$n=15=3\times5$，$\varphi(15)=2\times4=8$；$n=16=2^4$，$\varphi(16)=8$；$n=20=2^2\times5$，$\varphi(20)=8$；$n=24=2^3\times3$，$\varphi(24)=4\times2=8$；$n=30=2\times3\times5$，$\varphi(30)=1\times2\times4=8$。故 $n=15,16,20,24,30$。
2. 若 $n$ 有奇质因子 $p$，则 $\varphi(n)$ 含因子 $p-1$ 为偶数。若 $n=2^k$（$k\ge2$），则 $\varphi(2^k)=2^{k-1}$ 为偶数。$n>2$ 必属于上述情形之一。更一般地，$\varphi(n)$ 为奇数当且仅当 $n=1,2$。
3. $2024=8\times253=2^3\times11\times23$。$\varphi(2^3)=4$，$\varphi(11)=10$，$\varphi(23)=22$。由积性 $\varphi(2024)=4\times10\times22=880$。验证：$2024\times(1-1/2)\times(1-1/11)\times(1-1/23)=2024\times1/2\times10/11\times22/23=880$。答案：$880$。

* 刚性达标阈值：进阶例题演练，正确率≥85%

* **开车（L5-L6 竞赛证明·邀请制专属）**

* 必练例题：

1. 证明：$\sum\_{d\mid n}\varphi(d)=n$。
2. 求所有 $n$ 使得 $\varphi(n)=n/2$。
3. 求所有满足 $\varphi(n)=12$ 的正整数 $n$。

* 解答提示：

1. 将 $1$ 到 $n$ 的整数按与 $n$ 的最大公因数分类。对每个 $d\mid n$，集合 ${k:1\le k\le n,\gcd(k,n)=d}$ 的大小恰好等于 $\varphi(n/d)$。所有 $d$ 对应的集合构成 $1$ 到 $n$ 的一个划分，故各集合元素个数之和为 $n$，即 $\sum\_{d\mid n}\varphi(d)=n$。证毕。
2. 由 $\varphi(n)=n\prod(1-1/p_i)=n/2$ 得 $\prod(1-1/p_i)=1/2$。若 $n$ 的质因子只有 $2$，则 $(1-1/2)=1/2$ 恰好满足。若包含其他奇质因子 $p$，则 $(1-1/p)\le2/3$，乘积 $<1/2$。故 $n=2^k$（$k\ge1$）。验证：$\varphi(2^k)=2^{k-1}=2^k/2$。答案：$n=2^k$（$k\ge1$）。
3. 质数解：$p-1=12\Rightarrow p=13$，故 $n=13$。合数解：$n=21=3\times7$，$\varphi=2\times6=12$；$n=26=2\times13$，$\varphi=1\times12=12$；$n=28=4\times7$，$\varphi=2\times6=12$；$n=36=4\times9$，$\varphi(36)=12$；$n=42=2\times3\times7$，$\varphi=1\times2\times6=12$。故 $n=13,21,26,28,36,42$。

* 刚性达标阈值：竞赛真题演练，正确率≥80%

* **验收方式**：家长确认签字制（家长检查学生是否能正确分解质因数、套用公式、利用特例验算，并理解 $\varphi(1)=1$ 的特殊规定）。