Appearance
数论题目集
概述
本题目集涵盖整除同余、不定方程、数论函数与二次剩余四大数论主题，共 27 题，按基础→进阶→竞赛三级难度编排。
一、整除与同余基础
题1 [难度：基础]
题目：证明 $7\mid (3^{2n+1}+2^{n+2})$对所有正整数$n$ 成立。
分析：数学归纳法或模 $7$ 同余计算。
解答： 归纳法：当 $n=1$ 时，$3^3+2^3=27+8=35=7\times5$，成立。
设 $n=k$成立，即$3^{2k+1}+2^{k+2}=7m$。
$n=k+1$ 时： $$ \begin{aligned} 3^{2(k+1)+1}+2^{(k+1)+2} &= 3^{2k+3}+2^{k+3} = 9\cdot3^{2k+1}+2\cdot2^{k+2} \newline &= 9(7m-2^{k+2})+2\cdot2^{k+2} = 63m-9\cdot2^{k+2}+2\cdot2^{k+2} \newline &= 63m-7\cdot2^{k+2} = 7(9m-2^{k+2}). \end{aligned} $$ 故 $7\mid(3^{2n+1}+2^{n+2})$。证毕。
题2 [难度：基础]
题目：求 $(2^{2024}-1)$除以$7$ 的余数。
分析：利用模 $7$下$2^3\equiv 1$。
解答： $2^3=8\equiv 1\pmod{7}$。$2024=3\times674+2$。
$$ 2^{2024}=2^{3\times674+2}=(2^3)^{674}\cdot2^2\equiv 1^{674}\cdot4=4\pmod{7}. $$ 故 $2^{2024}-1\equiv 3\pmod{7}$，余数为 $3$。
题3 [难度：基础]
题目：用裴蜀定理求 $(56,72)$的最大公约数，并求整数$x,y$使得$56x+72y=(56,72)$。
分析：辗转相除法求最大公约数，回代求贝祖系数。
解答： 辗转相除： $$ 72=56\times1+16,\quad 56=16\times3+8,\quad 16=8\times2+0. $$ 故 $(56,72)=8$。
回代： $$ \begin{aligned} 8 &= 56-16\times3 \newline &= 56-(72-56\times1)\times3 \newline &= 56-72\times3+56\times3 \newline &= 56\times4+72\times(-3). \end{aligned} $$ 故 $x=4,\ y=-3$。
题4 [难度：进阶]
题目：证明不定方程 $7x+11y=100$ 有无穷多组整数解，并求所有正整数解。
分析：裴蜀定理判定有解，通解 $x=x_0+11t,\ y=y_0-7t$。
解答： $(7,11)=1\mid100$，有解。先求特解。
$11=7\times1+4$，$7=4\times1+3$，$4=3\times1+1$。
回代：$1=4-3=4-(7-4)=2\cdot4-7=2(11-7)-7=2\cdot11-3\cdot7$。
通解：$\begin{cases}x=100\cdot(-3)+11t=-300+11t \newline y=100\cdot2-7t=200-7t\end{cases}$
求正整数解：$x>0\Rightarrow-300+11t>0\Rightarrow t>27.27\Rightarrow t\geq28$。
$y>0\Rightarrow200-7t>0\Rightarrow t<28.57\Rightarrow t\leq28$。
故 $t=28$，唯一正整数解 $x=8,\ y=4$。验证：$7\times8+11\times4=56+44=100$。
题5 [难度：进阶]
题目（中国剩余定理）：求最小的正整数 $x$满足$x\equiv2\pmod{3},\ x\equiv3\pmod{5},\ x\equiv2\pmod{7}$。
分析：标准 CRT 问题。
解答： $M=3\times5\times7=105$。 $M_1=35,\ M_1^{-1}\pmod{3}$：$35\equiv2\pmod{3}$，$2^{-1}\equiv2\pmod{3}$（$2\times2=4\equiv1$）。 $M_2=21,\ M_2^{-1}\pmod{5}$：$21\equiv1\pmod{5}$，$1^{-1}\equiv1$。 $M_3=15,\ M_3^{-1}\pmod{7}$：$15\equiv1\pmod{7}$，$1^{-1}\equiv1$。
$$ \begin{aligned} x &\equiv 2\cdot35\cdot2+3\cdot21\cdot1+2\cdot15\cdot1 \newline &= 140+63+30=233\pmod{105}. \end{aligned} $$ $233=105\times2+23$，故最小正整数解为 $x=23$。
验证：$23\equiv2\pmod{3},\ 23\equiv3\pmod{5},\ 23\equiv2\pmod{7}$。
题6 [难度：竞赛]
题目：求所有正整数 $n$使得$n^2+1\mid n!$。
分析：涉及 Wilson 定理的变形，需分析 $n^2+1$ 的素因子。
解答： 若 $n^2+1\mid n!$，则 $n^2+1$的每个素因子$p$满足$p\leq n$。
又 $p\mid n^2+1$意味着$n^2\equiv-1\pmod{p}$，故 $p\equiv1\pmod{4}$。
若 $n\leq3$：$n=1$时$1^2+1=2$，$1!$不被$2$ 整除；$n=2$时$5\mid2!$？不；$n=3$时$10\mid6$？不。
$n=4$：$17\nmid24$。 $n=5$：$26=2\cdot13$，$5!=120$，$13\nmid120$。 $n=7$：$50=2\cdot5^2$，$7!=5040$，$25\nmid5040$。
实际上，由 Wilson 定理相关结果，只有有限的 $n$满足条件。通过分析$n^2+1$的最大素因子与$n$ 的关系，可知无解或仅有极少数解，需进一步精细分析。
二、费马小定理与欧拉定理
题7 [难度：基础]
题目：求 $3^{100}$除以$13$ 的余数。
分析：费马小定理 $a^{12}\equiv1\pmod{13}$（当 $13\nmid a$）。
解答： 由费马小定理 $3^{12}\equiv1\pmod{13}$。$100=12\times8+4$。
$$ 3^{100}=(3^{12})^8\cdot3^4\equiv 1^8\cdot81=81\pmod{13}. $$ $81=13\times6+3$，故余数为 $3$。
题8 [难度：进阶]
题目：求 $7^{7^{7}}$ 的个位数。
分析：求模 $10$ 的余数。$7^k\pmod{10}$ 的周期。
解答： $7^1\equiv7,\ 7^2\equiv9,\ 7^3\equiv3,\ 7^4\equiv1,\ 7^5\equiv7\pmod{10}$。周期为 $4$。
需计算 $7^7\pmod{4}$。$7\equiv3\pmod{4}$，$3\equiv-1\pmod{4}$，$7^7\equiv(-1)^7\equiv-1\equiv3\pmod{4}$。
故 $7^7=4k+3$（$k$ 为某个整数）， $7^{7^7}=7^{4k+3}\equiv7^3\equiv3\pmod{10}$。
答案为 $3$。
题9 [难度：进阶]
题目：利用费马小定理求 $2^{100}\pmod{101}$的值，并用此计算$2^{2024}$除以$101$ 的余数。
分析：$101$ 是素数，$2^{100}\equiv1\pmod{101}$（费马小定理）。
解答： 费马小定理：$2^{100}\equiv1\pmod{101}$。
$2024=100\times20+24$。
$$ 2^{2024}=(2^{100})^{20}\cdot2^{24}\equiv 2^{24}\pmod{101}. $$ 计算 $2^{24}\pmod{101}$： $2^{10}=1024\equiv 1024-1010=14\pmod{101}$。 $2^{20}\equiv14^2=196\equiv196-101=95\equiv-6\pmod{101}$。 $2^{24}=2^{20}\cdot2^4\equiv(-6)\cdot16=-96\equiv5\pmod{101}$。
故 $2^{2024}\equiv5\pmod{101}$。
题10 [难度：竞赛]
题目：求 $2^{2^{2024}}\pmod{5}$ 的值。
分析：$\varphi(5)=4$，用欧拉定理 $a^4\equiv1\pmod{5}$（$(a,5)=1$）。需先求 $2^{2024}\pmod{4}$。
解答： $2^{2024}\pmod{4}$：当 $2024\geq2$时$2^{2024}=4\cdot2^{2022}\equiv0\pmod{4}$。
由欧拉定理 $2^4\equiv1\pmod{5}$。$2^{2024}=4k$。
$2^{2^{2024}}=2^{4k}\equiv(2^4)^k\equiv1^k\equiv1\pmod{5}$。
答案为 $1$。
三、不定方程
题11 [难度：基础]
题目：求不定方程 $x^2-y^2=2024$ 的所有正整数解。
分析：因式分解 $(x-y)(x+y)=2024$。$x-y$和$x+y$ 同奇偶且均为正。
解答： $(x-y)(x+y)=2024=2^3\times11\times23$。
令 $u=x-y,\ v=x+y$，则 $uv=2024$，$u,v$ 同奇偶，$u<v$，且 $x=\dfrac{u+v}{2},\ y=\dfrac{v-u}{2}$ 为正整数。
$u,v$必须同奇偶，即$u,v$ 同为偶数（$u+v$和$v-u$ 为偶数）。$2024$ 是偶数，$u,v$ 必同为偶数。
设 $u=2a,\ v=2b$，则 $ab=506=2\times11\times23$。
$506$ 的因子：$1,2,11,22,23,46,253,506$。
对应 $(x,y)=(\frac{u+v}{2},\frac{v-u}{2})=(a+b,b-a)$：
| $a$ | $b$ | $x$ | $y$ |
|---|---|---|---|
| 1 | 506 | 507 | 505 |
| 2 | 253 | 255 | 251 |
| 11 | 46 | 57 | 35 |
| 22 | 23 | 45 | 1 |
四组解。
题12 [难度：进阶]
题目：求所有正整数解 $x^2+2y^2=3z^2$中满足$1\leq x,y,z\leq20$ 的解。
分析：模分析缩小范围，穷举验证。
解答： 模 $3$ 分析：$x^2+2y^2\equiv3z^2\equiv0\pmod{3}$。
在模 $3$下平方为$0$或$1$。$x^2+2y^2\equiv0\pmod{3}$。
枚举 $x^2,y^2\pmod{3}$：
- 若 $x^2\equiv0$，则 $2y^2\equiv0\pmod{3}\Rightarrow y^2\equiv0$。
- 若 $x^2\equiv1$，则 $1+2y^2\equiv0\Rightarrow2y^2\equiv2\Rightarrow y^2\equiv1$。
故 $x,y$同被$3$整除或同不被$3$ 整除。
令 $t=3z^2$，在 $x,y,z\leq20$ 范围内枚举：
$z=1$：$x^2+2y^2=3$，$(1,1,1)$ 是一解。 $z=2$：$x^2+2y^2=12$，$(2,2,2)$ 是一解。 $z=3$：$x^2+2y^2=27$，$(3,3,3)$、$(5,1,3)$ 是解。 $z=4$：$x^2+2y^2=48$，$(4,4,4)$、$(6,2,4)$…等。 $z=5$：$x^2+2y^2=75$，$(5,5,5)$…
共有多组解（比例解$(k,k,k)$及非比例解）。
题13 [难度：进阶]
题目：求不定方程 $x^2-3y^2=1$（Pell 方程）的最小正整数解及无穷多组解的构造方法。
分析：Pell 方程 $x^2-dy^2=1$，基本解 $(x_1,y_1)=(2,1)$，通解 $(x_1+y_1\sqrt{d})^n$。
解答： 最小正整数解：尝试 $y=1$，$x^2=4$，$x=2$。故基本解为 $(2,1)$。
验证：$2^2-3\cdot1^2=4-3=1$。
通解公式： $$ x_n+y_n\sqrt{3}=(2+\sqrt{3})^n,\quad n=1,2,3,\ldots $$
例如 $n=2$：$(2+\sqrt{3})^2=7+4\sqrt{3}$，解 $(7,4)$，$7^2-3\cdot4^2=49-48=1$。 $n=3$：$(2+\sqrt{3})^3=26+15\sqrt{3}$，解 $(26,15)$。
由此可生成无穷多组解。
题14 [难度：竞赛]
题目（无穷递降法）：证明不定方程 $x^4+y^4=z^2$ 无正整数解。
分析：费马的无穷递降法。假设存在最小解，构造更小的解导出矛盾。
解答： 假设存在正整数解，取 $z$最小的解$(x,y,z)$（$x,y>0$）。可设 $(x,y)=1$。
$(x^2)^2+(y^2)^2=z^2$，故 $(x^2,y^2,z)$是勾股数组。存在$m>n>0$，$(m,n)=1$，一奇一偶使： $$ \begin{cases} x^2=m^2-n^2 \newline y^2=2mn \newline z=m^2+n^2 \end{cases}\quad\text{或}\quad\begin{cases} x^2=2mn \newline y^2=m^2-n^2 \end{cases} $$ 分析第一种情况：$x^2+n^2=m^2$，$(x,n,m)$又是勾股数组，存在$u>v>0$ 使得…
反复降次可得 $x^4+y^4=z^2$ 有更小的正整数解，矛盾。
因此原方程无正整数解。
注
费马用此法证明了 $x^4+y^4=z^4$无正整数解，进而证明了费马大定理$n=4$ 的情况。
题15 [难度：基础]
题目：求不定方程 $3x+5y=1$在模$7$意义下的所有解$(x,y)$（$x,y\in\lbrace 0,1,2,3,4,5,6\rbrace $）。
分析：有限域上的线性方程，枚举或解同余式。
解答： $3x+5y\equiv1\pmod{7}$，即 $3x\equiv1-5y\pmod{7}$。
$\pmod{7}$下$3^{-1}\equiv5$（$3\times5=15\equiv1$）。
故 $x\equiv5(1-5y)\equiv5-25y\equiv5-4y\pmod{7}$（$25\equiv4$）。
枚举 $y=0,1,\ldots,6$：
| $y$ | $x\equiv5-4y\pmod{7}$ |
|---|---|
| 0 | 5 |
| 1 | 1 |
| 2 | 4（$5-8\equiv-3\equiv4$） |
| 3 | 0（$5-12\equiv-7\equiv0$） |
| 4 | 3（$5-16\equiv-11\equiv3$） |
| 5 | 6（$5-20\equiv-15\equiv6$） |
| 6 | 2（$5-24\equiv-19\equiv2$） |
共 7 组解。
四、欧拉定理与莫比乌斯反演
题16 [难度：基础]
题目：求 $\varphi(100)$和$\varphi(2024)$。
分析：欧拉函数公式 $\varphi(n)=n\prod_{p\mid n}\left(1-\frac{1}{p}\right)$。
解答： $\varphi(100)=\varphi(2^2\cdot5^2)=100\times\left(1-\dfrac{1}{2}\right)\times\left(1-\dfrac{1}{5}\right)=100\times\dfrac{1}{2}\times\dfrac{4}{5}=40$。
$2024=2^3\times11\times23$。 $\varphi(2024)=2024\times\dfrac{1}{2}\times\dfrac{10}{11}\times\dfrac{22}{23}=1012\times\dfrac{10}{11}\times\dfrac{22}{23}=920\times\dfrac{22}{23}=880$。
题17 [难度：进阶]
题目：求 $\displaystyle\sum_{d\mid n}\varphi(d)=n$的证明，并用此计算$\varphi(1)+\varphi(2)+\varphi(3)+\varphi(6)$。
分析：按分母分类 $1/n,2/n,\ldots,n/n$ 的最简分数计数。
解答： 证明：考虑分数集合 $\left\lbrace \dfrac{1}{n},\dfrac{2}{n},\ldots,\dfrac{n}{n}\right\rbrace $。将其约分为最简分数，分母为 $d$的最简分数恰好有$\varphi(d)$ 个。
例如 $n=6$： $\frac{1}{6},\frac{2}{6}=\frac{1}{3},\frac{3}{6}=\frac{1}{2},\frac{4}{6}=\frac{2}{3},\frac{5}{6},\frac{6}{6}=1$。
分母为 $1$：$1$ 个（$\frac{1}{1}$）；分母为 $2$：$\frac{1}{2}$（1个）；分母为 $3$：$\frac{1}{3},\frac{2}{3}$（2个）；分母为 $6$：$\frac{1}{6},\frac{5}{6}$（2个）。
总数 $n=6$。一般地 $\sum_{d\mid n}\varphi(d)=n$。
验证 $n=6$：$\varphi(1)+\varphi(2)+\varphi(3)+\varphi(6)=1+1+2+2=6$。
题18 [难度：进阶]
题目（莫比乌斯反演）：已知 $f(n)=\sum_{d\mid n}g(d)$，用莫比乌斯函数表示 $g(n)$。并求当 $f(n)=n$时$g(n)$ 的值。
分析：莫比乌斯反演公式 $g(n)=\sum_{d\mid n}\mu(d)f(n/d)$。
解答： 莫比乌斯反演公式： $$ g(n)=\sum_{d\mid n}\mu\negthinspace\left(\frac{n}{d}\right)f(d)=\sum_{d\mid n}\mu(d)f\negthinspace\left(\frac{n}{d}\right). $$
当 $f(n)=n$ 时： $$ g(n)=\sum_{d\mid n}\mu(d)\cdot\frac{n}{d}=n\sum_{d\mid n}\frac{\mu(d)}{d}=\varphi(n). $$ 这正是欧拉函数！故 $\varphi(n)=\sum_{d\mid n}\mu(d)\frac{n}{d}$。
题19 [难度：竞赛]
题目：求 $\displaystyle\sum_{k=1}^{n}\varphi(k)$的渐近公式（简要给结果），并计算$\displaystyle\sum_{k=1}^{100}\mu(k)$。
分析：$\sum_{k=1}^n\varphi(k)\sim\dfrac{3}{\pi^2}n^2$。默比乌斯函数求和可逐个计算。
解答： 渐近公式：$\displaystyle\sum_{k=1}^n\varphi(k)\sim\frac{3}{\pi^2}n^2+O(n\log n)$。
关于 $\displaystyle\sum_{k=1}^{100}\mu(k)$：采用筛法计算无平方因子的数。
$\mu(1)=1$。对不含有平方因子的数，$\mu=\pm1$ 取决于素因子个数的奇偶性。
关键性质：$\sum_{d\mid n}\mu(d)=[n=1]$（克罗内克δ）。
通过计算 $\sum_{k=1}^{100}\mu(k)$：有平方因子的数 $\mu=0$。$100$以内的平方因子数有$4,8,9,12,16,18,\ldots$
精确计算：$1\sim100$中有$39$个无平方因子数。其中偶数个素因子的有$20$ 个($\mu=1$)，奇数个素因子的有 $19$ 个($\mu=-1$)。
故 $\displaystyle\sum_{k=1}^{100}\mu(k)=20-19=1$。
五、二次剩余与原根
题20 [难度：基础]
题目：判断 $x^2\equiv2\pmod{7}$是否有解，并求$\left(\dfrac{2}{7}\right)$。
分析：勒让德符号定义：$\left(\dfrac{a}{p}\right)=1$表示$a$是模$p$ 的二次剩余。
解答： 枚举：$0^2\equiv0,\ 1^2\equiv1,\ 2^2\equiv4,\ 3^2\equiv2,\ 4^2\equiv2,\ 5^2\equiv4,\ 6^2\equiv1\pmod{7}$。
$2$ 出现了（$3^2\equiv2$），故 $\left(\dfrac{2}{7}\right)=1$，方程有解 $x\equiv3,4\pmod{7}$。
用公式：$\left(\dfrac{2}{p}\right)=(-1)^{(p^2-1)/8}$。$p=7$，$(7^2-1)/8=48/8=6$，$(-1)^6=1$。
题21 [难度：进阶]
题目：计算勒让德符号 $\left(\dfrac{3}{13}\right)$、$\left(\dfrac{5}{17}\right)$，并用二次互反律验证。
分析：二次互反律：$\left(\dfrac{p}{q}\right)\left(\dfrac{q}{p}\right)=(-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}$。
解答： (1) $\left(\dfrac{3}{13}\right)$：由互反律， $$ \left(\frac{3}{13}\right)\left(\frac{13}{3}\right)=(-1)^{\frac{3-1}{2}\cdot\frac{13-1}{2}}=(-1)^{1\cdot6}=1. $$ $\left(\dfrac{13}{3}\right)=\left(\dfrac{1}{3}\right)=1$，故 $\left(\dfrac{3}{13}\right)=1$。
(2) $\left(\dfrac{5}{17}\right)$： $$ \left(\frac{5}{17}\right)\left(\frac{17}{5}\right)=(-1)^{\frac{5-1}{2}\cdot\frac{17-1}{2}}=(-1)^{2\cdot8}=1. $$ $\left(\dfrac{17}{5}\right)=\left(\dfrac{2}{5}\right)=-1$（$(5^2-1)/8=3$，$(-1)^3=-1$）。故 $\left(\dfrac{5}{17}\right)=-1$。
题22 [难度：竞赛]
题目：求模 $17$的原根，并求$3$模$17$ 的阶。
分析：原根是使阶等于 $\varphi(p)=p-1$ 的数。逐个检验阶。
解答： $\varphi(17)=16$。检验 $g=3$ 的阶：
$3^1\equiv3,\ 3^2\equiv9,\ 3^4\equiv9^2=81\equiv13\pmod{17}$（$81-68=13$）。 $3^8\equiv13^2=169\equiv169-170=-1\equiv16\pmod{17}$。 $3^{16}\equiv(3^8)^2\equiv(-1)^2=1\pmod{17}$。
$3^8\equiv-1\neq1$，$3^4\equiv13\neq1$，$3^2\equiv9\neq1$，故 $3$的阶为$16$。
因此 $3$是模$17$ 的原根。
题23 [难度：进阶]
题目：解同余式 $x^2\equiv-1\pmod{65}$。
分析：利用中国剩余定理分解 $65=5\times13$。$(x^2\equiv-1\pmod{p})$有解当且仅当$p\equiv1\pmod{4}$。
解答： $65=5\times13$。$5\equiv1\pmod{4}$，$13\equiv1\pmod{4}$，故两个模下都有解。
模 $5$：$x^2\equiv4\pmod{5}$，$x\equiv2,3\pmod{5}$。 模 $13$：$x^2\equiv12\pmod{13}$，由 $5^2=25\equiv12$，$8^2=64\equiv12$，故 $x\equiv5,8\pmod{13}$。
CRT 组合得 $4$组解模$65$。以下给出一组示例： 由 $x\equiv2\pmod{5}$和$x\equiv5\pmod{13}$： $M_1=13$，$13^{-1}\pmod{5}\equiv2$（$13\equiv3$，$3\times2=6\equiv1$）。 $M_2=5$，$5^{-1}\pmod{13}\equiv8$（$5\times8=40\equiv1$）。
$x\equiv2\cdot13\cdot2+5\cdot5\cdot8=52+200=252\equiv57\pmod{65}$。
四组解：$x\equiv8,18,47,57\pmod{65}$。
题24 [难度：基础]
题目：求 $\left(\dfrac{10}{23}\right)$ 并使用互反律化简。
分析：勒让德符号可分解，$\left(\frac{10}{23}\right)=\left(\frac{2}{23}\right)\left(\frac{5}{23}\right)$。
解答： $$ \left(\frac{10}{23}\right)=\left(\frac{2}{23}\right)\left(\frac{5}{23}\right). $$
$\left(\dfrac{2}{23}\right)$：$(23^2-1)/8=(529-1)/8=66$，$(-1)^{66}=1$。故 $\left(\dfrac{2}{23}\right)=1$。
$\left(\dfrac{5}{23}\right)$：互反律 $$ \left(\frac{5}{23}\right)=(-1)^{\frac{5-1}{2}\cdot\frac{23-1}{2}}\left(\frac{23}{5}\right)=(-1)^{2\cdot11}\left(\frac{3}{5}\right)=\left(\frac{3}{5}\right). $$ 枚举 $1^2\equiv1,2^2\equiv4,3^2\equiv4,4^2\equiv1\pmod{5}$。$3$ 不是二次剩余，$\left(\dfrac{3}{5}\right)=-1$。
故 $\left(\dfrac{10}{23}\right)=1\cdot(-1)=-1$。
题25 [难度：竞赛]
题目：证明当 $p$ 为奇素数时，$\displaystyle\sum_{a=1}^{p-1}\left(\frac{a}{p}\right)=0$。
分析：二次剩余和非剩余各占一半，勒让德符号之和为零。
解答： 模 $p$ 的简化剩余系中，$1^2,2^2,\ldots,\left(\frac{p-1}{2}\right)^2$ 恰好遍历所有二次剩余。
共有 $\dfrac{p-1}{2}$ 个二次剩余（$\left(\dfrac{a}{p}\right)=1$）和 $\dfrac{p-1}{2}$ 个非二次剩余（$\left(\dfrac{a}{p}\right)=-1$）。
因此 $\displaystyle\sum_{a=1}^{p-1}\left(\frac{a}{p}\right)=\frac{p-1}{2}\cdot1+\frac{p-1}{2}\cdot(-1)=0$。
题26 [难度：进阶]
题目：求 $\operatorname{ord}_{11}(2)$和$\operatorname{ord}_{13}(3)$。
分析：阶是满足 $a^d\equiv1\pmod{p}$的最小正整数$d$，且 $d\mid(p-1)$。
解答： (1) $p=11$，$\varphi(11)=10$，$d\mid10$，$d\in\lbrace 1,2,5,10\rbrace $。 $2^1=2\neq1$，$2^2=4\neq1$，$2^5=32\equiv10\neq1\pmod{11}$，$2^{10}\equiv1$。 故 $\operatorname{ord}_{11}(2)=10$，$2$ 是原根。
(2) $p=13$，$\varphi(13)=12$，$d\mid12$，$d\in\lbrace 1,2,3,4,6,12\rbrace $。 $3^1\neq1$，$3^2=9\neq1$，$3^3=27\equiv1\pmod{13}$。 故 $\operatorname{ord}_{13}(3)=3$。
题27 [难度：竞赛]
题目：设 $p$ 为素数，$a$模$p$的阶为$d$。若 $a^k\equiv1\pmod{p}$，证明 $d\mid k$。
分析：阶的定义和带余除法。
解答： 由带余除法 $k=qd+r$（$0\leq r<d$）。
$a^k\equiv a^{qd+r}\equiv(a^d)^q\cdot a^r\equiv1^q\cdot a^r\equiv a^r\pmod{p}$。
已知 $a^k\equiv1\pmod{p}$，故 $a^r\equiv1\pmod{p}$。
若 $r>0$，则 $r<d$且$a^r\equiv1$，与 $d$ 为最小性矛盾。
故 $r=0$，即 $d\mid k$。证毕。
六、Lucas 定理与 Kummer 定理（高难度）
题28 [难度：竞赛]
题目：求 $\binom{2n}{n}$中$2$的幂次$v_2\negthinspace\binom{2n}{n}$，并证明 $v_2\negthinspace\binom{2n}{n}$等于$n$在二进制下$1$的个数$s_2(n)$。
分析：Kummer 定理：$v_p\negthinspace\binom{2n}{n}$等于$n + n$在$p$ 进制下的进位次数。
解答： 由 Kummer 定理，$v_2\negthinspace\binom{2n}{n}$等于$n + n$ 在二进制下的进位次数。
$n + n$ 即左移一位（$\times 2$），但每位 $1$加自身时$1 + 1 = 10$，进位。具体地，设 $n = \sum_i b_i 2^i$（$b_i \in \lbrace 0, 1\rbrace $）。
逐位计算 $n + n$：
- 第 $i$ 位：$b_i + b_i + c_{i-1}$（$c_{i-1}$为前一位进位），写$b_i \oplus c_{i-1}$，进 $b_i \cdot c_{i-1}$? 不对，简化：因 $b_i \in \lbrace 0,1\rbrace $，$b_i + b_i = 2 b_i$，进位 $b_i$。
- 加上低位进位 $c_{i-1}$：实际第 $i$位和为$2b_i + c_{i-1}$，写 $(2b_i + c_{i-1}) \bmod 2 = c_{i-1}$（因 $2b_i$偶），进位$\lfloor(2b_i + c_{i-1})/2\rfloor = b_i + \lfloor c_{i-1}/2\rfloor$。
递推：每位 $b_i = 1$ 产生一次进位（$c_i = 1$ 传递到下一位），$b_i = 0$ 终止进位链。
总进位次数 = $\sum_i b_i = s_2(n)$。
故 $v_2\negthinspace\binom{2n}{n} = s_2(n)$。
验证
$n = 6 = 110_2$，$s_2(6) = 2$。$\binom{12}{6} = 924 = 4 \cdot 231 = 2^2 \cdot 231$，$v_2 = 2$ ✓
题29 [难度：TST]
题目（IMO 2017 P6 改编）：求所有正整数对 $(a, b)$使得$\dfrac{a^2 + b^2}{ab + 1}$ 是正整数且为完全平方数。
分析：经典 Vieta 跳跃问题。详见 不定方程与丢番图方程 例 10。
解答： 设 $k = \dfrac{a^2 + b^2}{ab + 1}$。则 $a^2 - kab + b^2 = k$。
视 $a$为主元，二次方程$a^2 - kb \cdot a + (b^2 - k) = 0$另一根$a' = kb - a$ 也是整数。
Vieta 跳跃：取 $a + b$最小的解，不妨$a \ge b$。
- 若 $b = 0$：$a^2 = k$，$k = a^2$，完全平方。
- 若 $b \ge 1$：$a' = kb - a$，可证 $0 \le a' < b$，得 $(b, a')$是更小解，矛盾（除非$a' = 0$，给 $k = b^2$）。
故 $k = a^2$（$b = 0$）或 $k = b^2$。最终 $k$ 必为完全平方数。
更精细地，所有正整数解由 Pell 型方程 $a^2 - k \cdot ab + b^2 = k$（$k = m^2$）给出，对应 二次型理论 中不定型 $[1, -m^2, 1]$ 的表示。
题30 [难度：CMO]
题目：证明对素数 $p \ge 5$，$\binom{2p-1}{p-1} \equiv 1 \pmod{p^3}$（Wolstenholme 定理）。
分析：组合数论：卢卡斯与库默尔 中 Wolstenholme 型问题。
解答： $\binom{2p-1}{p-1} = \dfrac{(2p-1)!}{(p-1)!^2} = \prod_{k=1}^{p-1} \dfrac{p + k - 1}{k} = \prod_{k=1}^{p-1} \left(1 + \dfrac{p-1}{k}\right)$? 不对，重新写：
$\binom{2p-1}{p-1} = \prod_{k=1}^{p-1} \dfrac{p - 1 + k}{k} = \prod_{k=1}^{p-1} \left(1 + \dfrac{p-1}{k}\right)$
展开至 $p^2$ 项： $$= 1 + (p-1) \sum_{k=1}^{p-1} \frac{1}{k} + (p-1)^2 \sum_{j<k} \frac{1}{jk} + \cdots$$
由 Wolstenholme 引理（整除与同余基础）：$\sum_{k=1}^{p-1} 1/k \equiv 0 \pmod{p^2}$（$p \ge 5$）。
又 $\sum_{j<k} 1/(jk) = \dfrac{1}{2}\left[(\sum 1/k)^2 - \sum 1/k^2\right]$。$\sum 1/k^2 \equiv 0 \pmod p$（$p \ge 5$，因 $\sum_{k=1}^{p-1} k^2 \equiv 0 \pmod p$）。
故 $\binom{2p-1}{p-1} \equiv 1 + 0 + 0 = 1 \pmod{p^3}$。
题31 [难度：竞赛]
题目：求所有素数 $p$使得$p^2 \mid 2^{p-1} - 1$（Wieferich 素数）。
分析：同余方程进阶与Hensel引理 中 Wieferich 素数。
解答： Wieferich 素数是满足 $2^{p-1} \equiv 1 \pmod{p^2}$的素数$p$。
计算小素数：
- $p = 3$：$2^2 = 4$，$4 \bmod 9 = 4 \ne 1$。
- $p = 5$：$2^4 = 16$，$16 \bmod 25 = 16 \ne 1$。
- $p = 7$：$2^6 = 64$，$64 \bmod 49 = 15 \ne 1$。
- $p = 11$：$2^{10} = 1024$，$1024 \bmod 121 = 1024 - 8 \cdot 121 = 1024 - 968 = 56 \ne 1$。
- $p = 13$：$2^{12} = 4096$，$4096 / 169 \approx 24.2$，$4096 - 24 \cdot 169 = 4096 - 4056 = 40 \ne 1$。
- $p = 1093$：经验证满足，是第一个 Wieferich 素数。
- $p = 3511$：第二个。
至 $6.7 \times 10^{15}$ 内仅发现这两个。是否无穷多未知。
题32 [难度：TST]
题目：设 $p$为奇素数。证明$\binom{p^a}{k} \equiv 0 \pmod{p^a / p^{v_p(k)}}$（$1 \le k \le p^a - 1$）。
分析：Lucas 定理的精细化应用。
解答： 由 Kummer：$v_p\negthinspace\binom{p^a}{k}$=$k + (p^a - k)$在$p$ 进制下的进位次数。
设 $k = p^b \cdot m$，$\gcd(m, p) = 1$，$b = v_p(k) < a$（因 $k < p^a$）。
$k$的$p$进制：第$b$ 位非零（$= m_0 \ne 0$），低位全 $0$。
$p^a - k$：借位计算，$p^a - k$的$p$进制表示在低于$a$ 的位非零（具体形式复杂）。
加和 $k + (p^a - k) = p^a$在$p$进制为$1$后跟$a$个$0$。从第 $b$位开始连续进位至第$a$位，共$a - b$ 次进位。
故 $v_p\negthinspace\binom{p^a}{k} = a - b = a - v_p(k)$。
即 $\binom{p^a}{k} \equiv 0 \pmod{p^{a - v_p(k)}}$，等价于 $p^{v_p(k)} \binom{p^a}{k} \equiv 0 \pmod{p^a}$。
七、二次型与表示数（高难度）
题33 [难度：TST]
题目：求所有素数 $p$使得$p = x^2 + 5y^2$ 有整数解。
分析：二次型理论 中判别式 $-20$的类数$h(-20) = 2$。
解答： $[1, 0, 5]$是判别式$-20$ 的主型。$h(-20) = 2$，另一类代表 $[2, 2, 3]$。
由类域论：
- $p$由$[1, 0, 5]$表示$\iff$ $p \equiv 1, 9 \pmod{20}$
- $p$由$[2, 2, 3]$表示$\iff$ $p \equiv 3, 7 \pmod{20}$
- $p \equiv 11, 13, 17, 19 \pmod{20}$ 时不被任何本原型表示
验证：
- $p = 29 \equiv 9 \pmod{20}$：$29 = 3^2 + 5 \cdot 2^2 = 9 + 20$ ✓
- $p = 41 \equiv 1 \pmod{20}$：$41 = 6^2 + 5 \cdot 1^2 = 36 + 5$ ✓
- $p = 7 \equiv 7 \pmod{20}$：$7 = 2 \cdot 1^2 + 2 \cdot 1 \cdot 1 + 3 \cdot 1^2 = 7$ ✓
- $p = 11 \equiv 11 \pmod{20}$：尝试 $x^2 + 5y^2 = 11$，$y = 1 \Rightarrow x^2 = 6$ 无解 ✓
题34 [难度：CMO]
题目：证明每个正整数可表示为四个整数平方和（Lagrange 四平方和定理），并用 Jacobi 公式计算 $r_4(10)$。
分析：二次型理论 §5.4 Lagrange 定理与 Jacobi 公式 $r_4(n) = 8 \sigma(n) - 32 \sigma(n/4)$。
解答： Lagrange 定理证明思路：由 Euler 四平方恒等式 $$(a^2+b^2+c^2+d^2)(e^2+f^2+g^2+h^2) = (\text{四平方和})$$ 只需证每个素数 $p$ 是四平方和。$p = 2$ 平凡。$p$奇：用 Minkowski 凸体定理（二次型理论 §10 例 8）证$x^2 + y^2 + 1 \equiv 0 \pmod p$ 有解，再用无穷递降。
$r_4(10)$ 计算：$10$不被$4$整除，故$r_4(10) = 8 \sigma(10) = 8 \cdot (1 + 2 + 5 + 10) = 8 \cdot 18 = 144$。
验证：$10 = 9 + 1 + 0 + 0$（排列 $4 \cdot 3 = 12$种，符号$2^2 = 4$，共 $48$） $10 = 4 + 4 + 1 + 1$（排列 $6$种，符号$2^4 = 16$，共 $96$） $10 = 4 + 1 + 1 + 4$ 同上 总计 $48 + 96 = 144$ ✓
题35 [难度：竞赛]
题目：判定 $n = 28$ 是否能表示为三整数平方和。
分析：二次型理论 Legendre 三平方和定理：$n \ne 4^a(8b+7)$。
解答： $28 = 4 \cdot 7 = 4^1 \cdot (8 \cdot 0 + 7)$。这正是 $4^a(8b + 7)$ 形式（$a = 1, b = 0$）。
故 $28$ 不能表示为三整数平方和。
验证：枚举 $|x|, |y|, |z| \le 5$（因 $5^2 \cdot 3 = 75 > 28$）。
- $25 + 1 + 1 = 27, 25 + 1 + 4 = 30$，无 $28$。
- $16 + 9 + 4 = 29, 16 + 9 + 1 = 26$，无 $28$。
- $16 + 4 + 4 = 24, 16 + 4 + 9 = 29$，无 $28$。
- $9 + 9 + 9 = 27, 9 + 9 + 4 = 22, 9 + 4 + 4 = 17$，无 $28$。
确实不能 ✓
八、素数分布与解析数论（高难度）
题36 [难度：TST]
题目：用 Chebyshev 方法证明 $\pi(x) \ge c x / \ln x$（$c > 0$ 常数）。
分析：素数分布与解析数论初步 Chebyshev 估计。
解答： 考虑 $\binom{2n}{n}$。它在 $(2n)!$ 中出现，且 $$\frac{4^n}{2n+1} \le \binom{2n}{n} \le 4^n$$
素因子分析：$\binom{2n}{n}$的素因子$p$满足$p \le 2n$（因 $p \mid (2n)!$）。$p > n$时$v_p\binom{2n}{n} = 1$（$p$在$(2n)!$中出现一次，在$n!^2$ 中不出现）。
故 $\binom{2n}{n} \ge \prod_{n < p \le 2n} p$。
取对数：$n \ln 4 - \ln(2n+1) \ge \sum_{n < p \le 2n} \ln p = \theta(2n) - \theta(n)$。
累加 $\sum_{k=1}^{m} [\theta(2^k) - \theta(2^{k-1})] = \theta(2^m) - \theta(1) \ge m \cdot c_1$（$c_1 = \ln 4 - O(1/m)$）。
得 $\theta(x) \ge c x$（$c = \ln 2 - \epsilon$）。结合 $\theta(x) \le \pi(x) \ln x$，得 $\pi(x) \ge c x / \ln x$。
题37 [难度：CMO]
题目：证明 $\sum_{p \le n} \dfrac{\ln p}{p} \le 2 \ln n$（$n \ge 2$），并由此证明 $\pi(n) \ge \dfrac{\ln 2}{2} \cdot \dfrac{n}{\ln n}$。
分析：Mertens 型估计的初等证明。
解答： $\operatorname{lcm}(1, 2, \ldots, n) = \prod_{p \le n} p^{\lfloor \log_p n \rfloor} \le \prod_{p \le n} n = n^{\pi(n)}$
故 $\pi(n) \ge \log_n \operatorname{lcm}(1, \ldots, n) = \dfrac{\ln \operatorname{lcm}}{\ln n}$。
又 $\operatorname{lcm}(1, \ldots, n) \ge \prod_{p \le n} p$（仅取 $p^1$项），故$\ln \operatorname{lcm} \ge \sum_{p \le n} \ln p = \theta(n)$。
由 Bertrand 假设（素数分布与解析数论初步）：$\theta(n) \ge c_1 n$（$c_1 > 0$）。故 $\pi(n) \ge c_1 n / \ln n$。
更精细：$\theta(n) = \sum_{p \le n} \ln p$，每个 $p$贡献$\ln p \le \ln n$，故 $\theta(n) \le \pi(n) \ln n$。
由 $\theta(n) \ge c_1 n$得$\pi(n) \ge c_1 n / \ln n$。
题38 [难度：竞赛]
题目：用 Bertrand 假设证明 $n! < n^n$在$n \ge 2$时严格，但$\dfrac{n!}{n^n}$在$n \to \infty$时趋于$0$。
分析：Stirling 公式与 Bertrand。
解答： 由 Stirling：$n! \sim \sqrt{2\pi n} (n/e)^n$。$n! / n^n \sim \sqrt{2\pi n} / e^n \to 0$（指数衰减）。
Bertrand 假设给出：$(n/2, n)$中有素数$p$，$p \mid n!$但$p \nmid n^n$（$p \nmid n$）。故 $n! \ne n^n$。结合 Stirling，$n! < n^n$（$n \ge 2$）。
九、特殊数列与 Bernoulli 数（高难度）
题39 [难度：CMO]
题目：证明 Clausitz-von Staudt 定理：对偶数 $k \ge 2$， $$B_k + \sum_{\substack{p \text{ 素} \newline (p-1) \mid k}} \frac{1}{p} \in \mathbb{Z}$$
分析：特殊数列的数论性质 Bernoulli 数的分母刻画。
解答： 用 Bernoulli 数的生成函数 $\dfrac{t}{e^t - 1} = \sum B_k t^k / k!$。
关键步骤：对素数 $p$，考虑 $t/(e^t - 1) \bmod p$在$t = 0$ 附近的展开。
在 $\mathbb{F}_p$ 中，$e^t - 1 = \sum_{n=1}^{\infty} t^n/n!$。$(e^t - 1)^{p-1} \equiv (e^{(p-1)t} - 1)/(e^t - 1) \cdot (e^t - 1)^{p-2}$? 直接计算复杂。
标准证明思路：用 $B_k = \sum_{j=0}^{k} \dfrac{1}{j+1} \sum_{i=0}^{j} (-1)^i \binom{j}{i} i^k$。
对素数 $p$与$k$ 偶：
- 若 $(p-1) \mid k$：由 Fermat 小定理 $i^{p-1} \equiv 1 \pmod p$（$p \nmid i$），故 $i^k \equiv 1 \pmod p$，求和贡献 $p B_k \equiv -1 \pmod p$，即 $p B_k + 1 \equiv 0 \pmod p$。
- 若 $(p-1) \nmid k$：$i^k$在$(\mathbb{Z}/p\mathbb{Z})^*$上和为$0$（特征正交性），贡献 $0$。
故 $B_k + \sum_{(p-1) \mid k} 1/p \in \mathbb{Z}$。
题40 [难度：TST]
题目：证明 Fermat 数 $F_n = 2^{2^n} + 1$ 的任意两两互素（$\gcd(F_m, F_n) = 1$当$m \ne n$），并由此推出素数无穷。
分析：特殊数列的数论性质 §3 Fermat 数。
解答： 互素证明：用乘积恒等式 $F_n = F_0 F_1 \cdots F_{n-1} + 2$（$n \ge 1$）。
归纳：$F_1 = 5 = 3 \cdot 1 + 2 = F_0 + 2$✓。设$F_n = F_0 \cdots F_{n-1} + 2$。则 $F_0 \cdots F_{n-1} = F_n - 2$。$F_{n+1} = 2^{2^{n+1}} + 1 = (2^{2^n})^2 + 1 = (F_n - 1)^2 + 1 = F_n^2 - 2 F_n + 2 = F_n(F_n - 2) + 2 = F_n \cdot F_0 \cdots F_{n-1} + 2$。归纳成立。
若 $m < n$且$p \mid F_m, F_n$，则 $p \mid F_0 \cdots F_{n-1}$（含 $F_m$），但 $F_n = F_0 \cdots F_{n-1} + 2$，故 $p \mid 2$，即 $p = 2$。但 $F_n$奇，矛盾。故$\gcd(F_m, F_n) = 1$。
素数无穷：每个 $F_n$至少有一个素因子，且不同$F_n$ 的素因子不同，故素数无穷。
题41 [难度：竞赛]
题目：验证 $M_{19} = 2^{19} - 1 = 524287$ 是 Mersenne 素数。
分析：特殊数列的数论性质 §2.2 Lucas-Lehmer 检验。
解答： 需计算 $s_{17} \bmod M_{19} = 524287$。
$s_0 = 4$ $s_1 = 14$ $s_2 = 194$ $s_3 = 194^2 - 2 = 37634$ $s_4 = 37634^2 - 2 \bmod M$（用快速算法）
详细计算繁复，通常编程实现。已知 $s_{17} \equiv 0 \pmod{524287}$，故 $M_{19}$ 素 ✓。
题42 [难度：CMO]
题目：求 $S_4(100) = \sum_{k=1}^{100} k^4 \bmod 100$。
分析：特殊数列的数论性质 幂次和 Bernoulli 公式。
解答： $S_4(n) = n(n+1)(2n+1)(3n^2+3n-1)/30$。
$S_4(100) = 100 \cdot 101 \cdot 201 \cdot (30000 + 300 - 1) / 30 = 100 \cdot 101 \cdot 201 \cdot 30299 / 30$。
$= 10 \cdot 101 \cdot 201 \cdot 30299 / 3 = 10 \cdot 101 \cdot 67 \cdot 30299$（$201/3 = 67$）。
$\bmod 100$：$10 \cdot 101 \cdot 67 \cdot 30299 \bmod 100$。
$101 \equiv 1$，$67 \equiv 67$，$30299 \equiv 99$。
$10 \cdot 1 \cdot 67 \cdot 99 = 10 \cdot 6633 = 66330 \equiv 30 \pmod{100}$。
故 $S_4(100) \equiv 30 \pmod{100}$。
十、综合应用（顶级难度）
题43 [难度：顶级]
题目（Putnam 2018 B6 改编）：设 $p$为奇素数，证明$\sum_{k=0}^{p-1} \binom{p-1}{k}^2 \equiv \binom{2p-2}{p-1} \pmod{p^2}$，并求 $\bmod p^3$ 的修正项。
分析：Vandermonde 恒等式 $\sum \binom{n}{k}^2 = \binom{2n}{n}$ 与 Wolstenholme 型修正。
解答： Vandermonde：$\sum_{k=0}^{n} \binom{n}{k}^2 = \binom{2n}{n}$（精确，非模）。
故 $\sum_{k=0}^{p-1} \binom{p-1}{k}^2 = \binom{2p-2}{p-1}$（精确等式）。
$\bmod p^3$：由 Wolstenholme（题 30），$\binom{2p-1}{p-1} \equiv 1 \pmod{p^3}$（$p \ge 5$）。
$\binom{2p-2}{p-1} = \binom{2p-1}{p-1} \cdot \dfrac{p-1}{2p-1} \equiv 1 \cdot \dfrac{p-1}{2p-1} \pmod{p^3}$? 不对，需用 $\binom{2p-2}{p-1} = \binom{2p-1}{p-1} \cdot \dfrac{p-1}{2p-1}$? 验证：$\binom{2p-1}{p-1} = \dfrac{(2p-1)!}{(p-1)! p!}$，$\binom{2p-2}{p-1} = \dfrac{(2p-2)!}{(p-1)!^2}$，比值 $\binom{2p-1}{p-1}/\binom{2p-2}{p-1} = \dfrac{(2p-1)}{p} = 2 - 1/p$。
故 $\binom{2p-2}{p-1} = \binom{2p-1}{p-1} \cdot \dfrac{p}{2p-1} \equiv 1 \cdot \dfrac{p}{2p-1} \pmod{p^3}$。
$\dfrac{p}{2p-1} = \dfrac{1}{2 - 1/p} = \dfrac{1}{2} \cdot \dfrac{1}{1 - 1/(2p)} = \dfrac{1}{2}\left(1 + \dfrac{1}{2p} + \dfrac{1}{4p^2} + \cdots\right)$
$= \dfrac{1}{2} + \dfrac{1}{4p} + \dfrac{1}{8p^2} + O(1/p^3)$
故 $\binom{2p-2}{p-1} \equiv \dfrac{1}{2} + \dfrac{1}{4p} + \dfrac{1}{8p^2} \pmod{p^3 / 2}$（需用 $p$-adic 除法更精细处理）。
更直接地，由 Babbage 定理：$\binom{2p-2}{p-1} \equiv 1 \pmod{p^2}$（$p \ge 3$）。$\bmod p^3$ 修正项与 Wolstenholme 素数相关。
题44 [难度：顶级]
题目：证明 $\zeta(2) = \pi^2/6$并推出$\prod_{p} (1 - 1/p^2)^{-1} = \pi^2/6$。
分析：素数分布与解析数论初步 Euler 乘积。
解答： Euler 求 $\zeta(2)$：用 $\sin x / x = \prod_{n=1}^{\infty} (1 - x^2/(n^2 \pi^2))$。
两边取 $x^2$ 系数：$-1/6 = -\sum 1/(n^2 \pi^2)$，故 $\sum 1/n^2 = \pi^2/6$。
Euler 乘积：$\zeta(2) = \sum 1/n^2 = \prod_p 1/(1 - 1/p^2)$（由算术基本定理）。
故 $\prod_p (1 - 1/p^2)^{-1} = \pi^2/6$，即 $\prod_p (1 - 1/p^2) = 6/\pi^2$。
应用：$\prod_p (1 - 1/p^2) = 1/\zeta(2) = 6/\pi^2 \approx 0.6079$。这是"随机两整数互素概率"。
题45 [难度：顶级]
题目：证明 Brun 定理的弱形式：$\sum_{p \text{ 双生}} 1/p \le 10$（粗略上界）。
分析：素数分布与解析数论初步 §7.2 Brun 筛。
解答： Brun 上筛给出双生素数计数 $\pi_2(x) \le C \cdot x / (\ln x)^2$（$C$ 常数）。
用 Abel 求和： $$\sum_{p \le x, p+2 \text{ 素}} \frac{1}{p} = \frac{\pi_2(x)}{x} + \int_2^x \frac{\pi_2(t)}{t^2} dt \le \frac{C}{(\ln x)^2} + \int_2^x \frac{C \thinspace dt}{t (\ln t)^2}$$
后者 $\int_2^{\infty} dt / (t (\ln t)^2) = 1/\ln 2 < \infty$。
故 $\sum_{p \text{ 双生}} 1/p$收敛。Brun 常数$B_2 \approx 1.902$，远小于 $10$。
题46 [难度：顶级]
题目：陈述并证明 Dirichlet 素数定理的特例：等差数列 $4k + 1$ 中有无穷多素数。
分析：素数分布与解析数论初步 §5 Dirichlet $L$函数。完整证明需$L(1, \chi_4) \ne 0$。
解答： 反证：设 $4k + 1$中素数有限，记$P_1 = \lbrace p_1, \ldots, p_n\rbrace $。
考虑 $N = (2 p_1 p_2 \cdots p_n)^2 + 1$。$N$奇，且$N \equiv 1 \pmod 4$。$N$的素因子$q$满足$q \mid x^2 + 1$（$x = 2 p_1 \cdots p_n$），故 $x^2 \equiv -1 \pmod q$，$\left(\dfrac{-1}{q}\right) = 1$，$q \equiv 1 \pmod 4$。
但 $q \ne p_i$（$q \mid N$但$p_i \nmid N$，因 $N \equiv 1 \pmod{p_i}$）。故 $q \in P_1$之外，与$P_1$ 完尽矛盾。
故 $4k + 1$ 中素数无穷。
注
此初等证明仅适用于 $a^2 \equiv -1 \pmod q$可解的情形（即$a = 1, q = 4$）。一般 Dirichlet 定理需 $L$ 函数理论。
题47 [难度：顶级]
题目：证明 Mordell 方程 $y^2 = x^3 - 2$的整数解只有$(3, \pm 5)$。
分析：不定方程与丢番图方程 §8 Mordell 方程。
解答： 模分析缩小范围：
- 模 $4$：$y^2 \equiv x^3 - 2 \pmod 4$。$x$ 偶：$x^3 \equiv 0$，$y^2 \equiv -2 \equiv 2 \pmod 4$，但平方 $\in \lbrace 0, 1\rbrace $，矛盾。故 $x$ 奇。
- $x$ 奇：$x^3 \equiv x \pmod 4$。$y^2 \equiv x - 2 \pmod 4$。若 $x \equiv 1$，$y^2 \equiv -1 \equiv 3$，矛盾。故 $x \equiv 3 \pmod 4$。
- 模 $9$：立方数 $\in \lbrace 0, \pm 1\rbrace $。$y^2 \equiv x^3 - 2 \in \lbrace -2, -1, -3\rbrace \equiv \lbrace 7, 8, 6\rbrace \pmod 9$。平方 $\in \lbrace 0, 1, 4, 7\rbrace $。交为 $\lbrace 7\rbrace $，故 $x^3 \equiv 0 \pmod 9$，$x \equiv 0, 3, 6 \pmod 9$。
结合 $x \equiv 3 \pmod 4$与$x \equiv 0 \pmod 3$，得 $x \equiv 3 \pmod{12}$。
穷举：$x = 3$给$y^2 = 25$，$y = \pm 5$ ✓。$x = 15$：$y^2 = 3373$，$\sqrt{3373} \approx 58.1$，$58^2 = 3364, 59^2 = 3481$，无解。$x = 27$：$y^2 = 19681$，$\sqrt{19681} \approx 140.3$，无。$x = -1$：$y^2 = -3$，无。
完整证明需用 代数数论初步 中 $\mathbb{Z}[\sqrt{-2}]$ 的唯一分解。Mordell 用椭圆曲线理论证明有限性。
题48 [难度：顶级]
题目：陈述 Chevalley-Warning 定理并用它证明对每个素数 $p$，方程 $x^2 + y^2 + z^2 \equiv 0 \pmod p$ 有非零解。
分析：同余方程进阶与Hensel引理 Chevalley-Warning 定理。
解答： Chevalley-Warning 定理：设 $f_1, \ldots, f_k \in \mathbb{F}_p[x_1, \ldots, x_n]$满足$\sum \deg f_i < n$。则 $$\#\lbrace \mathbf{x} \in \mathbb{F}_p^n : f_1(\mathbf{x}) = \cdots = f_k(\mathbf{x}) = 0\rbrace \equiv 0 \pmod p$$
应用：$f(x, y, z) = x^2 + y^2 + z^2$，$n = 3$，$\deg f = 2 < 3$。故解数 $\equiv 0 \pmod p$。
$\mathbf{0} = (0, 0, 0)$显然是解。故解数$\ge 1$。但解数 $\equiv 0 \pmod p$，若 $p > 1$则解数$\ge p$，特别有非零解。
推广
此结果可推广：对 $n$元$d$次齐次方程$f = 0$在$\mathbb{F}_p$上，若$n > d$ 则有非零解。这是 二次型理论 中 Hasse-Minkowski 的有限域版本。
题49 [难度：顶级]
题目：证明 Pell 方程 $x^2 - Dy^2 = 1$（$D > 0$ 非完全平方数）有无穷多正整数解。
分析：不定方程与丢番图方程 §3 Pell 方程与 连分数与丢番图逼近 连分数方法。
解答： 关键引理：存在整数 $x_0, y_0$使$|x_0^2 - D y_0^2| \le 2\sqrt{D} + 1$（$y_0 \ge 1$）。
由 Dirichlet 逼近（连分数与丢番图逼近），存在 $|x/y - \sqrt{D}| < 1/y^2$，故 $|x^2 - D y^2| = |x - \sqrt{D} y| \cdot |x + \sqrt{D} y| < (1/y) \cdot (2 \sqrt{D} y + 1/y) \le 2\sqrt{D} + 1$。
构造解族：取基本解 $(x_1, y_1)$（$|x_1^2 - D y_1^2|$最小者，必为$1$ 由更精细分析）。则 $$x_n + y_n \sqrt{D} = (x_1 + y_1 \sqrt{D})^n, \quad n = 1, 2, 3, \ldots$$ 给无穷多解。
归纳验证：$(x_1 + y_1 \sqrt{D})^2 = (x_1^2 + D y_1^2) + 2 x_1 y_1 \sqrt{D}$，给新解 $(x_1^2 + D y_1^2, 2 x_1 y_1)$。
例子
$D = 2$：基本解 $(3, 2)$（$9 - 8 = 1$）。$(3 + 2\sqrt 2)^2 = 17 + 12\sqrt 2$，$(17, 12)$ 是下个解。
题50 [难度：顶级]
题目：证明 Artin 原根猜想在 $a = 2$时的弱形式：存在无穷多素数$p$使$2$是模$p$ 的原根。
分析：二次剩余与阶 原根分布。完整证明需 GRH，无条件证明至今未得。
解答： 无条件部分结果（Gupta-Murty, 1984）：存在至多 $3$个素数$a_1, a_2, a_3$，其中至少一个在无穷多素数 $p$ 处为原根。
Heath-Brown（1986）改进：至多 $2$ 个素数例外。
完整 Artin 猜想：每个非 $-1$、非平方整数 $a$是无穷多素数$p$ 的原根。
$a = 2$ 的弱形式：未单独无条件证明，但若 Artin 猜想成立，$2$在密度$\approx 0.3739$的素数$p$处为原根（Artin 常数$A = \prod_p (1 - 1/(p(p-1))) \approx 0.3739$）。
现状
Hooley（1967）在 GRH 下证明 Artin 猜想。无条件下仍开放，是数论核心未决问题之一。
总结
数论题目集扩展至 50 题，覆盖：
- 一试基础：整除同余、裴蜀、CRT、费马/欧拉定理、模分析
- 二试进阶：Pell 方程、无穷递降、莫比乌斯反演、二次互反律、原根
- TST/CMO：Lucas/Kummer 定理、Wolstenholme、二次型表示、Mordell 方程
- 顶级难题：Chevalley-Warning、Artin 猜想、Brun 筛、Pell 方程理论、Fermat 数与 Mersenne 素数、Catalan 猜想相关
配合 二次型理论、组合数论：卢卡斯与库默尔、素数分布与解析数论初步、特殊数列的数论性质、数论不等式与估计、代数数论初步、同余方程进阶与Hensel引理、连分数与丢番图逼近 八篇理论笔记，几乎覆盖一试、二试以及 CMO/TST/IMO/Putnam 等更高档次竞赛的全部数论考点。