初等数论参考练习

本文整理了 30 道初等数论练习题，覆盖同余式、二次剩余、原根、不定方程、分圆多项式、Dirichlet 密度等主题。

问题 1. 设 $p$ 为奇素数。对于正整数 $1 \le i \le p-1$，令 $a_i$ 是一个满足 $i a_i \equiv 1 \pmod{p}$ 的正整数。

1. 证明 $\displaystyle\sum_{i=1}^{p-1} a_i \equiv 0 \pmod{p}$。
2. 设 $S$ 为前 $p-1$ 个正整数之和：$S = 1 + 2 + \cdots + (p-1)$。证明对于所有素数 $p > 3$ 都有 $(p-1)! \not\equiv -1 \pmod{S}$。

问题 2. 设 $p$ 和 $q$ 为奇素数。假设 $q$ 能整除梅森数 $M_p = 2^p - 1$。证明 $q > p$。

问题 3. 考虑二次同余式 $x^2 \equiv a \pmod{p^2}$，其中 $p$ 为奇素数且 $\gcd(a, p) = 1$。

1. 设 $x_0$ 是 $x^2 \equiv a \pmod{p}$ 的一个解。证明存在模 $p$ 下唯一的整数 $t$，使得 $x_1 = x_0 + tp$ 是该同余式模 $p^2$ 的解。
2. 证明：对任意正整数 $k$，方程 $x^2 \equiv a \pmod{p^k}$ 都有解。

问题 4. 考虑不定方程 $x^3 + 2y^3 = 7z^3$。

1. 证明任意整数的立方模 $7$ 必然同余于 $0, 1$ 或 $-1$。
2. 证明方程 $x^3 + 2y^3 = 7z^3$ 仅有平凡解 $x = y = z = 0$。

问题 5. 考虑方程 $x^2 - 3y^2 = 1$。

1. 求此方程最小的正整数解 $(x_1, y_1)$。
2. 通过 $(x_n + y_n\sqrt{3}) = (x_1 + y_1\sqrt{3})^n$ 定义解序列 $(x_n, y_n)$。证明 $x_n$ 始终为奇数。
3. 证明 $\{(x_n, y_n) \mid n \in \mathbb{Z}_{>0}\}$ 即是此方程所有的正整数解。

问题 6. 设 $\mu(n)$ 表示莫比乌斯函数，$\Phi_n(x)$ 表示第 $n$ 个分圆多项式。我们有 $x^n - 1 = \prod_{d \mid n} \Phi_d(x)$。

1. 将 $\Phi_n(x)$ 表示为 $x^d - 1$ 的有理函数。
2. 设 $p$ 为素数。证明 $\Phi_{p^k}(x) = \Phi_p(x^{p^{k-1}})$。

问题 7. 求 $7^{7^7}$ 除以 $100$ 的余数。

问题 8. 设 $a \in \mathbb{Z}$ 和 $10$ 互素。证明 $a^{20} \equiv 1 \pmod{100}$。

问题 9. 设 $p > 3$ 为素数。假设存在整数 $a$，使得 $a$ 在模 $p$ 下的（乘法）阶为 $3$。

1. 证明：$p \equiv 1 \pmod{3}$。
2. 证明：$a^2 + a + 1 \equiv 0 \pmod{p}$。
3. 确定 $a + 1$ 模 $p$ 的（乘法）阶，并给出证明。

问题 10. 设 $p$ 是一个奇素数，且 $p \nmid 2026$。当 $p$ 满足什么条件时，同余方程 $x^2 \equiv 2026 \pmod{p}$ 有解？

问题 11. 解不定方程 $x^2 + y^2 + z^2 = 615$。

问题 12.

1. 证明对于任意素数 $p$ 和正整数 $k$，方程 $x^2 \equiv x \pmod{p^k}$ 只有两个解，并写出这两个解。
2. 求同余方程 $x^2 \equiv x \pmod{100}$ 在模 $100$ 意义下的所有解。

问题 13. 设 $p$ 为奇素数。

1. 证明对于任意整数 $0 \le k \le p-1$，组合数满足同余式：$\binom{p-1}{k} \equiv (-1)^k \pmod{p}$。
2. 计算 $\displaystyle\sum_{k=0}^{p-1} \binom{p-1}{k}^2$ 模 $p$ 的余数。

问题 14. 考虑有限域 $\mathbb{F}_p$ 上的线性方程组（其中 $p > 3$ 为素数）：

对于哪些 $a \in \mathbb{F}_p$，上述方程组有解？

问题 15. 设 $p$ 为奇素数，$g$ 是模 $p$ 的一个原根。

1. 证明：$g^{(p-1)/2} \equiv -1 \pmod{p}$。
2. 对于哪些奇素数 $p$，$-g$ 仍然是模 $p$ 的原根？请给出证明。

问题 16. 设 $n$ 是严格大于 $1$ 的整数。证明 $n^4 + 4^n$ 一定不是素数。 （提示：利用恒等式 $a^4 + 4b^4 = (a^2 + 2b^2 + 2ab)(a^2 + 2b^2 - 2ab)$。）

问题 17. 求方程 $x^2 + y^2 = 2$ 的所有有理数解。 （提示：换元 $u = \frac{x+y}{2}$, $v = \frac{x-y}{2}$。）

问题 18. 设 $p$ 为奇素数，且 $a$ 是一个不能被 $p$ 整除的整数。

1. 证明：$\displaystyle\sum_{y=0}^{p-1} \left(\frac{y^2 + a}{p}\right) = -1$，其中括号代表 Legendre 符号。
2. 计算同余方程 $x^2 - y^2 \equiv a \pmod{p}$ 在模 $p$ 下的解 $(x_0, y_0)$ 的个数。

问题 19. 考虑不定方程 $x^2 + y^2 = z^3$。

1. 证明：如果上述方程有整数解 $(x_0, y_0, z_0)$，满足 $x_0, y_0$ 互素，那么 $x_0$ 是奇数，且 $y_0$ 是偶数。
2. 证明在 Gauss 整数环 $\mathbb{Z}[\sqrt{-1}]$ 中 $x_0 + y_0\sqrt{-1}$ 和 $x_0 - y_0\sqrt{-1}$ 互素。
3. 证明存在整数 $a, b$，使得 $$\begin{cases} x_0 = a(a^2 - 3b^2), \\ y_0 = b(3a^2 - b^2), \\ z_0 = a^2 + b^2. \end{cases}$$

问题 20. 考虑以下线性同余方程组：

1. 证明该方程组有解当且仅当 $a \equiv 5 \pmod{6}$。
2. 设 $a = 11$，求该方程组的所有解。

问题 21. 求所有大于 $7$ 的奇素数，使得 $105$ 是模 $p$ 的二次剩余。这样的素数的 Dirichlet 密度是多少？

问题 22. 记 $p$ 的所有二次剩余为 $a_1, a_2, \ldots, a_{\frac{p-1}{2}}$。证明

问题 23. 证明不定方程 $(x^2 - 2)(x^2 - 3)(x^3 - 6) = 0$ 没有整数解，但对于任意素数 $p$，此方程模 $p$ 都有解。

问题 24. 考虑三次分圆整数环 $\mathbb{Z}[\omega]$，其中 $\omega = e^{2\pi\sqrt{-1}/3}$。对于任意 $x = a + b\omega \in \mathbb{Z}[\omega]$，定义其范数为 $N(x) = a^2 - ab + b^2$。设 $\alpha, \beta \in \mathbb{Z}[\omega]$，且它们的范数 $N(\alpha)$ 与 $N(\beta)$ 都不能被 $3$ 整除。假设 $\alpha$ 和 $\beta$ 在环 $\mathbb{Z}[\omega]$ 中是互素的。

1. $\alpha, \beta$ 在 $\mathbb{Z}$ 中的范数 $N(\alpha)$ 和 $N(\beta)$ 是否一定互素？如果为真，请证明；如果为假，请提供一个反例。
2. 设正整数 $g$ 为 $N(\alpha)$ 和 $N(\beta)$ 在 $\mathbb{Z}$ 中的最大公约数。证明 $g \equiv 1 \pmod{3}$。

问题 25. 证明：对于任意给定的正整数 $k$，都存在无穷多个素数，其十进制表示的最后 $k$ 位数字全为 $1$。

问题 26. 设 $A$ 为满足 $p \equiv 1 \pmod{3}$ 的素数集合，$B$ 为满足 $p \equiv 3 \pmod{4}$ 的素数集合。分别求集合 $A$、集合 $B$、集合 $A \cap B$ 的 Dirichlet 密度。

问题 27. 证明任意一个等差数列

都必定包含一个非素数。

问题 28.

1. 设 $m$ 是一个正整数。证明：若 $p = 2^m + 1$ 是一个素数，则 $m$ 是 $2$ 的方幂。
2. 对 $n \ge 0$，记 $F_n = 2^{2^n} + 1$，称为 Fermat 数。证明：若 $m > n$，则 $F_n \mid (F_m - 2)$。
3. 证明：若 $m \neq n$，则 $\gcd(F_m, F_n) = 1$。利用这个结论证明素数有无穷多个。

问题 29. 求 $2026^{618}$ 在十进制下的最后两位数。

问题 30. 设 $p$ 是一个奇素数。证明所有模 $p$ 原根都是模 $p$ 的二次非剩余。对于哪些奇素数 $p$ 所有的模 $p$ 二次非剩余都是原根？