面向零基础读者的初等数论入门

版式与记号约定

• 记号：$a\mid b$ 表示“a 整除 b”；$\gcd(a,b)$ 表示最大公因数；$\operatorname{lcm}(a,b)$ 表示最小公倍数；$a\equiv b\pmod m$ 表示模 $m$ 同余；$\lfloor x\rfloor$ 表示向下取整。
• 常用等式（记住两条）：$\gcd(a,b)=\gcd(b,\,a\bmod b)$ 与 $a\cdot b=\gcd(a,b)\cdot \operatorname{lcm}(a,b)$
• 解题格式：题干 → 思路 → 计算 → 结论 → 检查点。

目录

• 第0章 快速上手（20分钟速成）
• 第1章 整数、因数与倍数
• 第2章 质数与分解质因数
• 第3章 最大公因数与最小公倍数（含辗转相除法）
• 第4章 同余与余数（模运算）
• 第5章 数位与整除判别（末位、数字和、数根）
• 第6章 奇偶性与构造（含反证直觉）
• 第7章 线性不定方程 $ax+by=c$
• 第8章 抽屉原理（鸽巢原理）在数论中的应用
• 第9章 常见题型模板与做题流程
• 第10章 强化例题与详解（分章）
• 附录A 常用结论速查表
• 附录B 章节练习参考答案

第0章 快速上手（20分钟速成）

你需要的5把钥匙：

1. 分解质因数：把数拆成质数相乘，如 $60=2^2\cdot3\cdot5$。
2. gcd/lcm：记住 $a\cdot b=\gcd(a,b)\cdot \operatorname{lcm}(a,b)$
3. 余数思想：看“被 $k$ 除的余数”，找周期循环。
4. 奇偶性：偶±偶=偶，奇±奇=偶，奇±偶=奇；偶×任意=偶，奇×奇=奇。
5. 方程 $ax+by=c$ 的可解条件：$\gcd(a,b)\mid c$。

两道代表性例题

• 例1：$7^{2025}$ 的个位数？→ 个位按周期 4 循环：7,9,3,1。$2025\equiv1\pmod 4$，故答案 7。
• 例2：解 $6x+9y=30$。→ $\gcd(6,9)=3$, 且 $3\mid30$ 有解。化简 $2x+3y=10$，取 $y=2$ 得 $x=2$。通解：$x=2+3t$, $y=2-2t$（$t\in\mathbb Z$）。

第1章 整数、因数与倍数

概念：$a\mid b$ 表示“a 整除 b”，此时 b 是 a 的倍数。

例题

• 例1：列出 24 的全部因数。 分解：$24=2^3\cdot3$。因数个数 $(3+1)(1+1)=8$ 个：1,2,3,4,6,8,12,24。
• 例2：1—100 中，能被 6 整除的数有几个？ $\lfloor100/6\rfloor=16$ 个（6,12,…,96）。

更多例题

• 例3：设 $n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$，证明因数个数 $d(n)=(a_1+1)(a_2+1)\cdots(a_k+1)$。 思路：每个质因数指数可从 $0$ 取到 $a_i$，独立选择，乘法原理即可。
• 例4：1—1000 中，被 4 或 6 整除的数个数？ 解：容斥：$\lfloor1000/4\rfloor+\lfloor1000/6\rfloor-\lfloor1000/12\rfloor=250+166-83=333$。

练习

1. 写出 36 的因数个数。
2. 1—200 中被 15 整除的数有几个？
3. 判断 7 是否整除 210（说明理由）。

第2章 质数与分解质因数

概念：质数只有 1 和自身两个正因数（2,3,5,7,…）；非质数且大于 1 的称合数。基本定理：任意 $>1$ 的整数可唯一分解为质数的乘积。

技巧：试除到 $\sqrt n$ 即可判定是否质数；常见分解：差平方 $a^2-b^2=(a-b)(a+b)$、提公因式等。

例题

• 例1：分解 84 → $84=2^2\cdot3\cdot7$。
• 例2：判定 97 是否质数。→ $\sqrt{97}\approx9.8$，试除 2,3,5,7，均不整除 ⇒ 97 为质数。

更多例题

• 例3（筛法）：用埃拉托斯特尼筛法列出 $\le 50$ 的质数： $2,3,5,7,11,13,17,19,23,29,31,37,41,43,47$。
• 例4（构造）：分解 $99^2-1=(99-1)(99+1)=98\cdot100$。

练习

1. 分解 90。
2. 判定 143 是否质数。
3. 用“差平方”分解 $n^2-1$。

第3章 最大公因数与最小公倍数（含辗转相除法）

要点：欧几里得算法：$\gcd(a,b)=\gcd(b,\,a\bmod b)$ 反复取余直到 0。且 $\operatorname{lcm}(a,b)=\dfrac{a\,b}{\gcd(a,b)}$

例题

• 例1：$\gcd(84,60)$？ 84=60×1+24；60=24×2+12；24=12×2+0 ⇒ $\gcd=12$。
• 例2：$\operatorname{lcm}(12,18)=12\cdot18/\gcd(12,18)=216/6=36$。

更多例题

• 例3：若 $\gcd(a,b)=6,\ \operatorname{lcm}(a,b)=180$，求所有 $(a,b)$。 设 $a=6x,b=6y,\gcd(x,y)=1$，有 $xy=30$。互素因子对：$(1,30),(2,15),(3,10),(5,6)$。得到 $(6,180),(12,90),(18,60),(30,36)$ 及其对调。
• 例4（扩展欧几里得）：求 $s,t$ 使 $119s+272t=17$。 回代得 $17=7\cdot119-3\cdot272$，故 $(s,t)=(7,-3)$。

练习

1. 用辗转相除法求 $\gcd(119,272)$。
2. 求 $\operatorname{lcm}(48,180)$。
3. 已知 $a\cdot b=420$ 且 $\gcd(a,b)=6$，求 $\operatorname{lcm}(a,b)$。

第4章 同余与余数（模运算）

写法：$a\equiv b\pmod m$ 表示 $a$ 与 $b$ 被 $m$ 除余数相同。

性质：若 $a\equiv b\pmod m$, $c\equiv d\pmod m$，则 $a\pm c\equiv b\pm d\pmod m$ 且 $ac\equiv bd\pmod m$。

消去律 若 $ax\equiv bx\pmod m$ 且 $\gcd(x,m)=1$，则 $a\equiv b\pmod m$。

更一般地，设 $d=\gcd(x,m)$，则

例题

• 例1：$7^{2025}$ 的个位？→ 模 10，周期 4；$2025\equiv1\pmod 4$，故个位 7。
• 例2：解 $x\equiv2\pmod 5$, $x\equiv3\pmod 7$。 列表法得 $x\equiv17\pmod{35}$。

更多例题

• 例3（小型 CRT）：解 $x\equiv 2\pmod 7,\ x\equiv 3\pmod 9$。 设 $x=2+7k$，代入得 $7k\equiv1\pmod 9$，因 $7\cdot4\equiv1\pmod 9$ 得 $k\equiv4\pmod 9$。取 $k=4$ 得 $x\equiv30\pmod{63}$。
• 例4（幂的余数）：求 $2^{2025}+3^{2025}\bmod 5$。 周期 4：$2^{2025}\equiv2$, $3^{2025}\equiv3$，和为 0。

练习

1. 求 $3^{2024}$ 的个位。
2. 解 $x\equiv4\pmod 9,\ x\equiv1\pmod 4$ 的最小正整数 $x$。
3. 求最小 $n$ 使 $2^n$ 的末两位为 76。

第5章 数位与整除判别（末位、数字和、数根）

整除规则（常用）

• 被2整除：末位偶数；被4整除：末两位是 4 的倍数；被8整除：末三位是 8 的倍数。
• 被3/9整除：数字和能被3/9整除（理由：$10\equiv1\pmod 9$）。
• 被5整除：末位 0 或 5；被6整除：同时被2与3整除；被10整除：末位0；被11整除：奇位和与偶位和之差是 11 的倍数。

更多例题

• 例1（原理证明）：若 $N=\sum a_i10^i$，则 $N\equiv\sum a_i\pmod 9$，故数字和判 9 的整除。
• 例2（构造）：求最小三位数，能被 9 与 11 同时整除。 解：$\operatorname{lcm}(9,11)=99$，最小三位倍数为 $198$。

练习

1. 判断 987654 是否被 9 整除。
2. 末两位为“00,04,08,12,16,…”的数都被哪个数整除？
3. 1—200 中，末位是 0 或 5 的数有多少个？

第6章 奇偶性与构造（含反证直觉）

奇偶标准形：偶=$2k$，奇=$2k+1$。

例题

• 例1：任意两个连续整数一奇一偶。→ $n$ 与 $n+1$ 中必有一个被 2 整除。
• 例2：若 $a$ 为奇，证明 $a^2$ 为奇。→ $a=2k+1\Rightarrow a^2=4k(k+1)+1$。

更多例题

• 例3：任取 5 个连续整数，必有一个被 5 整除（模 5 余数覆盖 0—4）。
• 例4（挑战）：棋盘去两对角后不可用 $1\times2$ 多米诺覆盖（双色不平衡）。

练习

1. 证明任意三个连续整数之和为 3 的倍数。
2. 证明 $n(n+1)$ 为偶数（$\forall n\in\mathbb Z$）。
3. 证明奇数个奇数相加为奇数。

第7章 线性不定方程 $ax+by=c$

要点：有解当且仅当 $\gcd(a,b)\mid c$。设 $d=\gcd(a,b)$，令 $a'=a/d$, $b'=b/d$, $c'=c/d$，先解 $a'x+b'y=c'$。若一组特解为 $(x_0,y_0)$，通解 $x=x_0+b' t,\quad y=y_0-a' t\qquad (t\in\mathbb Z)$

例题

• 例1：$6x+9y=30$ → 化简为 $2x+3y=10$；取 $y=2$ 得 $x=2$。通解：$x=2+3t,\ y=2-2t$。
• 例2：$15x+21y=12$。$d=3\nmid12$ ⇒ 无整数解。

更多例题

• 例3（带区间约束）：解 $35x+21y=7$，且 $0\le x\le10$。 化简 $5x+3y=1$，特解 $(2,-3)$。通解 $x=2+3t,\ y=-3-5t$。约束给出 $t=0,1,2$。
• 例4：$21x+14y=77\Rightarrow 3x+2y=11$。取 $(x,y)=(1,4)$，通解 $x=1+2t,\ y=4-3t$。

练习

1. 解 $14x+21y=7$。
2. 解 $8x+12y=100$ 并给出最小正整数解。
3. 判断 $25x+35y=6$ 是否有解。

第8章 抽屉原理（鸽巢原理）在数论中的应用

原理：$n+1$ 只鸽子放进 $n$ 个洞，必有一洞 $\ge 2$ 只。

常见模型

• 余数装箱：按 $\pmod m$ 的余数分成 $m$ 个抽屉。
• 数量保证：只要“数量 > 抽屉数”，必有“至少两个在同一抽屉”。

例题

• 例1：任取 6 个整数，必有两数除以 5 余数相同（抽屉：0—4）。
• 例2：1—100 任取 51 个数，必有一对和为 101（成对：(1,100),(2,99),…,(50,51) 共 50 抽屉）。

更多例题

• 例3：在 1—100 任取 20 个整数，必有两数差是 19 的倍数（mod 19 共有 19 抽屉）。
• 例4：在 1—60 任取 31 个数，必有一对“一个整除另一个”（写成 $2^k\cdot\text{奇数}$ 比较）。

练习

1. 任取 8 个整数，证明必有两数差是 7 的倍数。
2. 任取 10 个两位数，证明至少有两数末位相同。
3. 在 1—60 任取 31 个数，证明必有一对，一个整除另一个。

第9章 常见题型模板与做题流程

题型A：末位/末两位/被 $k$ 除余数

• 模板：找“周期”或直接“模 $k$ 运算”。
• 示例：$2^n$ 的个位循环 2,4,8,6（周期 4）。

题型B：最小公倍数/最大公因数

• 模板：分解质因数再取指数最大/最小；或先用欧几里得算法求 $\gcd$。

题型C：方程求整解

• 模板：先判 $\gcd(a,b)\mid c$；化简，求特解，写通解；若需最小正解，调参数 $t$。

题型D：整除判别/数字和

• 模板：用 3、9、11 的判别法或末位规则。

题型E：分类与构造

• 模板：按余数分类（$\pmod k$），或构造满足条件的数列/反例。

做题通用流程（4步）

1. 识别类型：末位/余数？$\gcd/\operatorname{lcm}$？方程？
2. 写标准形：分解质因数；写成“模方程”；奇偶写成 $2k/2k+1$。
3. 套工具：余数运算、欧几里得、整除判别、抽屉原理。
4. 检验：代回验证；范围与最小性检查。

第10章 强化例题与详解（分章）

覆盖第1—第8章的常见高频问法，每题都附“检查点”。

10.1 因数与倍数

例A（最小构造） 已知 $n$ 有 12 个因数，且 $n$ 是 2 的倍数但不是 4 的倍数，求最小 $n$。 解：$n=2^1\,p^2q^1\Rightarrow n=2\cdot3^2\cdot5=90$。检查点：$d(n)=12$，且 $4\nmid n$。

例B（容斥） 1—1000 中，被 5 或 7 整除的整数个数：$200+142-28=314$。

10.2 质数与分解

例A（筛法） $\le 50$ 的质数见第2章“更多例题”。检查点：只需筛到 $\sqrt{50}<8$。

例B（快速判定） $n=221$，判定是否质数。 解：$\sqrt{221}\approx14.8$；试除 2,3,5,7,11,13。发现 $221=13\cdot17$。

10.3 $\gcd/\operatorname{lcm}$

例A 若 $\gcd(a,b)=6$ 且 $ab=1080$，求 $\operatorname{lcm}(a,b)$。 解：用恒等式直接得 $\operatorname{lcm}=\dfrac{ab}{\gcd}=\dfrac{1080}{6}=180$。

例B（系数表示） 用扩展欧几里得写出 $\gcd(272,119)=17$ 的整数表示：$17=7\cdot119-3\cdot272$。

10.4 同余

例A（两模合并） 解 $x\equiv 2\pmod7,\ x\equiv 3\pmod9$ 得 $x\equiv30\pmod{63}$。 例B（幂周期） $2^{2025}+3^{2025}\equiv0\pmod5$。检查点：周期均为 4。

10.5 数位与整除

例A（9 的判别） 证明见第5章。 例B（构造） 最小三位数被 9 与 11 同时整除：$198$。

10.6 奇偶与构造

例A 任取 5 个连续整数，必有一个被 5 整除（余数覆盖）。 例B（挑战） 棋盘去两角不可覆盖（双色不平衡）。

10.7 线性不定方程

例A（区间解） $35x+21y=7$, $0\le x\le10$ → $x=2+3t$（$t=0,1,2$）。 例B $3x+2y=11$ → $(x,y)=(1+2t,\,4-3t)$；如需正整数解取 $t=0,1$。

10.8 抽屉原理

例A 任取 20 个整数于 1—100，必有两数差为 19 的倍数（mod 19）。 例B 任取 31 个数于 1—60，必有一对“一者整除另一者”（奇数部分法）。

附录A 常用结论速查表

• $a\cdot b=\gcd(a,b)\cdot \operatorname{lcm}(a,b)$

• $\gcd(a,b)=\gcd(b,\,a\bmod b)$

• 若 $a\equiv b\pmod m$，则 $a\pm k\equiv b\pm k\pmod m,\qquad ak\equiv bk\pmod m$

• 幂的个位周期：

  • 2→(2,4,8,6)；3→(3,9,7,1)；4→(4,6)；7→(7,9,3,1)；8→(8,4,2,6)；9→(9,1)。

• 被11整除判别：奇位和−偶位和 是 11 的倍数（含 0）。

• $ax+by=c$ 有解 $\Leftrightarrow\ \gcd(a,b)\mid c$；通解 $x=x_0+(b/d)t,\ y=y_0-(a/d)t$（$d=\gcd(a,b)$）。

附录B 章节练习参考答案

第1章

1. $36=2^2\cdot3^2\Rightarrow (2+1)(2+1)=9$。
2. $\lfloor200/15\rfloor=13$。
3. $210=7\cdot30$，故 7 整除 210。

第2章

1. $90=2\cdot3^2\cdot5$。
2. $143=11\cdot13$ 为合数。
3. $n^2-1=(n-1)(n+1)$。

第3章

1. 见“更多例题 例4”的回代过程，$\gcd=17$。
2. $\operatorname{lcm}(48,180)=\dfrac{48\cdot180}{12}=720$。
3. $\operatorname{lcm}=\dfrac{420}{6}=70$。

第4章

1. 3 的个位周期 (3,9,7,1)，$2024\equiv0\pmod4$ ⇒ 个位 1。
2. $x\equiv13\pmod{36}$。
3. 最小 $n=20$（周期 20，见课堂验算）。

第5章

1. 数字和 $9+8+7+6+5+4=39$ 被 9 整除 ⇒ 是。
2. 末两位是 4 的倍数 ⇒ 被 4 整除。
3. 每 10 个有 2 个，$200/10\times2=40$。

第6章

1. $(n-1)+n+(n+1)=3n$ 被 3 整除。
2. $n$ 与 $n+1$ 至少一偶 ⇒ 积为偶。
3. 归纳或奇偶加法规律可证。

第7章

1. $d=7$，化简 $2x+3y=1$，特解 $(2,-1)$。通解 $x=2+3t,\ y=-1-2t$。
2. $d=4$，化简 $2x+3y=25$。特解 $(11,1)$，通解 $x=11+3t,\ y=1-2t$。最小正整解：取 $t=-3$ 得 $(2,7)$。
3. $d=5\nmid6$ ⇒ 无解。

第8章

1. 模 7 共有 7 抽屉，取 8 个必同余；差是 7 的倍数。
2. 10 个末位抽屉（0—9）；取 10 个两位数必有同末位。
3. 写成 $2^k\cdot\text{奇数}$；奇数部分最多 30 种，取 31 个必撞同奇数部分，较小者整除较大者。

结语

先用第0章跑通直觉，再按第9章流程做题。不会时先问：这是“余数”“$\gcd/\operatorname{lcm}$”“奇偶”还是“抽屉”？把题改写成标准形，九成题目就开窍。