Appearance
第1章：整数的可除性 · 原始习题解析
正文教程：返回 第1章：整数的可除性
这页只放原始习题、考试写法和解析。复习时建议先看【考试写法】，那是考试卷面上应该呈现的主线；括号解析负责解释“为什么这样判断、为什么这样变形”。
这页按“原题 → 考试写法 → 胎教版解析”的顺序整理。每道题之间用分割线隔开，复习时不用在答案区和解析区来回跳。
原始练习题扫描
下面是本章对应的原始练习题扫描。建议先把上面的例题看懂，再回到这里按题号练。
逐题解析
判断题 1
原题： 设 n 是正合数，p 是 n 的大于 1 的正因数，则 p <= √n
考试写法：
错。
如果 p 只是 n 的一个大于 1 的因数，不一定有 p <= √n。比如 n=6，取 p=6，明显 6 > √6。
真正成立的是：如果 n 是合数，那么它一定有一个大于 1 且不超过 √n 的因数。回看正文：判断素数：试到 √n 就够了。
胎教版解析（默认隐藏，展开看为什么）
答案：错。
先把题目翻译成人话：
n 是合数，p 是 n 的一个因数。题目说：只要 p 是大于 1 的因数，就一定不超过 √n。
这个说法太强了。一个合数确实一定有“小因数”，但不是说它的每一个因数都小。
举一个反例就够了：
取 n = 6。6 是合数。p = 6 是 6 的大于 1 的正因数。
但是 √6 大约是 2.45，显然 6 > √6。
所以原命题错误。
真正正确的说法是：
如果 n 是合数，那么 n 至少有一个大于 1 且不超过 √n 的因数。
为什么？如果 n = ab，并且 a,b 都大于 √n，那 ab 就会大于 n，矛盾。所以两个因数里至少有一个不超过 √n。
回看正文：判断素数：试到 √n 就够了。
判断题 2
原题： 若 a,b 互素，则存在整数 s,t，使得 sa+tb=1
考试写法：
对。a,b 互素就是 (a,b)=1。根据贝祖等式，一定存在整数 s,t，使 sa+tb=1。
回看正文：扩展欧几里得：把最大公因数凑出来。
胎教版解析（默认隐藏，展开看为什么）
答案：对。
a,b 互素的意思是：
gcd(a,b)=1
扩展欧几里得告诉我们：
对任意整数 a,b，都存在整数 s,t，使得
sa+tb=gcd(a,b)。
现在 gcd(a,b)=1，所以自然就有：
sa+tb=1
这不是凭空来的，而是扩展欧几里得“倒推”的结果。
比如 47 和 30 互素，倒推就能得到：
47×(-7)+30×11=1
回看正文：扩展欧几里得。
判断题 3
原题： 若 k 是正整数，则 (ak,bk)=(a,b)
考试写法：
错。
正确结论是 (ak,bk)=k(a,b)，不是 (a,b)。比如 a=2,b=3,k=5，左边 (10,15)=5，右边 (2,3)=1。
胎教版解析（默认隐藏，展开看为什么）
答案：错。
先用一个具体数字试：
取 a=2,b=3,k=5。
左边：
ak=10，bk=15，所以 (ak,bk)=gcd(10,15)=5。
右边：
(a,b)=gcd(2,3)=1。
左边是 5，右边是 1，不相等。
正确公式是：
gcd(ak,bk)=k·gcd(a,b)
为什么？因为 a 和 b 同时乘了一个 k，它们的所有公共因数也整体多了一个共同的 k。
判断题 4
原题： 若 (a,c)=1，则 (ab,c)=(b,c)
考试写法：
对。
如果 (a,c)=1，那么 a 和 c 没有共同因子。此时 ab 和 c 的共同因子只能从 b 里来，所以 (ab,c)=(b,c)。
胎教版解析（默认隐藏，展开看为什么）
答案：对。
这题不要硬背，想“公共因子从哪里来”。
(ab,c) 的意思是：ab 和 c 共同拥有的因子。
但题目给了 (a,c)=1，意思是：
a 和 c 没有共同因子。
所以 ab 里能和 c 重合的因子，不可能来自 a，只能来自 b。
因此：
(ab,c)=(b,c)
举例感受一下：
取 a=5,b=12,c=18。(5,18)=1。
左边 (ab,c)=(60,18)=6。
右边 (b,c)=(12,18)=6。
确实一样。
判断题 5
原题： 若 a|m，b|m，则 [a,b]|m
考试写法：
对。
如果 a|m、b|m，那么 m 同时是 a 和 b 的倍数，所以 m 一定是最小公倍数 [a,b] 的倍数。
回看正文：最小公倍数 lcm。
胎教版解析（默认隐藏，展开看为什么）
答案：对。
a|m 的意思是：m 是 a 的倍数。b|m 的意思是：m 也是 b 的倍数。
所以 m 是 a 和 b 的一个“公倍数”。
而 [a,b] 是 a 和 b 的“最小正公倍数”。
既然 [a,b] 是所有公倍数里最小的那个，那么任何公倍数都应该是它的倍数，所以：
[a,b]|m
回看正文：最小公倍数。
判断题 6
原题： 若 c|ab 且 (a,c)=1，则 c|b
考试写法：
对。c|ab，而 (a,c)=1，说明 a 不能贡献 c 的因子，所以这些因子只能由 b 提供，因此 c|b。
胎教版解析（默认隐藏，展开看为什么）
答案：对。
这题背后还是“因子从哪里来”。
c|ab 表示：c 的所有素因子都能在 ab 里找到。
又因为 (a,c)=1，说明 a 和 c 没有共同素因子。
所以 c 的因子不可能藏在 a 里面，只能藏在 b 里面。
因此 c|b。
举例：
c=6,a=5,b=12。6|5×12=60，并且 (5,6)=1。
于是 6|12，成立。
判断题 7
原题： 若 c|a，c|b，且 m=sa+tb，则 c|m
考试写法：
对。c|a 且 c|b，那么 a,b 的任意整数线性组合都能被 c 整除。m=sa+tb 正是这种组合。
回看正文：整除的常用性质。
胎教版解析（默认隐藏，展开看为什么）
答案：对。
这就是整除的线性组合性质。
因为 c|a，所以 a=cA。
因为 c|b，所以 b=cB。
代入 m=sa+tb：
m=s(cA)+t(cB)
把 c 提出来：
m=c(sA+tB)
括号里 sA+tB 是整数，所以 m 是 c 的倍数。
因此：
c|m
回看正文：整除的常用性质。
判断题 8
原题： 对任意整数 c，存在唯一 q,r，使 a=bq+r，c<r<b+c
考试写法：
错。
标准带余除法要求余数区间长度刚好覆盖 b 个可能余数。题中写的是 c<r<b+c，两边都是严格不等号，只包含 b-1 个整数，不能保证所有 a 都能表示。
胎教版解析（默认隐藏，展开看为什么）
答案：错。
标准带余除法的余数范围是：
0 <= r < b
这个区间有 b 个整数余数，刚好能代表所有余数类。
题目给的是：
c < r < b+c
注意两边都是严格不等号。这个区间里的整数只有 b-1 个，不够覆盖全部余数。
举例：
设 b=5,c=0，题目要求：
0 < r < 5
所以 r 只能是 1,2,3,4，没有 0。
但如果 a=10，它除以 5 的余数应该是 0。题目不允许 r=0，所以不成立。
回看正文：带余除法。
判断题 9
原题： 若 b>0，则存在唯一 q,r，使 a=bq+r，0<=r<b
考试写法：
对。
这就是标准带余除法：a=bq+r，且 0<=r<b，商和余数唯一。
回看正文：带余除法。
胎教版解析（默认隐藏，展开看为什么）
答案：对。
这就是标准带余除法定理。
关键有两点：
第一，存在：任何整数 a 都能除以正整数 b，得到商和余数。
第二，唯一：余数限制在 0 到 b-1 之间，不能乱选。
比如 23=5×4+3，不能写成 23=5×3+8，因为 8 不满足 0<=r<5。
判断题 10
原题： 若 a|m，b|m，则 ab|m
考试写法：
错。a|m、b|m 只能推出 [a,b]|m，不能推出 ab|m。例如 a=2,b=4,m=4，有 2|4、4|4，但 8 不整除 4。
胎教版解析（默认隐藏，展开看为什么）
答案：错。
题目想把“都能整除 m”误推成“乘起来也能整除 m”。
反例：
取 a=2,b=4,m=4。
2|4 成立。4|4 成立。
但是 ab=8，8 不整除 4。
正确结论是：
[a,b]|m
不是 ab|m。
综合题 1
原题： 判断 101 是否为素数
考试写法：
101 是素数。√101 比 10 大一点，只需要试除 2,3,5,7。101 不能被它们整除，所以是素数。
回看正文：判断素数。
胎教版解析（默认隐藏，展开看为什么）
答案：101 是素数。
判断素数不用试到 100，只要试到 √101。
因为：
10²=100，11²=121
所以 √101 介于 10 和 11 之间。
只需要检查不超过 10 的素数：
2,3,5,7
逐个看：
101 不是偶数，所以不能被 2 整除。
数字和 1+0+1=2，不能被 3 整除。
个位不是 0 或 5，不能被 5 整除。7×14=98，7×15=105，所以不能被 7 整除。
都不行，所以 101 是素数。
综合题 2
原题： 求下列各组整数的最大公因数：(55,85)，(202,282)，(78,169)。
考试写法：
最大公因数：(55,85)=5；(202,282)=2；(78,169)=13。
思路都是辗转相除：大数除小数，余数继续除，直到余数为 0。
胎教版解析（默认隐藏，展开看为什么）
（1）(55,85)=5。
过程：
85=55×1+3055=30×1+2530=25×1+525=5×5+0
最后一个非 0 余数是 5。
（2）(202,282)=2。
过程：
282=202×1+80202=80×2+4280=42×1+3842=38×1+438=4×9+24=2×2+0
最后一个非 0 余数是 2。
（3）(78,169)=13。
过程：
169=78×2+1378=13×6+0
所以答案是 13。
综合题 3
原题： 计算 (368,299,552)
考试写法：
(368,299,552)=23。
先算 (368,299)=23，再算 (23,552)=23，所以三个数的最大公因数是 23。
胎教版解析（默认隐藏，展开看为什么）
先算前两个：
368=299×1+69299=69×4+2369=23×3+0
所以：
(368,299)=23
再和第三个数 552 算：
552=23×24+0
所以：
(368,299,552)=23
综合题 4
原题： 求 72a+108b+96c 能表示的最小正整数
考试写法：
最小正整数是 12，一组取值是 a=0,b=1,c=-1。
因为 gcd(72,108,96)=12，所以表达式能表示的最小正整数就是 12。
直接验证：72×0 + 108×1 + 96×(-1)=12。
胎教版解析（默认隐藏，展开看为什么）
这个题的核心结论是：
一堆整数线性组合能表示的最小正整数，就是这些系数的最大公因数。
所以先求：
gcd(72,108,96)
先算：
108=72×1+3672=36×2+0
所以 (72,108)=36。
再算：
96=36×2+2436=24×1+1224=12×2+0
所以 (36,96)=12。
因此最小正整数是 12。
还要给出 a,b,c。观察系数可得：
108-96=12
也就是：
72×0+108×1+96×(-1)=12
所以一组答案是：
a=0,b=1,c=-1
综合题 5
原题： 66x+75y=(66,75)
考试写法：
一组答案：x=8,y=-7。(66,75)=3，并且 66×8 + 75×(-7)=528-525=3。
胎教版解析（默认隐藏，展开看为什么）
先求最大公因数：
75=66×1+966=9×7+39=3×3+0
所以：
(66,75)=3
开始倒推：
3=66-9×7
而：
9=75-66
代入：
3=66-(75-66)×7
拆括号：
3=66-75×7+66×7
合并 66：
3=66×8-75×7
所以：
x=8,y=-7
综合题 6
原题： a=551,b=203，求 s,t，使 as+bt=(a,b)
考试写法：
s=3,t=-8。551=203×2+145，203=145+58，145=58×2+29，所以 gcd 是 29。
倒推得到：29=3×551-8×203。
胎教版解析（默认隐藏，展开看为什么）
先辗转相除：
551=203×2+145203=145×1+58145=58×2+2958=29×2+0
所以：
(551,203)=29
倒推：
29=145-58×2
而：
58=203-145
代入：
29=145-(203-145)×2
拆括号：
29=145×3-203×2
又因为：
145=551-203×2
继续代入：
29=(551-203×2)×3-203×2
拆开：
29=551×3-203×6-203×2
合并：
29=551×3-203×8
所以：
s=3,t=-8
综合题 7
原题： 437s+322t 能表示的最小正整数
考试写法：
最小正整数是 23。
因为 (437,322)=23。一组表示是：23=3×437-4×322。
胎教版解析（默认隐藏，展开看为什么）
最小正整数就是：
gcd(437,322)
辗转相除：
437=322×1+115322=115×2+92115=92×1+2392=23×4+0
所以：
gcd(437,322)=23
如果要写成组合，倒推：
23=115-92
92=322-115×2
代入：
23=115-(322-115×2)=115×3-322
115=437-322
再代入：
23=(437-322)×3-322=437×3-322×4
所以最小正整数是 23，一组是：
s=3,t=-4
综合题 8
原题： 写出 1225 的标准分解式
考试写法：
1225=5²×7²。
因为 1225=35²=(5×7)²。
胎教版解析（默认隐藏，展开看为什么）
答案：
1225=5²×7²
先看题目要什么：
标准分解式，就是把一个正整数拆成“素数的乘积”，并且相同素数用指数写出来。
所以我们从最小的素数开始试：
第一步，看能不能被 2 除。1225 是奇数，不能被 2 整除。
第二步，看能不能被 3 除。
各位数字和是 1+2+2+5=10。10 不能被 3 整除，所以 1225 不能被 3 整除。
第三步，看能不能被 5 除。
个位是 5，所以一定能被 5 整除：
1225÷5=245
245 个位还是 5，继续除以 5：
245÷5=49
到这里已经得到：
1225=5×5×49
第四步，分解 49。49=7×7。
所以：
1225=5×5×7×7=5²×7²
检查一下：
5²×7²=25×49=1225
能乘回原数，说明分解没错。
回看正文：标准分解式。
综合题 9
原题： 写出 600 的标准分解式
考试写法：
600=2³×3×5²。
胎教版解析（默认隐藏，展开看为什么）
答案：
600=2³×3×5²
还是老规矩：从小素数开始除。
第一步，先除 2。600 是偶数：
600÷2=300
300 还是偶数：
300÷2=150
150 还是偶数：
150÷2=75
75 不是偶数，不能再除 2 了。
所以目前已经有三个 2：
600=2×2×2×75=2³×75
第二步，分解 75。75 各位数字和是 7+5=12，能被 3 整除：
75÷3=25
第三步，分解 25。25=5×5=5²
合起来：
600=2³×3×5²
检查：
2³×3×5²=8×3×25=24×25=600
回看正文：标准分解式。
综合题 10
原题： 写出 1176 的标准分解式
考试写法：
1176=2³×3×7²。
胎教版解析（默认隐藏，展开看为什么）
答案：
1176=2³×3×7²
第一步，除 2。1176 是偶数：
1176÷2=588
588 还是偶数：
588÷2=294
294 还是偶数：
294÷2=147
147 是奇数，不能再除 2。
所以：
1176=2³×147
第二步，分解 147。
看能不能除 3：各位数字和是 1+4+7=12，能被 3 整除。
147÷3=49
第三步，分解 49。49=7×7=7²
所以：
1176=2³×3×7²
检查：
2³×3×7²=8×3×49=24×49=1176
回看正文：标准分解式。
综合题 11
原题： 求最小公倍数 [49,77] 和 [78,169]
考试写法：
最小公倍数：[49,77]=539；[78,169]=1014。
解：先求 gcd，再用 [a,b]=ab/(a,b)。
胎教版解析（默认隐藏，展开看为什么）
这类题先记住公式：
[a,b]=ab/(a,b)
它的意思是：
两个数相乘时，公共因子被算了两遍；除掉一次最大公因数，就得到最小公倍数。
（1）求 [49,77]
先求最大公因数：
49=7²77=7×11
两个数共同拥有的因子只有一个 7，所以：
(49,77)=7
套公式：
[49,77]=49×77÷7
先把 49÷7=7，这样算更轻松：
[49,77]=7×77=539
所以：
[49,77]=539
（2）求 [78,169]
先分解：
78=2×3×13
169=13×13=13²
共同因子是一个 13，所以：
(78,169)=13
套公式：
[78,169]=78×169÷13
因为 169÷13=13，所以：
[78,169]=78×13=1014
所以：
[78,169]=1014
回看正文：最小公倍数。
综合题 12
原题： 编程实现本章的欧几里得算法/扩展欧几里得算法
考试写法：
编程题算法步骤。
如果是实现教材定理 1.2.8，建议先把“输入两个整数 → 辗转相除 → 输出 gcd 或系数”的流程写清楚。真正写代码时，核心循环就是：不断把 (a,b) 换成 (b,a mod b)，直到余数为 0。
胎教版解析（默认隐藏，展开看为什么）
这题不是让你背代码，而是让你把数学步骤翻译成程序步骤。先把人手算的过程看懂，代码自然就出来了。
目标一：只求最大公因数 gcd
手算时我们做的是：
a=bq+r
如果 r 不是 0，下一轮就把：
原来的 b 变成新的 a，原来的 r 变成新的 b。
也就是不断重复：
(a,b) -> (b,a mod b)
直到 b=0。这时候 a 就是最大公因数。
为什么最后的 a 是 gcd？
因为：
a=bq+r
可以移项得到：
r=a-bq
这说明 a,b 的公因数，一定也是 b,r 的公因数；反过来也一样。
所以每换一轮，最大公因数没有变：
gcd(a,b)=gcd(b,r)
程序思路可以写成：
- 输入
a,b。 - 当
b不等于0时，计算r=a mod b。 - 把
a改成旧的b，把b改成r。 - 循环结束后，输出
a。
目标二：同时求 s,t，使 as+bt=gcd(a,b)
如果题目说的是“定理 1.2.8 / 贝祖等式 / 扩展欧几里得”，那就要多输出两个系数。
核心想法是：
每一轮不仅保存余数，还保存“这个余数是原始 a 和原始 b 怎么凑出来的”。
举个变量含义：
当前 a 可以写成：
a=old_s×原始a+old_t×原始b
当前 b 可以写成：
b=s×原始a+t×原始b
一开始：
原始a=1×原始a+0×原始b，所以 old_s=1, old_t=0。原始b=0×原始a+1×原始b，所以 s=0, t=1。
每轮做除法：
a=bq+r
所以：
r=a-bq
也就是说，余数的系数也要跟着做同样的减法：
new_s=old_s-q×snew_t=old_t-q×t
然后像普通欧几里得一样挪位：
a <- b，b <- r
系数也一起挪：
old_s <- s，old_t <- ts <- new_s，t <- new_t
最后 b=0 时，当前的 a 就是 gcd，当前的 old_s,old_t 就是一组答案。
这就是程序版的“倒着往回代”。手算是先算完再倒推，程序是边算边把倒推信息存起来。
回看正文：扩展欧几里得。