第 8 章 · 整数の性質

项目	内容
シラバス项目	6. 整数の性質（数学Ａ）：(1) 約数と倍数（① 倍数の判定法 ② 素数と素因数分解 ③ 最大公約数，最小公倍数 ④ 整数の割り算）、(2) ユークリッドの互除法、(3) 1次不定方程式、(4) 記数法
コース	コース1、コース2 都考
国内书对应	无。国内书只在第 34 章 34.2 节“常用推论”里提到约数个数公式
本章新内容的分量	全新。五个知识点都要从头学；小学学过的因数、倍数、质数只够当起点

国内现行高中课程没有“整数”这一块：辗转相除法和进位制原来在旧课标必修 3 的“算法案例”里，新课标已经删掉，一次不定方程从来没有系统讲过。EJU 却常拿整数出一整道大题，コース1 尤其如此：2020 年第 2 回コース1 的 Ⅲ 是一次不定方程，2021 年第 1 回コース1 的 Ⅲ 是 5 进制、9 进制、4 进制的记数法。丢分主要丢在三处：一次不定方程的一般解写错系数，n 进制转换时余数读反，按余数分类时漏掉一类。

8.1 与国内的对照

シラバス小项目（日文原文）	国内书位置	相同 / 讲法不同 / 国内没有	本章哪节讲
(1) ① 倍数の判定法	无（小学学过 2、3、5 的倍数特征）	国内没有（高中）	8.2
(1) ② 素数と素因数分解	国内书第 34 章 34.2 节只有约数个数公式，没有约数总和	国内没有（高中）	8.2
(1) ③ 最大公約数，最小公倍数	无（小学学过求法）	国内没有（高中）	8.3
(1) ④ 整数の割り算	无	国内没有	8.3
(2) ユークリッドの互除法	无（旧课标“算法案例”的辗转相除法，新课标已删）	国内没有	8.4
(3) 1次不定方程式	无	国内没有	8.5
(4) 記数法	无（旧课标“算法案例”的进位制，新课标已删）	国内没有	8.6

在日本现行教科书里，这部分放在数学Ａ「数学と人間の活動」一章，各出版社的编排不完全一样；EJU シラバス仍把它单列为第 6 项，范围就是上表的七个小项。

本章五个知识点是一条线：先会分解和判定（8.2），再会算最大公约数和余数（8.3）；互除法（8.4）是求最大公约数的快办法，又是解一次不定方程（8.5）的工具；记数法（8.6）靠的是反复做除法取余数。

8.2 倍数の判定法と素因数分解

说明

約数と倍数：$a$、$b$ 是整数，$b \ne 0$。如果有整数 $k$ 使 $a = bk$，就说 $b$ 是 $a$ 的約数（约数，小学叫因数），$a$ 是 $b$ 的倍数。日本教科书里约数包括负数：6 的约数是 $\pm 1, \pm 2, \pm 3, \pm 6$。题目说「正の約数」时才只取正的。0 是任何非零整数的倍数。

倍数の判定法：不做除法，只看数字就能判断是不是某个数的倍数。

判定	条件	例
2 的倍数	末位是 0、2、4、6、8	538
5 的倍数	末位是 0 或 5	745
4 的倍数	末两位组成的数是 4 的倍数	7316：16 是 4 的倍数
8 的倍数	末三位组成的数是 8 的倍数	5136：136 是 8 的倍数
3 的倍数	各位数字之和是 3 的倍数	2457：$2 + 4 + 5 + 7 = 18$
9 的倍数	各位数字之和是 9 的倍数	2457：18 是 9 的倍数
6 的倍数	既是 2 的倍数又是 3 的倍数	2454
11 的倍数	从末位起，奇数位数字之和与偶数位数字之和的差是 11 的倍数（含 0）	9273：$(3 + 2) - (7 + 9) = -11$

素数：大于 1、正约数只有 1 和它本身的自然数，如 $2, 3, 5, 7, 11, 13, \dots$。中文叫质数。1 不是素数；2 是唯一的偶素数。大于 1 又不是素数的自然数叫合成数（合数）。

素因数分解：把自然数写成素数的积，如 $540 = 2^2 \cdot 3^3 \cdot 5$。做法是从最小的素数 2 开始反复去除，除不尽再换下一个素数。一个自然数的素因数分解只有一种（不计顺序），这叫素因数分解的唯一性。日本教科书写乘号时多用 $\cdot$ 或 $\times$。

判断一个数是不是素数：只要用不超过 $\sqrt{N}$ 的素数去试除，都除不尽，$N$ 就是素数。例如判断 211：$\sqrt{211} < 15$，用 2、3、5、7、11、13 试除都不尽，所以 211 是素数。

正の約数の個数と総和：设 $N = p^a q^b r^c$（$p$、$q$、$r$ 是不同的素数），则

$$\text{正の約数の個数} = (a + 1)(b + 1)(c + 1),$$ $$\text{正の約数の総和} = (1 + p + \dots + p^a)(1 + q + \dots + q^b)(1 + r + \dots + r^c).$$

素因数是两个或四个以上时同样写。

使用场景

• 题目给出含未知数字的多位数，要求它是某个数的倍数：用倍数判定法列出数字要满足的条件。
• 题目问「正の約数の個数」「正の約数の総和」：先素因数分解，再套公式。
• 题目要求 $\sqrt{kn}$ 是自然数，或 $kn$ 是某个自然数的平方：看素因数分解里每个指数是不是偶数。
• 题目问 $n!$ 能被某个素数整除几次，或 $n!$ 的末尾有几个 0：数 1 到 $n$ 里 $p, p^2, p^3, \dots$ 的倍数各有几个。

注意点

• 判定“36 的倍数”要拆成互素的两个数：$36 = 4 \times 9$，4 和 9 互素，所以“是 36 的倍数”等价于“既是 4 的倍数又是 9 的倍数”。拆成 $3 \times 12$ 不行（见易错点）。
• 1 不是素数，也不写进素因数分解。
• 约数个数公式里每个指数都要加 1，因为指数可以取 0。
• 约数总和公式的每个括号都从 1 开始写。
• EJU 题干的说法：「〜の倍数である」「〜で割り切れる」（能被……整除）、「正の約数の個数」「正の約数の総和」「素因数分解すると」。

证明

结论 1：3 和 9 的判定法。 以四位数 $N = 1000a + 100b + 10c + d$ 为例（$a, b, c, d$ 是各位数字）：

$$N = (999a + 99b + 9c) + (a + b + c + d).$$

（关键一步：$10^k - 1 = 99\cdots9$ 是 9 的倍数，所以 $1000a = 999a + a$ 等，每一位都可以拆成“9 的倍数 + 数字本身”。）括号 $999a + 99b + 9c$ 是 9 的倍数，当然也是 3 的倍数。所以 $N$ 是 9（或 3）的倍数，当且仅当 $a + b + c + d$ 是 9（或 3）的倍数。位数更多时同理。

结论 2：4 和 8 的判定法。 $N = 100m + (\text{末两位})$，$100 = 4 \times 25$ 是 4 的倍数，所以只看末两位。$1000 = 8 \times 125$ 是 8 的倍数，所以 8 只看末三位。

结论 3：11 的判定法。 四位数 $N = 1000a + 100b + 10c + d$，因为 $1000 = 1001 - 1$，$100 = 99 + 1$，$10 = 11 - 1$，而 $1001 = 11 \times 91$，$99 = 11 \times 9$，所以

$$N = (1001a + 99b + 11c) + (d - c + b - a).$$

前一个括号是 11 的倍数，所以 $N$ 是 11 的倍数当且仅当 $(d + b) - (c + a)$ 是 11 的倍数。

结论 4：约数的个数和总和。 以 $N = p^a q^b$ 为例。由素因数分解的唯一性，$N$ 的正约数只能含素因数 $p$、$q$，而且指数不超过 $a$、$b$，所以每个正约数都写成 $p^i q^j$（$0 \le i \le a$，$0 \le j \le b$）。

• 个数：$i$ 有 $a + 1$ 种取法，$j$ 有 $b + 1$ 种取法，由分步乘法计数原理（国内书第 34 章 34.2 节）共 $(a + 1)(b + 1)$ 个。
• 总和：把 $(1 + p + \dots + p^a)(1 + q + \dots + q^b)$ 展开，每一项是从第一个括号取一个 $p^i$、从第二个括号取一个 $q^j$ 相乘，得到 $p^i q^j$。（关键一步：每个约数 $p^i q^j$ 在展开式中恰好出现一次，不重不漏。）所以展开式就是所有正约数之和。

结论 5：试除到 $\sqrt{N}$ 就够了。 若 $N$ 是合成数，可以写成 $N = mn$，$1 < m \le n$，则 $m^2 \le mn = N$，$m \le \sqrt{N}$。$m$ 的素因数也不超过 $\sqrt{N}$，并且整除 $N$。所以不超过 $\sqrt{N}$ 的素数都除不尽时，$N$ 不可能是合成数。

素因数分解的唯一性，日本高中教科书当作事实使用。严格证明要用到“素数 $p$ 整除 $ab$，则 $p$ 整除 $a$ 或 $b$”，这可以由 8.4 节的互除法推出（见 8.5 节证明里的引理）。

例题

例 1　（场景：含未知数字的多位数是某数的倍数）

問題　$4$ 桁の整数 $5a2b$（$a$，$b$ は $1$ 桁の数字）が $36$ の倍数であるとき，そのような $4$ 桁の整数をすべて求めよ。

解答　$36 = 4 \times 9$ で，$4$ と $9$ は互いに素であるから，条件は「$4$ の倍数かつ $9$ の倍数」と同値である。

(1) $4$ の倍数：下 $2$ 桁 $2b$（すなわち $20 + b$）が $4$ の倍数であるから，$b = 0, 4, 8$。

(2) $9$ の倍数：各位の数字の和 $5 + a + 2 + b = 7 + a + b$ が $9$ の倍数である。$a + b$ は $0$ から $18$ までだから，$7 + a + b = 9$ または $18$，すなわち $a + b = 2$ または $11$。

(3) 組合せ： $b = 0$ のとき $a = 2$（$a = 11$ は数字でない）。 $b = 4$ のとき，$a + b = 2$ は $a = -2$ となり不適，$a + b = 11$ は $a = 7$。 $b = 8$ のとき，$a + b = 2$ は不適，$a + b = 11$ は $a = 3$。

よって求める整数は $5220$，$5328$，$5724$ である。

中文翻译　题目：四位数 $5a2b$（$a$、$b$ 是一位数字）是 $36$ 的倍数，求所有这样的四位数。解答：$36 = 4 \times 9$，$4$ 和 $9$ 互素，所以条件等价于“是 $4$ 的倍数且是 $9$ 的倍数”。（1）$4$ 的倍数：末两位 $2b$（即 $20 + b$）是 $4$ 的倍数，$b = 0, 4, 8$。（2）$9$ 的倍数：数字和 $5 + a + 2 + b = 7 + a + b$ 是 $9$ 的倍数。$a + b$ 在 $0$ 到 $18$ 之间，所以 $7 + a + b = 9$ 或 $18$，即 $a + b = 2$ 或 $11$。（3）组合：$b = 0$ 时 $a = 2$（$a = 11$ 不是数字）；$b = 4$ 时 $a + b = 2$ 得 $a = -2$ 不行，$a + b = 11$ 得 $a = 7$；$b = 8$ 时 $a + b = 2$ 不行，$a + b = 11$ 得 $a = 3$。所以这样的四位数是 $5220$、$5328$、$5724$。

解说　容易卡在：$a + b$ 只想到等于 $2$，漏了 $11$。数字和可以是 $9$，也可以是 $18$（$a + b$ 最大为 $18$，所以 $7+a+b$ 最大为 $25$，只可能等于 $9$ 或 $18$）。拆 $36$ 要拆成互素的 $4 \times 9$，不能拆成 $3 \times 12$，否则两个条件会重叠。

例 2　（场景：正约数的个数与总和）

問題　$540$ の正の約数の個数と総和を求めよ。

解答　$540 = 2^2 \cdot 3^3 \cdot 5$ である。

個数：$(2 + 1)(3 + 1)(1 + 1) = 3 \times 4 \times 2 = 24$。

総和：$(1 + 2 + 4)(1 + 3 + 9 + 27)(1 + 5) = 7 \times 40 \times 6 = 1680$。

中文翻译　题目：求 $540$ 的正约数的个数和总和。解答：$540 = 2^2 \cdot 3^3 \cdot 5$。个数：$(2 + 1)(3 + 1)(1 + 1) = 3 \times 4 \times 2 = 24$。总和：$(1 + 2 + 4)(1 + 3 + 9 + 27)(1 + 5) = 7 \times 40 \times 6 = 1680$。

解说　约数个数的公式里，每个指数有“取 $0$ 到 $a$“共 $a + 1$ 种，所以是 $(a+1)(b+1)\cdots$，不是 $ab\cdots$。总和的每个括号都要从 $1$（即 $p^0$）写起，漏了 $1$ 就会把不含该素因数的约数全丢掉；括号里的和可以用等比数列求和公式。

例 3　（场景：乘积是平方数）

問題　$\sqrt{756n}$ が自然数となる最小の自然数 $n$ を求めよ。

解答　$756 = 2^2 \cdot 3^3 \cdot 7$ である。$\sqrt{756n}$ が自然数であることは，$756n$ がある自然数の平方であること，すなわち $756n$ の素因数分解のすべての指数が偶数であることと同じである。$2^2$ の指数はすでに偶数で，$3^3$ はあと $1$ 個の $3$，$7$ はあと $1$ 個の $7$ が必要である。よって最小の $n = 3 \times 7 = 21$ であり，このとき $756 \times 21 = 2^2 \cdot 3^4 \cdot 7^2 = 126^2$，$\sqrt{756n} = 126$ である。

中文翻译　题目：求使 $\sqrt{756n}$ 为自然数的最小自然数 $n$。解答：$756 = 2^2 \cdot 3^3 \cdot 7$。$\sqrt{756n}$ 是自然数，即 $756n$ 是某个自然数的平方，也就是 $756n$ 的素因数分解中每个指数都是偶数。$2^2$ 的指数已是偶数；$3^3$ 还差一个 $3$；$7$ 还差一个 $7$。所以最小的 $n = 3 \times 7 = 21$，此时 $756 \times 21 = 2^2 \cdot 3^4 \cdot 7^2 = 126^2$，$\sqrt{756n} = 126$。

解说　平方数的判定：素因数分解中每个指数都是偶数。做法是把已有的指数补到下一个偶数：$3$ 的指数 $3$ 补到 $4$，$7$ 的指数 $1$ 补到 $2$，缺的因数乘起来就是最小的 $n$。补完可以验算 $756n$ 是否真的开得尽方。

例 4　（场景：$n!$ 中素因数的个数）

問題　$30!$ を素因数分解したとき，$2$ の指数はいくらか。また，$30!$ の末尾に続く $0$ の個数を求めよ。

解答　$1$ から $30$ までのうち，$2$ の倍数は $15$ 個でそれぞれ少なくとも $1$ 個の $2$ を含む。$4$ の倍数は $7$ 個でさらにもう $1$ 個，$8$ の倍数は $3$ 個でさらにもう $1$ 個，$16$ の倍数は $1$ 個でさらにもう $1$ 個を含む。よって $2$ の指数は $15 + 7 + 3 + 1 = 26$。

末尾の $0$ は $10 = 2 \times 5$ から生じ，その個数は $2$ の指数と $5$ の指数の小さい方である。$5$ の指数は，$5$ の倍数 $6$ 個と $25$ の倍数 $1$ 個から $6 + 1 = 7$。$7 < 26$ であるから，末尾に続く $0$ は $7$ 個である。

中文翻译　题目：$30!$ 素因数分解后，$2$ 的指数是多少？$30!$ 的末尾连续有几个 $0$？解答：$1$ 到 $30$ 中，$2$ 的倍数有 $15$ 个，每个至少贡献一个 $2$；$4$ 的倍数有 $7$ 个，各再多贡献一个；$8$ 的倍数有 $3$ 个，再多一个；$16$ 的倍数有 $1$ 个，再多一个。所以 $2$ 的指数是 $15 + 7 + 3 + 1 = 26$。末尾的 $0$ 来自因数 $10 = 2 \times 5$，个数等于 $2$ 的指数和 $5$ 的指数中较小的那个。$5$ 的指数：$5$ 的倍数 $6$ 个，$25$ 的倍数 $1$ 个，共 $6 + 1 = 7$。$7 < 26$，所以末尾有 $7$ 个 $0$。

解说　$n!$ 中素数 $p$ 的指数用 $\left\lfloor \dfrac{n}{p} \right\rfloor + \left\lfloor \dfrac{n}{p^2} \right\rfloor + \cdots$ 计算，本质是数”$p$、$p^2$、$p^3$……各贡献多少个”。容易卡在：只数 $5$ 的倍数得 $6$，漏了 $25$ 含两个 $5$，所以还要加 $\left\lfloor \dfrac{30}{25} \right\rfloor = 1$。

常用推论

• 平方数的判定：自然数 $N$ 是平方数，当且仅当素因数分解中每个指数都是偶数。推导：$N = m^2$ 时，把 $m$ 的分解平方，指数全部翻倍；反过来指数都是偶数时，指数减半就得到 $m$。
• 约数个数为奇数，当且仅当 $N$ 是平方数。推导：$(a + 1)(b + 1)\cdots$ 是奇数，当且仅当每个 $a + 1, b + 1, \dots$ 都是奇数，即每个指数都是偶数。
• $n!$ 中素数 $p$ 的指数 $= \left\lfloor \dfrac{n}{p} \right\rfloor + \left\lfloor \dfrac{n}{p^2} \right\rfloor + \left\lfloor \dfrac{n}{p^3} \right\rfloor + \cdots$（$\lfloor x \rfloor$ 表示不超过 $x$ 的最大整数）。推导见例 4。
• 约数总和的每个括号可以用等比数列求和：$1 + p + \dots + p^a = \dfrac{p^{a + 1} - 1}{p - 1}$（国内书第 23 章 23.3 节）。
• 由约数个数反求 $N$：约数恰有 6 个的自然数形如 $p^5$ 或 $p^2 q$（因为 $6 = 5 + 1$ 或 $6 = (2 + 1)(1 + 1)$），最小的是 $2^2 \times 3 = 12$。

易错点

• 错在哪：把 1 当成素数，或者在素因数分解里写上 1。 为什么错：素数的定义要求大于 1。把 1 算作素数，分解就不唯一了（$6 = 2 \cdot 3 = 1 \cdot 2 \cdot 3$）。 正确做法：最小的素数是 2；分解时只写大于 1 的素数。
• 错在哪：判定 36 的倍数时拆成“3 的倍数且 12 的倍数”或“6 的倍数且 6 的倍数”。 为什么错：3 和 12 不互素，同时是 3 和 12 的倍数只能推出是 12 的倍数（例如 12 本身不是 36 的倍数）。 正确做法：拆成互素的因数，$36 = 4 \times 9$，再分别用 4 和 9 的判定法。
• 错在哪：540 的约数个数算成 $2 \times 3 \times 1 = 6$。 为什么错：指数可以取 0（例如约数 5 里 2 的指数是 0），每个素因数的指数有 $a + 1$ 种取法。 正确做法：$(2 + 1)(3 + 1)(1 + 1) = 24$。
• 错在哪：约数总和写成 $(2 + 4)(3 + 9 + 27)(5)$。 为什么错：漏了每个括号里的 $p^0 = 1$，等于把不含某个素因数的约数都丢了。 正确做法：每个括号都从 1 写起。

直观理解

把 $72 = 2^3 \cdot 3^2$ 的正约数排成一张表：行是 2 的幂，列是 3 的幂。

	$3^0 = 1$	$3^1 = 3$	$3^2 = 9$
$2^0 = 1$	1	3	9
$2^1 = 2$	2	6	18
$2^2 = 4$	4	12	36
$2^3 = 8$	8	24	72

表格有 $4 \times 3 = 12$ 格，就是约数的个数；每格是“行头 × 列头”，全部加起来等于“行头之和 × 列头之和” $= 15 \times 13 = 195$，就是约数的总和。

判定法的直观：10 除以 9 余 1，100 除以 9 也余 1……所以每一位数字“搬到个位”时，除以 9 的余数不变，整个数除以 9 的余数就等于数字和除以 9 的余数。

关联知识点

• 前置：小学的因数、倍数、质数、合数和 2、3、5 的倍数特征。
• 国内书第 34 章 34.2 节：约数个数公式作为分步乘法计数原理的推论出现，本节补上总和公式和证明。
• 国内书第 23 章 23.3 节：约数总和的每个括号是等比数列求和。
• 后续：8.3 节用素因数分解求最大公约数和最小公倍数。
• 本书第 7 章 場合の数と確率：约数个数本质上是计数问题。
• 本书第 4 章 集合と命題：背理法的经典例子（素数有无穷多个、$\sqrt{2}$ 是无理数）用的就是素因数分解和整除。

8.3 最大公約数・最小公倍数と整数の割り算

说明

最大公約数・最小公倍数：几个整数共同的约数叫公約数，其中最大的叫最大公約数；共同的正的倍数叫公倍数，其中最小的叫最小公倍数。两个整数的最大公约数是 1 时，说它们互いに素（互素）。日本教科书和 EJU 题干一般用文字写「$a$ と $b$ の最大公約数」，本书讲解时为了简洁写成 $\gcd(a, b)$。

用素因数分解求：把两个数分解后，

• 最大公约数：每个公共素因数取较小的指数；
• 最小公倍数：每个出现过的素因数取较大的指数。

例如 $72 = 2^3 \cdot 3^2$，$60 = 2^2 \cdot 3 \cdot 5$：最大公约数 $2^2 \cdot 3 = 12$，最小公倍数 $2^3 \cdot 3^2 \cdot 5 = 360$。

最大公约数与最小公倍数的关系：设自然数 $a$、$b$ 的最大公约数为 $g$，最小公倍数为 $l$，则

$$a = g a', \quad b = g b' \quad (a', b' \text{ は互いに素}), \qquad l = g a' b', \qquad ab = gl.$$

整数の割り算：对整数 $a$ 和正整数 $b$，存在唯一的一对整数 $q$、$r$，使

$$a = bq + r, \qquad 0 \le r < b.$$

$q$ 叫商，$r$ 叫余り（余数）。$r = 0$ 就是 $a$ 能被 $b$ 整除（割り切れる）。$a$ 是负数时余数也要满足 $0 \le r < b$：$-17 = 5 \times (-4) + 3$，$-17$ 除以 5 的余数是 3，不是 $-2$。

余りによる分類：任何整数除以 $m$ 的余数只能是 $0, 1, \dots, m - 1$，所以整数可以按余数分成 $m$ 类。除以 3 时，每个整数都能写成 $3k$、$3k + 1$、$3k + 2$ 之一（$k$ 是整数）；$3k + 2$ 也常写成 $3k - 1$，计算时正负对称更方便。

余りの性質：$a$、$b$ 除以 $m$ 的余数分别是 $r$、$r'$，则

• $a + b$ 除以 $m$ 的余数，等于 $r + r'$ 除以 $m$ 的余数；$a - b$ 同理；
• $ab$ 除以 $m$ 的余数，等于 $rr'$ 除以 $m$ 的余数；
• $a^n$ 除以 $m$ 的余数，等于 $r^n$ 除以 $m$ 的余数。

合同式：$a - b$ 是 $m$ 的倍数时写作 $a \equiv b \pmod{m}$，读作「$m$ を法として $a$ と $b$ は合同」。上面的余数性质用合同式写就是：$a \equiv r$，$b \equiv r'$ 时 $a + b \equiv r + r'$，$ab \equiv rr'$，$a^n \equiv r^n \pmod{m}$。EJU 题干不用这个记号（2017-1、2017-2、2018-2、2019-1、2020-2、2021-1 六份公开过去问全文都没有 $\equiv$ 或 mod），但自己演算时用它能省很多字。注意日本教科书里 $\equiv$ 还表示图形全等（合同），两者靠后面有没有 $\pmod{m}$ 区分。

使用场景

• 求两个数的最大公约数、最小公倍数，数不大、容易分解：用素因数分解取较小、较大指数。
• 已知两个数的最大公约数和最小公倍数，求这两个数：设 $a = ga'$，$b = gb'$，用 $a'$、$b'$ 互素和 $ab = gl$。
• 求一个和、积或高次幂除以 $m$ 的余数：只用各自的余数去算。
• 证明“对所有整数 $n$，某式是 $m$ 的倍数”或讨论平方数的余数：按 $n$ 除以 $m$ 的余数分类。

注意点

• 余数一定满足 $0 \le r < b$，被除数是负数时也一样。
• $ab = gl$ 只对两个数成立，三个数没有这样简单的关系。
• 由 $ab = gl$ 求出的数要回头检验最大公约数确实是 $g$：$ab = gl$ 是必要条件，不是充分条件。
• 按余数分类时类要分全：除以 3 分三类，除以 4 分四类。只分奇偶（除以 2）不能用来证明 3 的倍数。
• EJU 题干的说法：「$a$ を 7 で割ったときの余り」「$a$ を 7 で割ると 3 余る」「$k$ を整数として $n = 3k + 1$ と表される」「互いに素な自然数」。

证明

结论 1：除法的存在和唯一。 把 $b$ 的倍数 $\dots, -b, 0, b, 2b, \dots$ 排在数轴上，它们把数轴分成长度为 $b$ 的小段，$a$ 一定落在某一段 $bq \le a < b(q + 1)$ 里。令 $r = a - bq$，则 $0 \le r < b$，存在性得证。

唯一性：若 $a = bq + r = bq' + r'$，$0 \le r, r' < b$，则 $b(q - q') = r' - r$。右边的绝对值小于 $b$，左边是 $b$ 的倍数，（关键一步：绝对值小于 $b$ 的 $b$ 的倍数只有 0）所以 $r' - r = 0$，$q = q'$。

结论 2：$ab = gl$。 设 $a = ga'$，$b = gb'$，$a'$、$b'$ 互素（若不互素，它们的公约数乘上 $g$ 会是比 $g$ 更大的公约数）。$a$ 和 $b$ 的公倍数必须含有 $g a'$ 和 $g b'$ 的全部素因数，而 $a'$、$b'$ 没有公共素因数，所以最小公倍数是 $l = g a' b'$。于是 $ab = g a' \cdot g b' = g \cdot g a' b' = gl$。

结论 3：余数的乘法性质。 设 $a = mq + r$，$b = mq' + r'$，则

$$ab = m^2 qq' + mqr' + mq'r + rr' = m(mqq' + qr' + q'r) + rr'.$$

前一部分是 $m$ 的倍数，所以 $ab$ 与 $rr'$ 除以 $m$ 的余数相同。加法同理：$a + b = m(q + q') + (r + r')$。把乘法性质反复用就得到 $a^n$ 的性质。

例题

例 1　（场景：用素因数分解求最大公约数、最小公倍数）

問題　$84$ と $120$ の最大公約数と最小公倍数を求めよ。

解答　$84 = 2^2 \cdot 3 \cdot 7$，$120 = 2^3 \cdot 3 \cdot 5$ である。

最大公約数：共通する素因数 $2$ と $3$ について小さい方の指数をとり，$2^2 \cdot 3 = 12$。

最小公倍数：現れる素因数 $2$，$3$，$5$，$7$ について大きい方の指数をとり，$2^3 \cdot 3 \cdot 5 \cdot 7 = 840$。

中文翻译　题目：求 $84$ 和 $120$ 的最大公约数和最小公倍数。解答：$84 = 2^2 \cdot 3 \cdot 7$，$120 = 2^3 \cdot 3 \cdot 5$。最大公约数：公共素因数是 $2$ 和 $3$，取较小指数，$2^2 \cdot 3 = 12$。最小公倍数：所有素因数 $2$、$3$、$5$、$7$ 取较大指数，$2^3 \cdot 3 \cdot 5 \cdot 7 = 840$。

解说　验算：$84 \times 120 = 10080 = 12 \times 840$，即 $ab = gl$ 成立。最大公约数只取公共素因数的较小指数；最小公倍数要把只在一个数里出现的素因数（本题的 $5$、$7$）也取上，且取较大指数。

例 2　（场景：已知最大公约数和最小公倍数求两数）

問題　$2$ つの自然数 $a$，$b$（$a < b$）の最大公約数が $6$，最小公倍数が $72$ であるとき，$a$，$b$ を求めよ。

解答　$a = 6a'$，$b = 6b'$（$a'$，$b'$ は互いに素，$a' < b'$）とおく。最小公倍数は $6a'b' = 72$ であるから，$a'b' = 12$。

$a'b' = 12$ の分け方は $(1, 12)$，$(2, 6)$，$(3, 4)$ で，このうち $(2, 6)$ は互いに素でないから除く。

よって $(a, b) = (6, 72)$ または $(18, 24)$ である。

中文翻译　题目：两个自然数 $a$、$b$（$a < b$）的最大公约数是 $6$，最小公倍数是 $72$，求 $a$、$b$。解答：设 $a = 6a'$，$b = 6b'$，$a'$、$b'$ 互素，$a' < b'$。最小公倍数 $6a'b' = 72$，所以 $a'b' = 12$。$a'b' = 12$ 的分法有 $(1, 12)$、$(2, 6)$、$(3, 4)$，其中 $(2, 6)$ 不互素，舍去。所以 $(a, b) = (6, 72)$ 或 $(18, 24)$。

解说　容易卡在：忘了 $a'$、$b'$ 必须互素，把 $(12, 36)$ 也写进答案；$12$ 和 $36$ 的最大公约数是 $12$，不是 $6$。设 $a = ga'$、$b = gb'$ 时一定要写明 $a'$、$b'$ 互素，最后用“最大公约数是否为 $g$“验算一遍。

例 3　（场景：用余数算和、积的余数）

問題　整数 $a$ を $7$ で割ると $4$ 余り，$b$ を $7$ で割ると $5$ 余る。$a + 2b$，$ab$，$a^2 + b^2$ を $7$ で割った余りをそれぞれ求めよ。

解答　余りだけを使って計算する。

$a + 2b$：$4 + 2 \times 5 = 14$ で，$14$ を $7$ で割った余りは $0$。

$ab$：$4 \times 5 = 20$ で，$20$ を $7$ で割った余りは $6$。

$a^2 + b^2$：$16 + 25 = 41$ で，$41$ を $7$ で割った余りは $6$。

中文翻译　题目：整数 $a$ 除以 $7$ 余 $4$，$b$ 除以 $7$ 余 $5$。求 $a + 2b$、$ab$、$a^2 + b^2$ 分别除以 $7$ 的余数。解答：只用余数计算。$a + 2b$：$4 + 2 \times 5 = 14$，$14$ 除以 $7$ 余 $0$。$ab$：$4 \times 5 = 20$，$20$ 除以 $7$ 余 $6$。$a^2 + b^2$：$16 + 25 = 41$，$41$ 除以 $7$ 余 $6$。

解说　以 $ab$ 为例写出依据：$a = 7s + 4$，$b = 7t + 5$，$ab = 49st + 35s + 28t + 20 = 7(7st + 5s + 4t + 2) + 6$，所以余数等于 $4 \times 5$ 的余数。和、积、幂都可以直接把余数代进去算，不必求出 $a$、$b$ 本身。

例 4　（场景：高次幂的余数）

問題　$7^{100}$ を $5$ で割った余りを求めよ。

解答　$7$ を $5$ で割った余りは $2$ であるから，$7^{100}$ と $2^{100}$ を $5$ で割った余りは同じである。余りが $1$ になる冪を探すと，$2^4 = 16$ は $5$ で割って $1$ 余る。そこで $2^{100} = (2^4)^{25}$ とすると，$5$ で割った余りは $1^{25} = 1$ を $5$ で割った余りに等しい。よって余りは $1$ である。

中文翻译　题目：求 $7^{100}$ 除以 $5$ 的余数。解答：$7$ 除以 $5$ 余 $2$，所以 $7^{100}$ 与 $2^{100}$ 除以 $5$ 的余数相同。找一个余数为 $1$ 的幂：$2^4 = 16$，除以 $5$ 余 $1$。于是 $2^{100} = (2^4)^{25}$，它除以 $5$ 的余数等于 $1^{25} = 1$ 除以 $5$ 的余数。所以余数是 $1$。

解说　容易卡在：一项一项去算 $7^2, 7^3, \dots$ 的实际值。只需要跟踪余数，找到余数是 $1$ 的那一次幂就能整段跳过。周期不一定从 $1$ 次开始，本题 $2^1$ 余 $2$、$2^2$ 余 $4$、$2^3$ 余 $3$、$2^4$ 余 $1$，四次一循环。

例 5　（场景：按余数分类证明整除）

問題　任意の整数 $n$ について，$n^3 + 2n$ が $3$ の倍数であることを証明せよ。

解答　$n^3 + 2n = n(n^2 + 2)$ である。$n$ を $3$ で割った余りで場合分けする（$k$ は整数）。

(1) $n = 3k$ のとき，因数 $n$ が $3$ の倍数である。

(2) $n = 3k + 1$ のとき，$n^2 + 2 = 9k^2 + 6k + 3 = 3(3k^2 + 2k + 1)$ であり，$3$ の倍数である。

(3) $n = 3k + 2$ のとき，$n^2 + 2 = 9k^2 + 12k + 6 = 3(3k^2 + 4k + 2)$ であり，$3$ の倍数である。

以上より，どの場合も $n^3 + 2n$ は $3$ の倍数である。

中文翻译　题目：证明：对任意整数 $n$，$n^3 + 2n$ 是 $3$ 的倍数。解答：$n^3 + 2n = n(n^2 + 2)$。按 $n$ 除以 $3$ 的余数分三类，$k$ 是整数。（1）$n = 3k$：因数 $n$ 是 $3$ 的倍数。（2）$n = 3k + 1$：$n^2 + 2 = 9k^2 + 6k + 3 = 3(3k^2 + 2k + 1)$，是 $3$ 的倍数。（3）$n = 3k + 2$：$n^2 + 2 = 9k^2 + 12k + 6 = 3(3k^2 + 4k + 2)$，是 $3$ 的倍数。三种情况下 $n^3 + 2n$ 都是 $3$ 的倍数。

解说　另一种解法：拆出连续整数之积。$n^3 + 2n = (n^3 - n) + 3n = (n - 1)n(n + 1) + 3n$。连续三个整数里一定有一个是 $3$ 的倍数，所以 $(n - 1)n(n + 1)$ 是 $3$ 的倍数，$3n$ 也是，和是 $3$ 的倍数。分类法总能用，适合看不出怎么变形的时候；凑连续整数之积更短，适合式子里能凑出 $n^3 - n$、$n(n + 1)$ 这类结构的时候。

常用推论

• $ab = gl$，以及 $a = ga'$、$b = gb'$、$l = ga'b'$（$a'$、$b'$ 互素）。推导见本节证明结论 2。
• 平方数除以 3 的余数只能是 0 或 1；除以 4 的余数只能是 0 或 1；奇数的平方除以 8 余 1。推导：$(3k \pm 1)^2 = 3(3k^2 \pm 2k) + 1$；$(2k)^2 = 4k^2$，$(2k + 1)^2 = 4k(k + 1) + 1$，而 $k(k + 1)$ 是偶数，所以 $4k(k + 1)$ 是 8 的倍数。
• 连续 2 个整数之积是 2 的倍数，连续 3 个整数之积是 6 的倍数。推导：连续 3 个整数中必有一个是 3 的倍数、至少一个是 2 的倍数，2 和 3 互素。
• 合同式的运算规则：$a \equiv b$，$c \equiv d \pmod{m}$ 时，$a \pm c \equiv b \pm d$，$ac \equiv bd$，$a^n \equiv b^n \pmod{m}$。推导就是本节证明结论 3。

易错点

• 错在哪：说 $-17$ 除以 5 的余数是 $-2$。 为什么错：余数必须满足 $0 \le r < 5$。 正确做法：$-17 = 5 \times (-4) + 3$，余数是 3。
• 错在哪：已知最大公约数 6、最小公倍数 72，把 $(12, 36)$ 也当答案。 为什么错：$a' = 2$、$b' = 6$ 不互素，12 和 36 的最大公约数是 12。 正确做法：$a'$、$b'$ 必须互素；最后用“最大公约数是否为 $g$“检验一遍。
• 错在哪：求最小公倍数时每个素因数取较小的指数，或者只取公共素因数。 为什么错：最小公倍数要同时是两个数的倍数，每个素因数都要“够用”，所以取较大指数，而且只在一个数里出现的素因数也要取。 正确做法：最大公约数“公共的、取小”，最小公倍数“全部的、取大”。
• 错在哪：证明 $n^3 + 2n$ 是 3 的倍数时，只分 $n$ 为奇数、偶数两类。 为什么错：奇偶分类只说明了除以 2 的情况，跟 3 的倍数没有关系。 正确做法：证明“是 $m$ 的倍数”，就按除以 $m$ 的余数分类。

直观理解

余数像钟表：12 点之后又回到 1 点，所以“现在 9 点，过 100 小时是几点”只要看 100 除以 12 余 4，$9 + 4 = 13$，答案是 1 点。除以 $m$ 的余数也是这样一圈一圈转，加、乘、乘方都只和“在圈上的位置”有关，和转了几圈无关。

最大公约数和最小公倍数用两个圈看最清楚：把两个数的素因数放进两个圈，公共的放在重叠处。重叠部分乘起来是最大公约数；两个圈的全部乘起来是最小公倍数；两个数相乘时重叠部分被算了两次，所以 $ab = gl$。

关联知识点

• 前置：8.2 素因数分解。
• 后续：8.4 互除法建立在”$a = bq + r$“之上。
• 后续：8.5 一次不定方程，“除以 5 余 3、除以 7 余 4”这类条件要化成方程。
• 后续：8.6 记数法，把 10 进制数化成 $n$ 进制就是反复取余数。
• 本书第 10 章 いろいろな式：多项式的除法 $A = BQ + R$ 和剰余の定理，结构与整数的除法相同。
• 本书第 14 章 数列（数学的帰納法）与国内书第 23 章 23.6 节：证明“对所有 $n$ 是某数的倍数”的另一种方法。

8.4 ユークリッドの互除法

说明

原理：自然数 $a$ 除以自然数 $b$，商 $q$、余数 $r$，即 $a = bq + r$，则

$$\gcd(a, b) = \gcd(b, r).$$

做法：用小的数去除大的数，再用余数去除刚才的除数，一直做到余数为 0。最后一个不为 0 的余数（也就是最后一步的除数）就是最大公约数。例如求 42 和 18：

$$42 = 18 \times 2 + 6, \qquad 18 = 6 \times 3 + 0,$$

所以 $\gcd(42, 18) = 6$。

这个方法中文叫辗转相除法（国内旧课标“算法案例”讲过，现行课程没有）。数大到不好分解时，互除法比素因数分解快得多。

倒推（逆算）：把互除法的每一步写成“余数 = 被除数 − 商 × 除数”，从最后一步往回代，可以把最大公约数写成 $ax + by$ 的形式。这是 8.5 节找一次不定方程特解的标准做法。

使用场景

• 两个数都很大、不好素因数分解，求最大公约数：用互除法。
• 约分分子、分母都很大的分数：先用互除法求最大公约数。
• 含文字 $n$ 的两个式子，求最大公约数或证明互素：把”$a = bq + r$“用在式子上，一步步降次。
• 求 $ax + by = 1$（或 $= \gcd(a, b)$）的一组整数解：做完互除法后倒推。

注意点

• 答案是最后一个不为 0 的余数，不是最后一步的商。
• 倒推时每一步都写成“余数 = 被除数 − 商 × 除数”，代入后只合并、不展开成具体数字，最后验算一次。
• 含文字时，$\gcd(n + 4, 3n + 5) = \gcd(n + 4, 7)$ 不等于 7：只有 $n + 4$ 是 7 的倍数时才是 7，否则是 1。
• 日本教科书一般不写 $\gcd$ 记号，答题时写「$a$ と $b$ の最大公約数」。
• EJU 题干的说法：「ユークリッドの互除法を用いて」「$a$ と $b$ の最大公約数を求めよ」「互いに素であることを示せ」。

证明

结论 1：$a = bq + r$ 时，$a$、$b$ 的公约数与 $b$、$r$ 的公约数完全相同。

• 设 $d$ 是 $a$、$b$ 的公约数。$r = a - bq$，$a$ 和 $bq$ 都是 $d$ 的倍数，所以 $r$ 也是。于是 $d$ 是 $b$、$r$ 的公约数。
• 设 $d$ 是 $b$、$r$ 的公约数。$a = bq + r$，同理 $a$ 是 $d$ 的倍数。于是 $d$ 是 $a$、$b$ 的公约数。

（关键一步：两个数都是 $d$ 的倍数，它们的和、差、整数倍也是 $d$ 的倍数。）两组公约数完全相同，最大的那个当然也相同，所以 $\gcd(a, b) = \gcd(b, r)$。

结论 2：互除法一定会停。 每一步的余数都比除数小：$b > r_1 > r_2 > \cdots \ge 0$。一列严格减小的非负整数不可能无穷长，所以有限步后余数变为 0。设余数为 0 的那一步是 $r_{k-1} = r_k q$，则 $\gcd(r_{k-1}, r_k) = r_k$，再由结论 1 一路传回去，$\gcd(a, b) = r_k$。

结论 3：最大公约数可以写成 $ax + by$（$x$、$y$ 是整数）。 第一个余数 $r_1 = a - bq_1$ 是 $a$、$b$ 的整数系数组合；第二个余数 $r_2 = b - r_1 q_2$，代入 $r_1$ 后仍是 $a$、$b$ 的整数系数组合；依此类推，每个余数都是，最后一个非零余数 $\gcd(a, b)$ 也是。

例题

例 1　（场景：大数的最大公约数）

問題　$1147$ と $851$ の最大公約数を求めよ。

解答　ユークリッドの互除法を用いる。 $\begin{aligned} 1147 &= 851 \times 1 + 296, \\ 851 &= 296 \times 2 + 259, \\ 296 &= 259 \times 1 + 37, \\ 259 &= 37 \times 7 + 0. \end{aligned}$ 最後に $0$ でない余りは $37$ であるから，最大公約数は $37$ である。

中文翻译　题目：求 $1147$ 和 $851$ 的最大公约数。解答：用辗转相除法。$1147 = 851 \times 1 + 296$，$851 = 296 \times 2 + 259$，$296 = 259 \times 1 + 37$，$259 = 37 \times 7 + 0$。最后一个不为 $0$ 的余数是 $37$，所以最大公约数是 $37$。

解说　验算：$1147 = 37 \times 31$，$851 = 37 \times 23$。最大公约数是最后一个不为 $0$ 的余数，也就是最后一行的除数，不是最后一步的商 $7$。两个数大到不好分解时，互除法比素因数分解快得多。

例 2　（场景：约分大分数）

問題　$\dfrac{391}{667}$ を既約分数にせよ。

解答　互除法で $667$ と $391$ の最大公約数を求める。 $\begin{aligned} 667 &= 391 \times 1 + 276, \\ 391 &= 276 \times 1 + 115, \\ 276 &= 115 \times 2 + 46, \\ 115 &= 46 \times 2 + 23, \\ 46 &= 23 \times 2 + 0. \end{aligned}$ 最大公約数は $23$。$391 = 23 \times 17$，$667 = 23 \times 29$ であるから，$\dfrac{391}{667} = \dfrac{17}{29}$。

中文翻译　题目：把 $\dfrac{391}{667}$ 化成既约分数。解答：用辗转相除法求 $667$ 和 $391$ 的最大公约数。$667 = 391 \times 1 + 276$，$391 = 276 \times 1 + 115$，$276 = 115 \times 2 + 46$，$115 = 46 \times 2 + 23$，$46 = 23 \times 2 + 0$。最大公约数是 $23$。$391 = 23 \times 17$，$667 = 23 \times 29$，所以 $\dfrac{391}{667} = \dfrac{17}{29}$。

解说　约分大分数时，先求分子分母的最大公约数再除，比逐个小素数试除快。最后检查 $\dfrac{17}{29}$ 的分子分母是否互素；$17$ 和 $29$ 都是素数且不同，已经既约。

例 3　（场景：含文字的式子互素）

問題　$n$ を自然数とする。$5n + 3$ と $2n + 1$ が互いに素であることを証明せよ。

解答　式について互除法を行う。 $\begin{aligned} 5n + 3 &= (2n + 1) \times 2 + (n + 1), \\ 2n + 1 &= (n + 1) \times 1 + n, \\ n + 1 &= n \times 1 + 1. \end{aligned}$ 結論 1 より，$\gcd(5n + 3, 2n + 1) = \gcd(2n + 1, n + 1) = \gcd(n + 1, n) = \gcd(n, 1) = 1$。よって $5n + 3$ と $2n + 1$ は互いに素である。

中文翻译　题目：$n$ 是自然数，证明 $5n + 3$ 与 $2n + 1$ 互素。解答：对式子做辗转相除法。$5n + 3 = (2n + 1) \times 2 + (n + 1)$，$2n + 1 = (n + 1) \times 1 + n$，$n + 1 = n \times 1 + 1$。由结论 1，$\gcd(5n + 3, 2n + 1) = \gcd(2n + 1, n + 1) = \gcd(n + 1, n) = \gcd(n, 1) = 1$。所以两者互素。

解说　含文字的式子做互除法时，把 $n$ 当作字母保留，只对系数做除法，每一步都写成“被除数 = 除数 × 商 + 余数”。最后出现常数 $1$ 就说明互素；互除法一定会停，因为余数的次数严格下降。

例 4　（场景：含文字的式子的最大公约数）

問題　$n + 4$ と $3n + 5$ の最大公約数が $7$ となる最小の自然数 $n$ を求めよ。

解答　$3n + 5 = (n + 4) \times 3 - 7$ であるから，$\gcd(3n + 5, n + 4) = \gcd(n + 4, 7)$。$7$ は素数であるから，$\gcd(n + 4, 7)$ は $1$ か $7$ のどちらかで，$7$ になるのは $n + 4$ が $7$ の倍数のときである。最小の自然数は $n = 3$（このとき $n + 4 = 7$，$3n + 5 = 14$）。

中文翻译　题目：求使 $n + 4$ 与 $3n + 5$ 的最大公约数为 $7$ 的最小自然数 $n$。解答：$3n + 5 = (n + 4) \times 3 - 7$，所以 $\gcd(3n + 5, n + 4) = \gcd(n + 4, 7)$。$7$ 是素数，$\gcd(n + 4, 7)$ 只能是 $1$ 或 $7$，等于 $7$ 当且仅当 $n + 4$ 是 $7$ 的倍数。最小的自然数 $n$ 是 $n = 3$（此时 $n + 4 = 7$，$3n + 5 = 14$）。

解说　容易卡在：写出 $\gcd(n + 4, 7)$ 就以为最大公约数总是 $7$。化到 $\gcd(\text{式子}, \text{常数})$ 后，还要讨论式子能否被这个常数的约数整除；本题 $7$ 是素数，所以只有“是 $7$ 的倍数”和“不是”两种。

例 5　（场景：倒推求 $ax + by = 1$ 的一组解）

問題　$37x + 13y = 1$ を満たす整数 $x$，$y$ の組を $1$ つ求めよ。

解答　まず互除法を行い，各段を「余り = …」の形に書き換える。 $\begin{aligned} 37 &= 13 \times 2 + 11 &\Longrightarrow\ 11 &= 37 - 13 \times 2, \\ 13 &= 11 \times 1 + 2 &\Longrightarrow\ 2 &= 13 - 11 \times 1, \\ 11 &= 2 \times 5 + 1 &\Longrightarrow\ 1 &= 11 - 2 \times 5. \end{aligned}$ 最後の行から逆に代入する。 $\begin{aligned} 1 &= 11 - 2 \times 5 = 11 - (13 - 11) \times 5 = 11 \times 6 - 13 \times 5 \\ &= (37 - 13 \times 2) \times 6 - 13 \times 5 = 37 \times 6 - 13 \times 17. \end{aligned}$ よって $x = 6$，$y = -17$ は $1$ 組の解である。

中文翻译　题目：求满足 $37x + 13y = 1$ 的一组整数 $x$、$y$。解答：先做辗转相除法，每一步改写成“余数 = …”：$37 = 13 \times 2 + 11$，即 $11 = 37 - 13 \times 2$；$13 = 11 \times 1 + 2$，即 $2 = 13 - 11 \times 1$；$11 = 2 \times 5 + 1$，即 $1 = 11 - 2 \times 5$。从最后一行往回代：$1 = 11 - 2 \times 5 = 11 - (13 - 11) \times 5 = 11 \times 6 - 13 \times 5 = (37 - 13 \times 2) \times 6 - 13 \times 5 = 37 \times 6 - 13 \times 17$。所以 $x = 6$，$y = -17$ 是一组解。

解说　验算：$37 \times 6 - 13 \times 17 = 222 - 221 = 1$。容易卡在：代回时把 $11$、$13$、$37$ 当成普通数字乘开。要把它们当成“字母”保留，只合并系数。另一种解法：只看除以 $13$ 的余数。$37x + 13y = 1$ 说明 $37x$ 除以 $13$ 余 $1$。$37$ 除以 $13$ 余 $11$，依次试 $x = 1, 2, \dots$：$11x$ 为 $11$、$22$、$33$、$44$、$55$、$66$，除以 $13$ 的余数为 $11$、$9$、$7$、$5$、$3$、$1$，到 $x = 6$ 余 $1$。代回得 $13y = 1 - 222 = -221$，$y = -17$。系数小（$13$ 以内试几次就到）时试余数更快；系数大时试的次数多，倒推互除法的步数却只和位数有关，更可靠。

常用推论

• 对任意整数 $k$，$\gcd(a, b) = \gcd(a - kb, b)$。含文字时就用它减去倍数降次。推导：同本节证明结论 1，把 $q$ 换成任意整数 $k$。
• 存在整数 $x$、$y$ 使 $ax + by = \gcd(a, b)$；特别地，$a$、$b$ 互素当且仅当存在整数 $x$、$y$ 使 $ax + by = 1$。推导：本节证明结论 3；反方向是因为 $a$、$b$ 的公约数整除 $ax + by = 1$，只能是 $\pm 1$。
• 相邻两个整数 $n$ 与 $n + 1$ 一定互素：$\gcd(n + 1, n) = \gcd(1, n) = 1$。

易错点

• 错在哪：把互除法最后一行的商当成最大公约数（例 1 写成 7）。 为什么错：最大公约数是余数链条的终点，商只是中间结果。 正确做法：取最后一个不为 0 的余数，也就是最后一行的除数（例 1 是 37）。
• 错在哪：倒推时符号弄乱，得到 $37 \times 6 + 13 \times 17$ 之类的结果。 为什么错：每一步“余数 = 被除数 − 商 × 除数”带着减号，代入时括号外的负号要分配进去。 正确做法：每一步都加括号代入，合并完立刻验算 $ax + by$ 是否等于 1。
• 错在哪：由 $\gcd(n + 4, 3n + 5) = \gcd(n + 4, 7)$ 断定最大公约数是 7。 为什么错：$\gcd(n + 4, 7)$ 还取决于 $n + 4$ 是不是 7 的倍数，例如 $n = 1$ 时 $\gcd(5, 8) = 1$。 正确做法：化到 $\gcd(\text{式子}, \text{常数})$ 后，再讨论式子能否被这个常数（的约数）整除。

直观理解

把 $a \times b$ 的长方形铺满同样大小的正方形瓷砖，瓷砖最大能多大？答案就是 $\gcd(a, b)$。互除法就是照着这个画面做：先从长方形里切掉尽可能多的 $b \times b$ 正方形，剩下一个窄条；再从窄条里切掉尽可能多的正方形……直到正好切完。最后那种正方形的边长能铺满之前每一块，所以它就是最大公约数。上面 42 × 18 的图里，先切出两块 18 × 18，剩下 6 × 18，正好切成三块 6 × 6。

关联知识点

• 前置：8.3 整数的除法 $a = bq + r$。
• 后续：8.5 一次不定方程，系数大时用倒推互除法找特解。
• 国内旧课标“算法案例”（辗转相除法、更相减损术）讲的是同一件事，现行国内书没有。
• 本书第 10 章 いろいろな式：多项式也能做带余除法，形式上与本节一样。

8.5 1次不定方程式

说明

$a$、$b$、$c$ 是整数（$a$、$b$ 不为 0），求方程

$$ax + by = c$$

的整数解 $(x, y)$。方程个数少于未知数个数，实数解有无穷多，限定“整数”之后才成为问题，所以叫不定方程式。

有没有解：$ax + by = c$ 有整数解，当且仅当 $\gcd(a, b)$ 整除 $c$。例如 $6x + 9y = 4$：左边总是 3 的倍数，右边 4 不是，所以没有整数解。

解法（$a$、$b$ 互素时；不互素就先两边除以 $\gcd(a, b)$）：

1. 找一组解 $(x_0, y_0)$，称为特殊解（日本教科书说「1 組の解」）。系数小时观察，系数大时用 8.4 节的倒推互除法。
2. 两式相减：$ax + by = c$ 减去 $ax_0 + by_0 = c$，得

$$a(x - x_0) = -b(y - y_0).$$

3. $a$ 与 $b$ 互素，而 $a(x - x_0)$ 是 $b$ 的倍数，所以 $x - x_0$ 是 $b$ 的倍数，设 $x - x_0 = bk$，代回得 $y - y_0 = -ak$。

一般解：

$$x = x_0 + bk, \qquad y = y_0 - ak \qquad (k \text{ は整数}).$$

记法：$x$ 的增量跟 $y$ 的系数 $b$，$y$ 的增量跟 $x$ 的系数 $a$，而且符号相反。

使用场景

• 求 $ax + by = c$ 的全部整数解，系数小、一眼能看出一组解：观察特解，相减，写一般解。
• 系数大，看不出特解：用互除法倒推出 $ax + by = 1$ 的解，再乘 $c$。
• 加上“正整数”“在某范围内”的条件，或者是买东西、凑钱的应用题：先写一般解，再用不等式定 $k$。
• 题目说“除以 $m$ 余 $r$、除以 $n$ 余 $s$ 的数”：设出两种写法，令其相等，化成一次不定方程。
• 判断方程有没有整数解：看 $\gcd(a, b)$ 是否整除 $c$。

注意点

• 一般解的形式不唯一：特解不同，写出来的式子不同，但表示的是同一组解（只是 $k$ 平移了）。EJU 的誘導通常先指定特解，必须按题目给的特解来写，否则填不进空格。
• $a$、$b$ 不互素时必须先约去公因数，否则一般解的“步长”太大，会漏解。
• 求正整数解时，$x > 0$ 和 $y > 0$ 两个不等式都要解，取 $k$ 的公共部分。
• EJU 题干的说法：「$k$ を整数として」「すべての整数解は〜と表される」「〜を満たす整数の組 $(x, y)$」「正の整数の組」「$x$ が 2 桁の自然数となるもの」。

证明

引理：$a$、$b$ 互素，且 $a$ 整除 $bc$，则 $a$ 整除 $c$。

由 8.4 节常用推论，存在整数 $s$、$t$ 使 $as + bt = 1$。两边乘 $c$：

$$c = acs + bct.$$

（关键一步：$acs$ 显然是 $a$ 的倍数，$bct$ 因为 $a$ 整除 $bc$ 也是 $a$ 的倍数。）所以 $c$ 是 $a$ 的倍数。

取 $a = p$ 为素数，就得到“素数 $p$ 整除 $bc$ 而不整除 $b$，则 $p$ 整除 $c$”，这正是 8.2 节说的素因数分解唯一性的关键。

一般解的推导：由 $a(x - x_0) = -b(y - y_0)$，$b$ 整除 $a(x - x_0)$，而 $a$、$b$ 互素，由引理 $b$ 整除 $x - x_0$，设 $x - x_0 = bk$。代回得 $abk = -b(y - y_0)$，两边除以 $b$ 得 $y - y_0 = -ak$。反过来，对任意整数 $k$，

$$a(x_0 + bk) + b(y_0 - ak) = ax_0 + by_0 = c,$$

所以这些确实全是解，不多也不少。

有解的条件：记 $g = \gcd(a, b)$。若有整数解，$ax + by$ 是 $g$ 的倍数，所以 $g$ 整除 $c$（必要性）。反过来，若 $c = gm$，由 8.4 节存在 $as + bt = g$，于是 $a(sm) + b(tm) = c$，有解（充分性）。

例题

例 1　（场景：观察特解，写全部整数解）

問題　$11x + 7y = 5$ の整数解をすべて求めよ。

解答　まず $11x + 7y = 1$ の解を探すと，$11 \times 2 + 7 \times (-3) = 1$。両辺を $5$ 倍して，特別解 $x_0 = 10$，$y_0 = -15$ を得る。

もとの方程式と辺々引くと $11(x - 10) = -7(y + 15)$。$11$ と $7$ は互いに素であるから，$x - 10 = 7k$，代回して $y + 15 = -11k$。よって整数解はすべて $x = 7k + 10$，$y = -11k - 15$（$k$ は整数） と表される。

中文翻译　题目：求 $11x + 7y = 5$ 的全部整数解。解答：先找 $11x + 7y = 1$ 的解：$11 \times 2 + 7 \times (-3) = 1$。两边乘 $5$，得特解 $x_0 = 10$，$y_0 = -15$。与原方程相减：$11(x - 10) = -7(y + 15)$。$11$ 与 $7$ 互素，所以 $x - 10 = 7k$，代回得 $y + 15 = -11k$。全部整数解为 $x = 7k + 10$，$y = -11k - 15$（$k$ 是整数）。

解说　也可以直接看出更小的特解 $x_0 = 3$，$y_0 = -4$（$33 - 28 = 5$），得到 $x = 7k + 3$，$y = -11k - 4$。两种写法是同一组解：把前一种的 $k$ 换成 $k - 1$ 就得到后一种。一般解的记法：$x$ 的增量是 $y$ 的系数 $7$，$y$ 的增量是 $x$ 的系数 $11$，符号相反。

例 2　（场景：系数大，用互除法找特解）

問題　$37x + 13y = 5$ の整数解をすべて求めよ。

解答　8.4 節例 5 より $37 \times 6 + 13 \times (-17) = 1$。両辺を $5$ 倍して $37 \times 30 + 13 \times (-85) = 5$。

辺々引くと $37(x - 30) = -13(y + 85)$。$37$ と $13$ は互いに素であるから，$x - 30 = 13k$，$y + 85 = -37k$。よって $x = 13k + 30$，$y = -37k - 85$（$k$ は整数）。

中文翻译　题目：求 $37x + 13y = 5$ 的全部整数解。解答：由 8.4 节例 5，$37 \times 6 + 13 \times (-17) = 1$，两边乘 $5$：$37 \times 30 + 13 \times (-85) = 5$。相减：$37(x - 30) = -13(y + 85)$，$37$ 与 $13$ 互素，$x - 30 = 13k$，$y + 85 = -37k$。所以 $x = 13k + 30$，$y = -37k - 85$（$k$ 是整数）。

解说　取 $k = -2$ 得更小的特解 $(4, -11)$，所以也可以写成 $x = 13k + 4$，$y = -37k - 11$。系数大时先用互除法倒推出一组 $=1$ 的解，再乘右边的常数 $5$；直接观察很难凑出来。写完一般解后，把 $k$ 代回原式验算一次。

例 3　（场景：正整数解的应用题）

問題　$50$ 円切手と $80$ 円切手をそれぞれ少なくとも $1$ 枚ずつ買い，代金の合計をちょうど $1000$ 円にしたい。それぞれ何枚ずつ買えばよいか。すべての場合を求めよ。

解答　$50$ 円切手を $x$ 枚，$80$ 円切手を $y$ 枚とすると，$50x + 80y = 1000$。両辺を $10$ で割って $5x + 8y = 100$。

特別解は $x = 4$，$y = 10$（$20 + 80 = 100$）。辺々引くと $5(x - 4) = -8(y - 10)$ で，$5$ と $8$ は互いに素であるから，$x - 4 = 8k$，$y - 10 = -5k$。よって $x = 8k + 4$，$y = -5k + 10$。

条件 $x \geqq 1$ より $8k + 4 \geqq 1$，すなわち $k \geqq 0$。条件 $y \geqq 1$ より $-5k + 10 \geqq 1$，すなわち $k \leqq 1$。よって $k = 0$ または $1$ である。

$k = 0$ のとき，$50$ 円切手 $4$ 枚，$80$ 円切手 $10$ 枚。 $k = 1$ のとき，$50$ 円切手 $12$ 枚，$80$ 円切手 $5$ 枚。

中文翻译　题目：$50$ 円邮票和 $80$ 円邮票各买至少 $1$ 枚，总价恰好 $1000$ 円。各买几枚？列出所有可能。解答：设 $50$ 円买 $x$ 枚，$80$ 円买 $y$ 枚：$50x + 80y = 1000$，两边除以 $10$，$5x + 8y = 100$。特解：$x = 4$，$y = 10$（$20 + 80 = 100$）。相减：$5(x - 4) = -8(y - 10)$，$5$ 与 $8$ 互素，$x - 4 = 8k$，$y - 10 = -5k$：$x = 8k + 4$，$y = -5k + 10$。条件 $x \geqq 1$：$8k + 4 \geqq 1$，$k \geqq -\dfrac{3}{8}$，即 $k \geqq 0$。条件 $y \geqq 1$：$-5k + 10 \geqq 1$，$k \leqq \dfrac{9}{5}$，即 $k \leqq 1$。所以 $k = 0$ 或 $1$：$k = 0$ 时 $50$ 円 $4$ 枚，$80$ 円 $10$ 枚；$k = 1$ 时 $50$ 円 $12$ 枚，$80$ 円 $5$ 枚。

解说　应用题先化成不定方程，求出一般解后，用“每种至少 $1$ 枚”的 $x \geqq 1$、$y \geqq 1$ 两个不等式夹出 $k$ 的范围。$k$ 的范围内有几个整数，就有几组解；最后把每一组的金额加回去验算是否等于 $1000$。

例 4　（场景：两个余数条件）

問題　$5$ で割ると $3$ 余り，$7$ で割ると $4$ 余る最小の $3$ 桁の自然数を求めよ。

解答　求める数を $N = 5x + 3 = 7y + 4$（$x$，$y$ は整数）とおくと，$5x - 7y = 1$。特別解は $x = 3$，$y = 2$（$15 - 14 = 1$）。辺々引くと $5(x - 3) = 7(y - 2)$ で，$5$ と $7$ は互いに素であるから，$x - 3 = 7k$，すなわち $x = 7k + 3$。よって $N = 5(7k + 3) + 3 = 35k + 18$。

条件を満たす数は $18$，$53$，$88$，$123$，$\dots$ であり，最小の $3$ 桁の数は $35 \times 3 + 18 = 123$ である。

中文翻译　题目：求除以 $5$ 余 $3$、除以 $7$ 余 $4$ 的最小三位自然数。解答：设这个数 $N = 5x + 3 = 7y + 4$（$x$、$y$ 是整数），得 $5x - 7y = 1$。特解 $x = 3$，$y = 2$（$15 - 14 = 1$）。相减：$5(x - 3) = 7(y - 2)$，$5$ 与 $7$ 互素，$x - 3 = 7k$，即 $x = 7k + 3$。所以 $N = 5(7k + 3) + 3 = 35k + 18$。满足条件的数是 $18$、$53$、$88$、$123$、……，最小的三位数是 $35 \times 3 + 18 = 123$。

解说　验算：$123 = 5 \times 24 + 3 = 7 \times 17 + 4$。另一种解法：直接列。除以 $7$ 余 $4$ 的数：$4$、$11$、$18$、$25$、……，逐个看除以 $5$ 的余数，$18$ 除以 $5$ 余 $3$，是第一个。$5$ 和 $7$ 互素，满足两个条件的数每隔 $5 \times 7 = 35$ 重复一次，所以是 $18 + 35k$，同样得到 $123$。除数小的时候列举更快；除数大或题目要求写出一般形式时，用不定方程更稳。

例 5　（场景：判断有没有整数解）

問題　$6x + 9y = 4$ と $6x + 9y = 15$ はそれぞれ整数解をもつか。もつ場合はすべて求めよ。

解答　$6$ と $9$ の最大公約数は $3$ である。

$6x + 9y = 4$：$3$ は $4$ を割り切らないから，整数解はない。

$6x + 9y = 15$：$3$ は $15$ を割り切るから解がある。両辺を $3$ で割ると $2x + 3y = 5$。特別解は $x = 1$，$y = 1$。辺々引くと $2(x - 1) = -3(y - 1)$ で，$x - 1 = 3k$，$y - 1 = -2k$。よって $x = 3k + 1$，$y = -2k + 1$（$k$ は整数）。

中文翻译　题目：$6x + 9y = 4$ 和 $6x + 9y = 15$ 有没有整数解？有的话求出全部。解答：$6$ 和 $9$ 的最大公约数是 $3$。$6x + 9y = 4$：$3$ 不整除 $4$，没有整数解。$6x + 9y = 15$：$3$ 整除 $15$，有解。两边除以 $3$：$2x + 3y = 5$，特解 $x = 1$，$y = 1$。相减得 $2(x - 1) = -3(y - 1)$，$x - 1 = 3k$，$y - 1 = -2k$，即 $x = 3k + 1$，$y = -2k + 1$。

解说　容易卡在：不约去 $3$，直接写 $x = 9k + 1$，$y = -6k + 1$，这样会漏掉一部分解，例如 $(4, -1)$。判断有没有解用 $\gcd(a, b)$ 是否整除 $c$；有解时先两边除以 $\gcd$，化成互素系数的方程再求一般解。

常用推论

• $a$、$b$ 互素时，相邻两个解的 $x$ 相差 $|b|$、$y$ 相差 $|a|$，所以直线 $ax + by = c$ 上的格点等距排列（见上图）。
• $a$、$b$ 是正数时，满足 $x > 0$、$y > 0$ 的解只有有限个：一般解代入两个不等式，得到 $k$ 的一个有界范围，解的个数就是这个范围里整数的个数（例 3）。
• 除以 $m$ 余 $r$、除以 $n$ 余 $s$ 的整数（$m$、$n$ 互素）形如 $mnk + N_0$：满足条件的数每隔 $mn$ 出现一次。推导见例 4。

易错点

• 错在哪：$5x + 8y = 100$ 的一般解写成 $x = 4 + 5k$，$y = 10 - 8k$。 为什么错：代回去 $5(4 + 5k) + 8(10 - 8k) = 100 - 39k$，不等于 100。$x$ 的步长应该是对方的系数。 正确做法：$x$ 跟 $b$、$y$ 跟 $a$，即 $x = 4 + 8k$，$y = 10 - 5k$；写完代回原方程，$k$ 必须完全消掉。
• 错在哪：$6x + 9y = 15$ 不约分，一般解写成 $x = 1 + 9k$，$y = 1 - 6k$。 为什么错：引理要求系数互素，6 和 9 不互素，这样写会漏解。 正确做法：先除以最大公约数，化成 $2x + 3y = 5$ 再解。
• 错在哪：自己求出的一般解和答案形式不同（例如 $x = 7k + 3$ 与 $x = 7k + 10$），就认为做错了；或者在 EJU 的空格里填自己找的特解。 为什么错：特解不同，一般解的常数项就不同，两者表示同一组解。但 EJU 填空的形式由誘導里给定的特解决定。 正确做法：自己解题时用任何特解都对；做 EJU 誘導题时，用题目前一问得到的那组特解写一般解。

直观理解

$ax + by = c$ 在坐标平面上是一条直线，整数解就是直线经过的格点（横纵坐标都是整数的点）。找到一个格点后，沿直线每走“横 $b$、纵 $-a$“一步就踩到下一个格点，中间不会有别的格点（$a$、$b$ 互素时）。一般解 $x = x_0 + bk$，$y = y_0 - ak$ 就是”从起点出发走 $k$ 步”。

关联知识点

• 前置：8.4 互除法（找特解、互素的判定）。
• 前置：8.3 余数，“除以 $m$ 余 $r$“写成 $mk + r$。
• 本书第 11 章 図形と方程式：直线的方程，整数解就是直线上的格点。
• 本书第 7 章 場合の数と確率：解的个数问题，如“满足条件的组 $(x, y)$ 有几组”。

8.6 記数法

说明

$n$ 進法：用 $0, 1, \dots, n - 1$ 这 $n$ 个数字，每一位的“位权”是 $n$ 的幂。写法是在数的右下角加 $(n)$：

$$abcd_{(n)} = a \cdot n^3 + b \cdot n^2 + c \cdot n + d.$$

例如 $1011_{(2)} = 8 + 0 + 2 + 1 = 11$。这样表示的数叫 $n$ 進数（2 進数、5 進数等），我们平常用的是 10 進法，10 进制数不加下标。

小数：小数点后各位的位权是 $\dfrac{1}{n}, \dfrac{1}{n^2}, \dots$：

$$0.abc_{(n)} = \frac{a}{n} + \frac{b}{n^2} + \frac{c}{n^3}.$$

10 进制整数化成 $n$ 进制：反复除以 $n$，记下余数，直到商为 0，余数从下往上读。例如 87 化成 5 进制：

除法	商	余数
$87 \div 5$	17	2
$17 \div 5$	3	2
$3 \div 5$	0	3

从下往上读：$87 = 322_{(5)}$。验算：$3 \times 25 + 2 \times 5 + 2 = 87$。

10 进制小数化成 $n$ 进制：反复乘以 $n$，取出整数部分，从上往下读，直到小数部分为 0（或出现循环）。

$n$ 进制化成 $m$ 进制：先化成 10 进制，再化成 $m$ 进制。

$n$ 进制下的加法：逢 $n$ 进一。例如 $1011_{(2)} + 111_{(2)} = 10010_{(2)}$（$11 + 7 = 18$）。

使用场景

• 把 $n$ 进制数化成 10 进制：按位权展开。
• 把 10 进制整数化成 $n$ 进制：反复除以 $n$，余数倒读。
• 小数的进制转换：$n$ 进制小数按位权 $\dfrac{1}{n^k}$ 展开；10 进制小数反复乘 $n$。
• 底数 $n$ 未知，已知某数在 $n$ 进制下的写法和它的值：列关于 $n$ 的方程，再检验数字都小于 $n$。
• 问 $n$ 进制下几位数、某个范围内有多少个数：用 $n^{k-1} \le N < n^k$。

注意点

• $n$ 进制里每一位数字只能是 $0$ 到 $n - 1$。$35_{(4)}$ 没有意义。
• $k$ 位数的最高位位权是 $n^{k-1}$，不是 $n^k$。
• 整数部分“除、余数倒读”，小数部分“乘、整数顺读”，两者别弄混。
• 一个分数在 10 进制下是有限小数，在别的进制下不一定是：$\dfrac{1}{3} = 0.1_{(3)}$，在 2 进制下却是无限循环小数。
• EJU 题干的说法：「5 進法で表された数 $2134_{(5)}$」「10 進法で表すと」「2 進法で表すと何桁の数か」「$n$ 進法で表すと 3 桁になる」。

证明

结论 1：反复除法给出 $n$ 进制的各位数字。 设 $N = d_k n^k + \dots + d_1 n + d_0$（$0 \le d_i \le n - 1$）。把它写成

$$N = n(d_k n^{k-1} + \dots + d_1) + d_0, \qquad 0 \le d_0 < n,$$

由 8.3 节除法的唯一性，$N$ 除以 $n$ 的余数就是 $d_0$（末位），商就是“去掉末位后的数” $d_k n^{k-1} + \dots + d_1$。（关键一步：除法的商和余数唯一，所以余数只能是末位。）对商重复同样的事，依次得到 $d_1, d_2, \dots$。先得到的是低位，所以要从下往上读。同一个论证也说明 $n$ 进制表示是唯一的。

结论 2：反复乘 $n$ 给出小数的各位。 设 $x = \dfrac{d_1}{n} + \dfrac{d_2}{n^2} + \cdots$，则

$$nx = d_1 + \left(\frac{d_2}{n} + \frac{d_3}{n^2} + \cdots\right),$$

括号里小于 1（各位都取最大值 $n - 1$ 时也不超过 1，有限小数时严格小于 1），所以 $nx$ 的整数部分就是 $d_1$。对剩下的小数部分重复，依次得到 $d_2, d_3, \dots$。

结论 3：$n$ 进制 $k$ 位数的范围。 最小的 $k$ 位数是 $100\cdots0_{(n)} = n^{k-1}$；最大的是各位都是 $n - 1$：

$$(n - 1)(n^{k-1} + \dots + n + 1) = n^k - 1.$$

所以 $n$ 进制下 $k$ 位的自然数 $N$ 满足 $n^{k-1} \le N < n^k$。

例题

例 1　（场景：$n$ 进制化成 10 进制）

問題　$1201_{(3)}$ を $10$ 進法で表せ。

解答　$1201_{(3)} = 1 \times 3^3 + 2 \times 3^2 + 0 \times 3 + 1 = 27 + 18 + 0 + 1 = 46$。

中文翻译　题目：把 $1201_{(3)}$ 化成 $10$ 进制。解答：$1201_{(3)} = 1 \times 3^3 + 2 \times 3^2 + 0 \times 3 + 1 = 27 + 18 + 0 + 1 = 46$。

解说　另一种解法：从最高位起“乘 $3$ 加下一位”：$1 \to 1 \times 3 + 2 = 5 \to 5 \times 3 + 0 = 15 \to 15 \times 3 + 1 = 46$。位数多时这样算不用先算 $3^k$，心算更不容易错；位数少时直接展开更直观。注意最高位的位权是 $3^3$（$4$ 位数），不是 $3^4$。

例 2　（场景：10 进制整数化成 $n$ 进制）

問題　$87$ を $2$ 進法と $5$ 進法で表せ。

解答　$2$ 進法：$2$ で繰り返し割る。 $87 = 2 \times 43 + 1$，$43 = 2 \times 21 + 1$，$21 = 2 \times 10 + 1$，$10 = 2 \times 5 + 0$，$5 = 2 \times 2 + 1$，$2 = 2 \times 1 + 0$，$1 = 2 \times 0 + 1$。 余りを下から順に読むと $87 = 1010111_{(2)}$ である。

$5$ 進法：同じように繰り返し割ると，$87 = 322_{(5)}$ である。

中文翻译　题目：把 $87$ 分别化成 $2$ 进制和 $5$ 进制。解答：$2$ 进制：反复除以 $2$。$87 = 2 \times 43 + 1$，$43 = 2 \times 21 + 1$，$21 = 2 \times 10 + 1$，$10 = 2 \times 5 + 0$，$5 = 2 \times 2 + 1$，$2 = 2 \times 1 + 0$，$1 = 2 \times 0 + 1$。余数从下往上读：$87 = 1010111_{(2)}$。$5$ 进制：见本节说明，$87 = 322_{(5)}$。

解说　验算：$1010111_{(2)} = 64 + 16 + 4 + 2 + 1 = 87$。容易卡在：余数从上往下读，写成 $1110101_{(2)}$（$= 117$）。整数部分的转换是“除、余数倒读”，第一次除得到的余数是个位，要写在最右边。

例 3　（场景：小数的进制转换）

問題　(1) $10$ 進法の $0.375$ を $2$ 進法で表せ。 (2) $0.12_{(3)}$ を $10$ 進法の分数で表せ。

解答　(1) $2$ を繰り返し掛けて整数部分を取る。 $0.375 \times 2 = 0.75$（整数部分 $0$），$0.75 \times 2 = 1.5$（整数部分 $1$），$0.5 \times 2 = 1$（整数部分 $1$，小数部分 $0$ で終了）。 整数部分を上から順に読むと $0.375 = 0.011_{(2)}$ である。

(2) $0.12_{(3)} = \dfrac{1}{3} + \dfrac{2}{9} = \dfrac{5}{9}$。

中文翻译　题目：（1）把 $10$ 进制的 $0.375$ 化成 $2$ 进制；（2）把 $0.12_{(3)}$ 化成 $10$ 进制分数。解答：（1）反复乘 $2$，取整数部分：$0.375 \times 2 = 0.75$，整数部分 $0$；$0.75 \times 2 = 1.5$，整数部分 $1$；$0.5 \times 2 = 1$，整数部分 $1$，小数部分为 $0$，停止。从上往下读：$0.375 = 0.011_{(2)}$。（2）$0.12_{(3)} = \dfrac{1}{3} + \dfrac{2}{9} = \dfrac{5}{9}$。

解说　验算：$\dfrac{1}{4} + \dfrac{1}{8} = \dfrac{3}{8} = 0.375$。整数部分“除、余数倒读”，小数部分“乘、整数顺读”，两者别弄混；小数部分的位权是 $\dfrac{1}{n^k}$，乘 $n$ 才能把下一位移到整数部分。

例 4　（场景：底数未知）

問題　ある自然数を $n$ 進法で表すと $123_{(n)}$，$10$ 進法で表すと $38$ になる。$n$ を求めよ。

解答　$123_{(n)} = n^2 + 2n + 3 = 38$ であるから，$n^2 + 2n - 35 = 0$，$(n + 7)(n - 5) = 0$。$n$ は自然数だから $n = 5$。各位の数字 $1$，$2$，$3$ はすべて $5$ より小さいから，この解は適する。よって $n = 5$。

中文翻译　题目：某个自然数用 $n$ 进制写成 $123_{(n)}$，用 $10$ 进制写是 $38$。求 $n$。解答：$123_{(n)} = n^2 + 2n + 3 = 38$，即 $n^2 + 2n - 35 = 0$，$(n + 7)(n - 5) = 0$。$n$ 是自然数，$n = 5$。检验：数字 $1$、$2$、$3$ 都小于 $5$，符合。所以 $n = 5$。

解说　容易卡在：忘了检验“每个数字小于 $n$”。若解出的 $n$ 不大于某一位数字，这个解要舍去。$n$ 进制里每一位只能是 $0$ 到 $n - 1$，本题若解出 $n = 2$ 或 $n = 3$，数字 $3$ 就不合法。

例 5　（场景：位数与个数）

問題　(1) $2$ 進法で $7$ 桁になる自然数は何個あるか。 (2) $3$ 進法で $4$ 桁になる自然数を $10$ 進法で表すと，どのような範囲になるか。

解答　(1) $2^6 \leqq N < 2^7$，すなわち $64 \leqq N \leqq 127$ であるから，$127 - 64 + 1 = 64$ 個。

(2) $3^3 \leqq N < 3^4$，すなわち $27 \leqq N \leqq 80$。

中文翻译　题目：（1）$2$ 进制下是 $7$ 位数的自然数有多少个？（2）$3$ 进制下是 $4$ 位数的自然数，用 $10$ 进制表示在什么范围？解答：（1）$2^6 \leqq N < 2^7$，即 $64 \leqq N \leqq 127$，共 $127 - 64 + 1 = 64$ 个。（2）$3^3 \leqq N < 3^4$，即 $27 \leqq N \leqq 80$。

解说　$n$ 进制下 $k$ 位的自然数 $N$ 满足 $n^{k-1} \leqq N < n^k$。数个数时注意两端：最小是 $n^{k-1}$，最大是 $n^k - 1$，所以个数是 $n^k - n^{k-1} = (n - 1)n^{k-1}$。第 (1) 问用这个公式就是 $(2 - 1) \cdot 2^6 = 64$。

常用推论

• $n$ 进制下 $k$ 位的自然数共有 $n^k - n^{k-1} = (n - 1)n^{k-1}$ 个。推导：本节证明结论 3。
• $N$ 在 $n$ 进制下的末位，等于 $N$ 除以 $n$ 的余数；末位是 0 当且仅当 $N$ 是 $n$ 的倍数。推导：本节证明结论 1。
• $n$ 进制下，$N$ 是 $n - 1$ 的倍数当且仅当各位数字之和是 $n - 1$ 的倍数。这就是 10 进制里“9 的倍数看数字和”的推广，证明同 8.2 节结论 1（$n^k - 1$ 是 $n - 1$ 的倍数）。
• 既约分数 $\dfrac{p}{q}$ 在 $n$ 进制下是有限小数，当且仅当 $q$ 的素因数都是 $n$ 的素因数。例如 $\dfrac{3}{8}$ 在 2 进制下有限，$\dfrac{1}{5}$ 在 2 进制下无限。

易错点

• 错在哪：87 化成 5 进制写成 $223_{(5)}$。 为什么错：第一次除法得到的余数是个位，要写在最右边。 正确做法：余数从下往上读，$322_{(5)}$；写完按位权展开验算一次。
• 错在哪：$1201_{(3)}$ 按 $1 \times 3^4 + 2 \times 3^3 + \cdots$ 展开。 为什么错：4 位数的最高位位权是 $3^3$，个位的位权是 $3^0 = 1$。 正确做法：从个位往左数，位权依次是 $n^0, n^1, n^2, \dots$。
• 错在哪：小数 0.375 化 2 进制时也用除法、余数倒读。 为什么错：小数部分的位权是 $\dfrac{1}{n^k}$，要乘 $n$ 才能把下一位“移”到整数部分。 正确做法：小数部分反复乘 $n$，整数部分从上往下读。

直观理解

$n$ 进制就是“满 $n$ 个打一包”：5 进制里，5 个一捆，5 捆一箱，5 箱一车。$322_{(5)}$ 就是 3 箱、2 捆、2 个。反复除以 5 就是先把东西 5 个一捆捆起来（剩下的零头是个位），再把捆 5 捆一箱装起来（剩下的零捆是第二位）……所以先得到的是个位。

2 进制可以想成一组砝码 1、2、4、8、16、…，每种只有一个，用或不用。$87 = 64 + 16 + 4 + 2 + 1$，用到的砝码记 1，没用的记 0，就是 $1010111_{(2)}$。

关联知识点

• 前置：8.3 整数的除法（余数唯一，保证转换结果唯一）。
• 前置：8.2 倍数判定法（10 进制的 9 判定是本节 $n - 1$ 判定的特例）。
• 后续：本书第 12 章 指数関数・対数関数：用常用对数求 10 进制位数，$N$ 是 $k$ 位数 $\iff 10^{k-1} \le N < 10^k$，和本节结论 3 完全同构。
• 国内书第 23 章 23.3 节：$k$ 位数的最大值 $n^k - 1$ 用的是等比数列求和。

8.7 题型与答法

EJU 的整数题固定出现在コース1 的大问 Ⅲ，一个大问只考一个主题。查 2017–2021 年公开的六份过去问，コース1 Ⅲ 依次是：$x^2 - y^2 = n$ 的整数解（2017 年第 1 回）、自然数集合与平方（2017 年第 2 回）、1400 的素因数分解与约数（2018 年第 2 回）、$\dfrac{m}{3} + \dfrac{n}{7}$ 最接近 $\sqrt{2}$ 的正整数 $m$、$n$（2019 年第 1 回）、一次不定方程 $14a + 9b = 147$（2020 年第 2 回）、5 进制与 9 进制的记数法（2021 年第 1 回）。コース2 的シラバス也包括本章，但这几年的コース2 题里没有整数大题（コース2 的 Ⅰ 与コース1 共用，Ⅱ 以后考数学Ⅱ、Ⅲ、Ｂ、Ｃ 的内容），准备时以コース1 的题型为主。2026 年新シラバス下还没有公开样题。

誘導的典型骨架：

• 一次不定方程：(1) 用倍数关系或互除法得一组解 →(2)「$k$ を整数として」写一般解 →(3) 加条件（正整数、位数、$x + y$ 最小等）定 $k$，数个数或求最值。
• 记数法：(1) $n$ 进制化 10 进制 →(2) 10 进制化 $n$ 进制 →(3) 同一个数在两种进制下的写法满足某关系，列方程求数字。
• 约数、余数：(1) 素因数分解，约数个数与总和 →(2) 最大公约数、最小公倍数 →(3) 余数计算。

填涂提醒：负数占两格以上，第一格填「－」（如 $y = -5$ 填进 $\fbox{BC}$ 是「－」「5」）；一般解里 $k$ 的系数是两位数时占两格；系数是 1 也要填出来。

問題 1　（1次不定方程式）

方程式

$$43x + 17y = 1 \quad \cdots\cdots ①$$

を満たす整数 $x$，$y$ について考える。

(1) ユークリッドの互除法を用いると，① を満たす整数の組の 1 つとして $x = \fbox{A}$，$y = \fbox{BC}$ が得られる。

(2) ① のすべての整数解は，$k$ を整数として $x = \fbox{DE}\,k + \fbox{F}$，$y = -\fbox{GH}\,k - \fbox{I}$ と表される。

(3) 方程式 $43x + 17y = 5$ の整数解のうち，$x$ が 2 桁の正の整数であるものは $\fbox{J}$ 個ある。そのうち $y$ の値が最も大きいものは $x = \fbox{KL}$，$y = \fbox{MNO}$ である。

解答　(1) 互除法より $43 = 17 \times 2 + 9$，$17 = 9 \times 1 + 8$，$9 = 8 \times 1 + 1$。逆に代入すると $1 = 9 - 8 = 9 - (17 - 9) = 9 \times 2 - 17 = (43 - 17 \times 2) \times 2 - 17 = 43 \times 2 - 17 \times 5$。 よって $x = 2$，$y = -5$ であり，$\fbox{A} = 2$，$\fbox{BC}$ には「－」と「5」を入れる。

(2) $43(x - 2) = -17(y + 5)$ で，$43$ と $17$ は互いに素であるから，$x - 2 = 17k$，$y + 5 = -43k$。よって $x = 17k + 2$，$y = -43k - 5$ であり，$\fbox{DE} = 1, 7$，$\fbox{F} = 2$，$\fbox{GH} = 4, 3$，$\fbox{I} = 5$。

(3) (1) より $43 \times 10 + 17 \times (-25) = 5$ であるから，(2) と同様に $x = 17k + 10$，$y = -43k - 25$。$10 \leqq 17k + 10 \leqq 99$ より $0 \leqq k \leqq \dfrac{89}{17}$ で，$k = 0, 1, 2, 3, 4, 5$ の $6$ 個。$y = -43k - 25$ は $k$ が大きいほど小さいから，$k = 0$ のとき $y$ が最大で，$x = 10$，$y = -25$。 よって $\fbox{J} = 6$，$\fbox{KL} = 1, 0$，$\fbox{MNO}$ には「－」と「2」と「5」を入れる。

中文翻译　题目：考虑满足方程 $43x + 17y = 1$（①）的整数 $x$、$y$。（1）用欧几里得互除法，得到满足 ① 的一组整数 $x = \fbox{A}$，$y = \fbox{BC}$。（2）① 的全部整数解可以用整数 $k$ 表示为 $x = \fbox{DE}\,k + \fbox{F}$，$y = -\fbox{GH}\,k - \fbox{I}$。（3）方程 $43x + 17y = 5$ 的整数解中，$x$ 是两位正整数的有 $\fbox{J}$ 个，其中 $y$ 最大的是 $x = \fbox{KL}$，$y = \fbox{MNO}$。解答：（1）互除法：$43 = 17 \times 2 + 9$，$17 = 9 \times 1 + 8$，$9 = 8 \times 1 + 1$。倒推：$1 = 9 - 8 = 9 - (17 - 9) = 9 \times 2 - 17 = (43 - 17 \times 2) \times 2 - 17 = 43 \times 2 - 17 \times 5$。所以 $x = 2$，$y = -5$，$\fbox{A} = 2$，$\fbox{BC}$ 填「－」和「5」。（2）$43(x - 2) = -17(y + 5)$，$43$ 与 $17$ 互素，$x - 2 = 17k$，$y + 5 = -43k$，即 $x = 17k + 2$，$y = -43k - 5$，所以 $\fbox{DE} = 1, 7$，$\fbox{F} = 2$，$\fbox{GH} = 4, 3$，$\fbox{I} = 5$。（3）由（1），$43 \times 10 + 17 \times (-25) = 5$，同（2）得 $x = 17k + 10$，$y = -43k - 25$。$10 \leqq 17k + 10 \leqq 99$，得 $0 \leqq k \leqq \dfrac{89}{17}$，$k = 0, 1, 2, 3, 4, 5$，共 $6$ 个。$y = -43k - 25$ 随 $k$ 增大而减小，$k = 0$ 时 $y$ 最大：$x = 10$，$y = -25$。所以 $\fbox{J} = 6$，$\fbox{KL} = 1, 0$，$\fbox{MNO}$ 填「－」「2」「5」。

解说　两分钟做法：先互除、倒推出一组 $=1$ 的解，再乘常数得到目标方程的特解，最后写一般解并用条件夹出 $k$ 的范围。空格判断：$\fbox{BC}$、$\fbox{MNO}$ 是负数，负号各占一格；$\fbox{GH}$ 题干已写出负号，只填 $43$ 的两位；$\fbox{DE}$ 是 $y$ 的系数 $17$，两位。第 (3) 问 $y$ 随 $k$ 增大而减小，所以 $y$ 最大对应最小的 $k$。

問題 2　（記数法）

(1) $5$ 進法で表された数 $2134_{(5)}$ を $10$ 進法で表すと $\fbox{ABC}$ である。

(2) $10$ 進法で表された数 $100$ を $3$ 進法で表すと $\fbox{DEFGH}_{(3)}$ である。

(3) 自然数 $N$ を $7$ 進法で表すと $3$ 桁の数 $abc_{(7)}$ となり，$5$ 進法で表すと $3$ 桁の数 $cba_{(5)}$ となる。ただし，$a$，$b$，$c$ は $0$ 以上 $4$ 以下の整数で，$a \neq 0$，$c \neq 0$ とする。このとき，$b = \fbox{IJ}\,(c - \fbox{K}\,a)$ が成り立つ。$0 \leqq b \leqq 4$ であるから $b = \fbox{L}$ であり，このような $N$ は $2$ 個ある。小さい方は $N = \fbox{MN}$，大きい方は $N = \fbox{OPQ}$ である。

解答　(1) $2 \times 125 + 1 \times 25 + 3 \times 5 + 4 = 250 + 25 + 15 + 4 = 294$。よって $\fbox{ABC} = 2, 9, 4$。

(2) $100 = 3 \times 33 + 1$，$33 = 3 \times 11 + 0$，$11 = 3 \times 3 + 2$，$3 = 3 \times 1 + 0$，$1 = 3 \times 0 + 1$。余りを下から順に読むと $10201_{(3)}$。よって $\fbox{DEFGH} = 1, 0, 2, 0, 1$。

(3) $abc_{(7)} = 49a + 7b + c$，$cba_{(5)} = 25c + 5b + a$ である。両者が等しいとすると $48a + 2b - 24c = 0$，すなわち $b = 12c - 24a = 12(c - 2a)$。 $b$ は $12$ の倍数で $0 \leqq b \leqq 4$ であるから，$b = 0$，$c = 2a$。$c \leqq 4$ より $(a, c) = (1, 2)$ または $(2, 4)$ である。 $(a, b, c) = (1, 0, 2)$ のとき $N = 49 + 0 + 2 = 51$（$51 = 201_{(5)}$）。 $(a, b, c) = (2, 0, 4)$ のとき $N = 98 + 0 + 4 = 102$（$102 = 402_{(5)}$）。 よって $\fbox{IJ} = 1, 2$，$\fbox{K} = 2$，$\fbox{L} = 0$，$\fbox{MN} = 5, 1$，$\fbox{OPQ} = 1, 0, 2$。

中文翻译　题目：（1）$5$ 进制数 $2134_{(5)}$ 用 $10$ 进制表示是 $\fbox{ABC}$。（2）$10$ 进制数 $100$ 用 $3$ 进制表示是 $\fbox{DEFGH}_{(3)}$。（3）自然数 $N$ 用 $7$ 进制表示是三位数 $abc_{(7)}$，用 $5$ 进制表示是三位数 $cba_{(5)}$，其中 $a$、$b$、$c$ 是 $0$ 到 $4$ 的整数，$a \ne 0$，$c \ne 0$。这时 $b = \fbox{IJ}\,(c - \fbox{K}\,a)$。因为 $0 \leqq b \leqq 4$，所以 $b = \fbox{L}$，这样的 $N$ 有 $2$ 个，较小的 $N = \fbox{MN}$，较大的 $N = \fbox{OPQ}$。解答：（1）$2 \times 125 + 1 \times 25 + 3 \times 5 + 4 = 250 + 25 + 15 + 4 = 294$。所以 $\fbox{ABC} = 2, 9, 4$。（2）$100 = 3 \times 33 + 1$，$33 = 3 \times 11 + 0$，$11 = 3 \times 3 + 2$，$3 = 3 \times 1 + 0$，$1 = 3 \times 0 + 1$。余数从下往上读：$10201_{(3)}$。所以 $\fbox{DEFGH} = 1, 0, 2, 0, 1$。（3）$abc_{(7)} = 49a + 7b + c$，$cba_{(5)} = 25c + 5b + a$。两者相等：$48a + 2b - 24c = 0$，$b = 12c - 24a = 12(c - 2a)$。$b$ 是 $12$ 的倍数且 $0 \leqq b \leqq 4$，所以 $b = 0$，$c = 2a$。$c \leqq 4$，所以 $(a, c) = (1, 2)$ 或 $(2, 4)$。$(a, b, c) = (1, 0, 2)$：$N = 49 + 0 + 2 = 51$（$51 = 201_{(5)}$）；$(a, b, c) = (2, 0, 4)$：$N = 98 + 0 + 4 = 102$（$102 = 402_{(5)}$）。所以 $\fbox{IJ} = 1, 2$，$\fbox{K} = 2$，$\fbox{L} = 0$，$\fbox{MN} = 5, 1$，$\fbox{OPQ} = 1, 0, 2$。

解说　两分钟做法：进制转换先按位权展开或反复除法；两种进制表示同一个数时，把两边都展开成 $10$ 进制列方程。空格判断：$\fbox{DEFGH}$ 中间的 $0$ 也要占格；$\fbox{L} = 0$ 是因为 $b$ 被夹在 $0$ 到 $4$ 之间；$\fbox{MN}$ 是两位、$\fbox{OPQ}$ 是三位。求出 $N$ 后代回两种进制各验算一次。

問題 3　（約数・最大公約数・余り）

(1) $360$ を素因数分解すると $360 = 2^{\fbox{A}} \cdot 3^{\fbox{B}} \cdot \fbox{C}$ である。したがって，$360$ の正の約数は $\fbox{DE}$ 個あり，その総和は $\fbox{FGHI}$ である。

(2) 自然数 $n$ と $360$ の最大公約数が $12$，最小公倍数が $2520$ であるとき，$n = \fbox{JK}$ である。

(3) 整数 $m$ を $7$ で割ると $3$ 余るとき，$m^2 + 2m$ を $7$ で割った余りは $\fbox{L}$ である。

解答　(1) $360 = 2^3 \cdot 3^2 \cdot 5$ であるから，$\fbox{A} = 3$，$\fbox{B} = 2$，$\fbox{C} = 5$。約数の個数は $(3 + 1)(2 + 1)(1 + 1) = 24$，総和は $(1 + 2 + 4 + 8)(1 + 3 + 9)(1 + 5) = 15 \times 13 \times 6 = 1170$。よって $\fbox{DE} = 2, 4$，$\fbox{FGHI} = 1, 1, 7, 0$。

(2) $ab = gl$ より $360n = 12 \times 2520$，よって $n = 84$。$\fbox{JK} = 8, 4$。

(3) 余りだけで計算すると $3^2 + 2 \times 3 = 15$ で，$15$ を $7$ で割った余りは $1$。よって $\fbox{L} = 1$。

中文翻译　题目：（1）$360$ 素因数分解为 $360 = 2^{\fbox{A}} \cdot 3^{\fbox{B}} \cdot \fbox{C}$，所以 $360$ 的正约数有 $\fbox{DE}$ 个，总和是 $\fbox{FGHI}$。（2）自然数 $n$ 与 $360$ 的最大公约数是 $12$、最小公倍数是 $2520$ 时，$n = \fbox{JK}$。（3）整数 $m$ 除以 $7$ 余 $3$ 时，$m^2 + 2m$ 除以 $7$ 的余数是 $\fbox{L}$。解答：（1）$360 = 2^3 \cdot 3^2 \cdot 5$，所以 $\fbox{A} = 3$，$\fbox{B} = 2$，$\fbox{C} = 5$。约数个数 $(3 + 1)(2 + 1)(1 + 1) = 24$；总和 $(1 + 2 + 4 + 8)(1 + 3 + 9)(1 + 5) = 15 \times 13 \times 6 = 1170$。所以 $\fbox{DE} = 2, 4$，$\fbox{FGHI} = 1, 1, 7, 0$。（2）由 $ab = gl$，$360n = 12 \times 2520$，所以 $n = 84$，$\fbox{JK} = 8, 4$。（3）只用余数算：$3^2 + 2 \times 3 = 15$，$15$ 除以 $7$ 余 $1$。所以 $\fbox{L} = 1$。

解说　检验（2）：$84 = 2^2 \cdot 3 \cdot 7$，与 $360 = 2^3 \cdot 3^2 \cdot 5$ 的最大公约数是 $2^2 \cdot 3 = 12$，最小公倍数是 $2^3 \cdot 3^2 \cdot 5 \cdot 7 = 2520$，符合。用 $ab = gl$ 求 $n$ 后一定要验算最大公约数，因为 $n$ 可能不止一个解。第 (3) 问只跟踪余数：$m^2 + 2m$ 的余数等于 $3^2 + 2 \times 3$ 的余数。

8.8 术语与题干用语

日文	读音	中文	例句或说明
約数	やくすう	约数（因数）	「360 の正の約数の個数を求めよ」
倍数	ばいすう	倍数	「$n$ は 3 の倍数である」
倍数の判定法	ばいすうのはんていほう	倍数判定法	各位の数の和で 3 の倍数を判定する
素数	そすう	素数（质数）	1 は素数ではない
合成数	ごうせいすう	合数	1 より大きく素数でない自然数
素因数分解	そいんすうぶんかい	素因数分解（分解质因数）	「540 を素因数分解すると」
素因数	そいんすう	素因数（质因数）	「$n!$ に含まれる素因数 2 の個数」
正の約数の総和	せいのやくすうのそうわ	正约数之和	総和 = すべてを足した和
公約数	こうやくすう	公约数
最大公約数	さいだいこうやくすう	最大公约数	「$a$ と $b$ の最大公約数は 12 である」
公倍数	こうばいすう	公倍数
最小公倍数	さいしょうこうばいすう	最小公倍数
互いに素	たがいにそ	互素	「$a$ と $b$ は互いに素である」
割り切れる	わりきれる	整除	「$n^3 + 2n$ は 3 で割り切れる」
割り算	わりざん	除法	整数の割り算 $a = bq + r$
商	しょう	商
余り	あまり	余数	「7 で割ったときの余りは 3 である」「7 で割ると 3 余る」
平方数	へいほうすう	平方数	「$756n$ がある自然数の 2 乗になる」とも書く
合同式	ごうどうしき	同余式	$a \equiv b \pmod{m}$
法	ほう	模	「7 を法として合同」
ユークリッドの互除法	ゆーくりっどのごじょほう	欧几里得互除法（辗转相除法）	「ユークリッドの互除法を用いて」
1次不定方程式	いちじふていほうていしき	一次不定方程	$ax + by = c$ の整数解
整数解	せいすうかい	整数解	「すべての整数解を求めよ」
整数の組	せいすうのくみ	整数对	「① を満たす整数の組 $(x, y)$」
記数法	きすうほう	记数法
$n$ 進法	えぬしんほう	$n$ 进制	「5 進法で表された数」
10 進法	じっしんほう	十进制	「じゅっしんほう」とも読む
2 進数	にしんすう	二进制数	2 進法で表された数
桁	けた	位（数位）	「2 進法で表すと何桁の数か」「2 桁の正の整数」
位	くらい	数位	一の位，十の位
有限小数	ゆうげんしょうすう	有限小数
〜を満たす	〜をみたす	满足……	「① を満たす整数」
$k$ を整数として	けいをせいすうとして	设 $k$ 为整数	一般解を書くときの決まり文句
〜と表される	〜とあらわされる	可以表示为……	「$x = 17k + 2$ と表される」
〜の値が最も大きいもの	〜のあたいがもっともおおきいもの	……的值最大的那个

8.9 自测

1. 四位数 $7a52$（$a$ 是一位数字）是 9 的倍数，求 $a$。
2. 求 720 的正约数的个数和总和。
3. 两个自然数的最大公约数是 8，最小公倍数是 240。两数之和最小时，这两个数是多少？
4. 求 $3^{50}$ 除以 8 的余数。
5. 用互除法求 2183 和 1517 的最大公约数。
6. 使 $n + 4$ 与 $3n + 5$ 的最大公约数为 7 的自然数 $n$ 中，第二小的是多少？
7. 求 $13x + 8y = 3$ 的全部整数解（用特解 $x = -1$，$y = 2$ 表示）。
8. 求除以 4 余 1、除以 9 余 7 的最小三位自然数。
9. 把 $2012_{(3)}$ 化成 10 进制；把 59 化成 2 进制。
10. 3 进制下是 5 位数的自然数有多少个？

答案：1. $a = 4$；2. 30 个，总和 2418；3. 40 和 48；4. 1；5. 37；6. $n = 10$；7. $x = 8k - 1$，$y = -13k + 2$（$k$ 是整数）；8. 133；9. 59，$111011_{(2)}$；10. 162 个。

8.10 深入阅读

• JASSO · 日本留学試験 数学シラバス：官方出题范围原文，第 6 项「整数の性質」列出本章的全部小项目。
• JASSO · 過去問題サンプル：官方公开的过去问，2020 年第 2 回、2021 年第 1 回コース1 Ⅲ 分别是一次不定方程和记数法的大题。
• 维基百科（日文）· ユークリッドの互除法：互除法的原理、历史和推广，「拡張ユークリッドの互除法」就是本章倒推求 ax + by = 1 的方法。
• 维基百科（日文）· 位取り記数法：n 進法的日文术语和各种进制的写法，查日文说法时用。