初等数论入门 · 全课基础练习卷

一、整除与素数（对应第1、2课）

1. 用带余除法计算：$-17$ 除以 $5$ 的商和余数。
2. 求 $\gcd(126, 84)$ 和 $\text{lcm}(126, 84)$。
3. 使用扩展欧几里得算法，求整数 $x, y$ 使得 $48x + 18y = \gcd(48, 18)$。
4. 将 $180$ 分解为标准素因数乘积形式。
5. 列举出 $30$ 以内的所有素数。

二、积性函数与莫比乌斯反演（对应第3、4课）

6. 计算欧拉函数 $\varphi(12)$ 的值。
7. 计算除数函数 $\tau(36)$（即 $36$ 的正约数个数）。
8. 已知 $f(n) = \sum_{d|n} g(d)$，且 $g$ 是莫比乌斯函数 $\mu$，求 $f(6)$ 的值。
9. 判断函数 $f(n) = n^2$ 是否为积性函数（简述理由）。
10. 计算莫比乌斯函数 $\mu(30)$ 和 $\mu(18)$。

三、同余与原根（对应第6、7课）

11. 化简 $2^{100} \pmod 7$。
12. 解一元线性同余方程：$3x \equiv 4 \pmod 7$。
13. 写出模 $10$ 的一个完全剩余系。
14. 求模 $7$ 意义下 $3$ 的阶（即最小的正整数 $k$ 使得 $3^k \equiv 1 \pmod 7$）。
15. 判断 $2$ 是否为模 $11$ 的原根（写出判断依据即可）。

四、二次剩余与不定方程（对应第8、9、10课）

16. 利用勒让德符号计算 $\left(\frac{19}{23}\right)$（即判断 $19$ 是否是模 $23$ 的二次剩余）。
17. 写出二元一次不定方程 $3x + 5y = 1$ 的一组整数解。
18. 写出本原勾股数组 $(a, b, c)$ 的一个例子（满足 $a^2+b^2=c^2$ 且 $\gcd(a,b,c)=1$）。
19. 佩尔方程 $x^2 - 2y^2 = 1$ 的最小正整数解 $(x_1, y_1)$ 是什么？
20. 写出实数 $\sqrt{2}$ 的前三项简单连分数展开系数 $[a_0; a_1, a_2]$。