练习 1
有 20 个红色筹码、30 个蓝色筹码，要全部装成相同的小礼物，最多能装几袋？每袋各有多少个？
查看推理与计算
袋数需要同时整除 20 和 30，因此求最大公因数。，。两边共有一个 2、一个 5，得到 袋。每袋红色 个，蓝色 个。更大的袋数不能同时整除这两个总数。
我们有 12 个红色筹码和 18 个蓝色筹码，想把它们装成一袋袋相同的小礼物：每袋的红色筹码数量相同，蓝色筹码数量也相同。筹码不能切开，也不能剩下。能装成多少袋呢？
只需要会整数的乘法和除法。因数、倍数和质数会在用到时解释。这里研究的是 1、2、3 等正整数，输入不包含零。
回看整除与余数试试图里的 5 袋。每袋放 2 个红色筹码，用掉 5×2=10 个，还剩 12−10=2 个。每袋放 3 个蓝色筹码，用掉 5×3=15 个，还剩 18−15=3 个。袋子里的数量虽然相同，可是还有筹码没装进去，所以这样不行。
改变袋数。一个红圆点代表一个红色筹码，一个蓝方块代表一个蓝色筹码；每个外框代表一袋。除了看袋子是否相同，也要看独立显示的剩余区。你还可以改变一开始有多少筹码。
改成 6 袋，每袋有 12÷6=2 个红色筹码和 18÷6=3 个蓝色筹码，一点也不剩。一个正整数能把另一个数整除，也就是除完没有余数，我们就说它是那个数的因数。6 同时是 12 和 18 的因数，所以也是它们的公因数。
每袋：红色 2 个，蓝色 3 个
这一种有剩余。 袋外还有 2 个红色筹码、3 个蓝色筹码。如果只把它们加进某些袋子，每袋的数量就不相同了。
还能装出更多相同的袋子吗？我们可以检查所有可能的袋数。每袋至少要有一个红色和一个蓝色筹码，所以袋数不能超过较少的那种筹码的总数。下面标出的数都能同时整除当前两种筹码的总数。点一下某个数，就能在袋子里检查。
带强调边框的数能同时整除两种总数，当前选中的数有底色。
公因数: 1, 2, 3, 6
其中最大的数是 6，所以最多能装成 6 袋相同的礼物。这个数叫作最大公因数，英文缩写为 GCD。gcd(12,18)=6 就是在记录这两个数及其最大公因数。
现在换一个问题。A 车每 4 分钟出发一次，B 车每 6 分钟出发一次；它们刚刚同时出发，把那一刻记为零。A 的出发时刻是 0、4、8、12、……分钟，B 的是 0、6、12、……分钟。它们下一次同时出发是什么时候？
两行使用相同的时间刻度。圆点表示 A 出发，菱形表示 B 出发。可以拖动时钟，也可以逐步推进时间。金色竖线会连接同时发生的两次出发。零时刻只是起点，不是我们要找的下一次相遇。
零时刻，两班车刚刚同时出发。我们要找的是这之后的相遇。
按照当前间隔，下一次同时出发是在 12 分钟后：12=3×4=2×6。记作 lcm(4,6)=12。图中时间显示到第二次正的相遇时刻，即 24 分钟。
4 的正倍数就是 4 分别乘以 1、2、3 等正整数的结果：4、8、12、……。同时出发的时刻必须是两个间隔的倍数，也就是它们的公倍数。我们要找其中最小的正数，叫作最小公倍数，英文缩写为 LCM。4 和 6 的最小公倍数是 12。
回想刚才的袋子：公因数能整除两个总数。这里则是公倍数能装下整数个两种间隔。问题的方向变了：12 的因数不可能大于 12，而 12 的正倍数不可能小于 12。
12 和 18 可以逐个检查因数，可是数很大时，这样会检查很多次。我们需要把数字变小，同时不改变它们的公因数。来看两条长度分别为 48 和 18 的纸条；这里的长度只是相同小格的个数，不引入新的物理单位。
48 格长的纸条里能放进两条 18 格长的纸条。它们占 2×18=36 格，剩下 48−36=12 格。这个剩下的数就是余数。为什么可以把 48、18 换成 18、12 呢？我们需要两个方向都检查，否则可能漏掉因数，或者多出本来不是因数的数。
假设一种长度能整除 48 和 18。那么 48 格纸条和每一段 18 格纸条都能切成这种长度的小段。拿走两段完整的 18 格纸条，只会拿走完整的小段，因此剩下的 12 格也由完整小段组成。原来的每一个公因数都会保留下来。
反过来，假设一种长度能整除 18 和 12。把两段 18 格与一段 12 格拼回去，就得到 48=2×18+12。每部分都由完整小段组成，所以它也能整除 48。这样也没有多出新的公因数。 两组数的公因数完全相同，最大的那个当然也相同。
这个道理适用于每一次带余除法：从较大的数里拿走尽可能多份完整的较小数，把较小数和余数留下。它们的公因数保持不变，然后继续对新的一组数做同样的事。只要余数不为零，它就比刚才的除数小；正整数不会永远越变越小，所以这个过程一定会结束。
点下一步，一次只处理一条纸条。每个蓝色块是一份当前除数，金色部分是余数。已经完成的除法会保留在图下。某块过小而无法标字时，仍可从下面的式子核对它的数量。
纸条还没有切开。点下一步，拿走若干份完整的较短纸条，检查剩下多少。
这个反复做除法的方法叫作辗转相除法，也叫欧几里得算法。算法就是一套可以按顺序执行的步骤。这里值得记住的是：数字变小，公因数不变，而且每一次替换都有理由。
我们已经能较快求最大公因数了。想把最大公因数和最小公倍数放在一起理解，还可以看看一个数内部的乘法。例如 12=3×4，而 4=2×2。把 4 换成 2×2，就得到 12=3×2×2。写法变了，乘积没变。
2 还能拆成两个都大于 1 的整数相乘吗？不能，因为它的正因数只有 1 和 2。一个大于 1 的整数，如果正因数只有 1 和它本身，就叫作质数。3、5、7 也是质数。4 这样的数还能拆成 2×2，叫作合数。
每个分叉都把一个数换成相乘等于它的两个因数。最下面一行保留当前正在使用的全部因数。选好一个数和第一次拆法，再逐步展开分叉。带强调圆环的末端数是质数；还没拆完的合数仍可以继续分。
乘积仍然是 36。展开一个分叉，把一个合数末端换成它的两个因数。这里不会凭空多乘一个数：新因数要替换掉原来的那个数。
为什么最后能拆完？例如 36=4×9，拆出的 4 和 9 都是比 36 小的正整数，同时又大于 1。沿着任意一条分支往下走，数都变小，不可能一直拆下去。最后留下的必须是质数，否则作为合数，它还可以继续拆。因此，每个大于 1 的整数都能分解成质数的乘积。
想把重复乘法写短一点，可以把 2×2×2 记成 23。右上角的 3 数的是三个因数 2，并不是 2×3。后面的图会保留每一个因数，即使式子采用这种简写。
36 可以从 4×9 拆，也可以从 6×6 拆，两条路最后都有两个 2、两个 3。但是，只画几个例子并不能证明任何拆法都会得到相同的质因数。下面求最大公因数、最小公倍数要依靠这些列表，所以先把这个理由说清楚。
还记得刚才的辗转相除法吗？它还有一个用处：最大公因数能写成两个原数的整数倍相加或相减。这里的整数倍允许负号，例如 −5 就是减去一份 5。下面把 5 和 3 算出的余数 1 拼回原来的两个数。
逐行展开，前面的式子会留下。每次替换都用已经得到的等式，不是猜出新的数字。数值例子之后，还会解释为什么同样的道理能用于一般情况。
现在选一个质数，记为 p，再把两个正整数记为 u、v。我们想问：如果 p 能整除 u×v，它一定能整除 u 或 v 中的某一个吗？如果它已经能整除 u，当然可以。接下来只看另一种情况：它不能整除 u。
质数 p 的正因数只有 1 和 p。既然 p 不能整除 u，它们的公因数就只剩 1。根据刚才对余数的解释，这个 1 可以写成 p 的一个整数倍加上 u 的一个整数倍。把这两个倍数记为 s、t，它们可以是负数。
把整个等式乘以 v。右边第一项是 p 的倍数；第二项也是，因为一开始就假定 p 能整除 uv。完整的 p 的倍数相加或相减，仍是 p 的倍数。因此左边的 v 也一定能被 p 整除。
这样就证明了需要的规则：质数能整除一个乘积，就一定能整除其中至少一个因数。因数超过两个时，把第一个以外的因数暂时看成一个乘积，再重复刚才的论证。这里“质数”不能删掉：6 能整除 2×3，却既不能整除 2，也不能整除 3。
假设两个质因数列表的乘积相同。从第一列取出一个质数，它能整除整个乘积，因此根据刚才的规则，它必定整除第二列中的某个质数。质数大于 1 的因数只有它本身，所以这两个质数相同。约去这一对，再对剩余部分重复。一列不可能已空，另一列还剩质数，因为剩余质数的乘积会大于 1。因此两列含有相同的质数，每种数量也相同，只有排列顺序可以不同。
整除也就可以用列表理解了。如果 d 能整除 a，就有 a=d×k，其中 k 是正整数。把 d 和 k 拆成质数，合起来就是 a 的质因数列表，因此 d 需要的每一份质因数，在 a 中都能找到。反过来，如果这些份数都能找到，剩下的质因数相乘得到整数 k，也就有 a=d×k。一份都没剩则取 k=1。现在可以放心用质因数的份数来判断整除了。
回到 12 和 18。它们的列表是 12=2×2×3 和 18=2×3×3。12 里的两个 2 是两份独立的质因数，不是一份名字叫 4 的质因数。图中把同一种质数放在同一列，比较两个数各有几份。
公因数需要的每份质因数，必须在两个数中都找得到。12 有两个 2，18 只有一个，所以最多取一个 2。12 有一个 3，18 有两个，所以最多取一个 3。把能取的都取上，得到 2×3=6。任何公因数都不可能多取某种质因数，因此它一定能整除这个乘积，也就不会比它大。这才说明得到的是最大公因数。
公倍数必须备齐足够的质因数，让两个数都能整除它。要容纳 12，需要两个 2；要容纳 18，需要两个 3。同一份因数可以同时满足两边的要求，所以每种各需两份，不是各三份：2×2×3×3=36。任何公倍数至少要备齐这些份数，因此这个乘积能整除每个公倍数；它自己又已经是公倍数，所以是最小的正公倍数。
选择最大公因数或最小公倍数，再一次处理一列质数。每个带数字的小块是一份因数，结果行记录保留几份。改变任一原数或计算方式时，会从头计算，避免旧答案挂在新的输入下。
还没有处理任何质数列。乘积从 1 开始，这样乘入第一个选中的因数时，结果就等于它。
简写式中，某个质数的份数叫作它的指数。求最大公因数，每种质数取较小指数；求最小公倍数，每种取较大指数。没有出现的质数算零份，也就是指数为零。这些规则的理由是刚才的列表与整除关系，不能只记“小的、大的”而忘掉为什么。
有三种情况可以用来核对：1 与任意正整数的最大公因数是 1，最小公倍数是那个数本身。两个数相等时，两种答案都等于它们自己。如果两个数没有共有的质因数，最大公因数就是 1，我们说它们互质。互质不表示它们各自都是质数：8 和 9 都不是质数，却互质，最小公倍数为 8×9=72。
计算前，先判断所找的数要整除两个原数，还是要容纳整数份两个原数。写下选择的理由，再打开解析。解析会给出计算过程，而不只报答案。
有 20 个红色筹码、30 个蓝色筹码，要全部装成相同的小礼物，最多能装几袋？每袋各有多少个？
袋数需要同时整除 20 和 30，因此求最大公因数。20=2×2×5，30=2×3×5。两边共有一个 2、一个 5，得到 2×5=10 袋。每袋红色 20÷10=2 个，蓝色 30÷10=3 个。更大的袋数不能同时整除这两个总数。
两只铃现在同时响，一只每 6 分钟响一次，另一只每 8 分钟响一次。它们下一次同时响是几分钟后？为什么答案不是零？
等待时间要容纳整数个 6 分钟间隔和 8 分钟间隔，所以找公倍数。6=2×3，8=2×2×2。备齐三个 2、一个 3，得到最小的正公倍数 2×2×2×3=24 分钟。核对：24=4×6=3×8。零表示现在这次，“下一次”要求等待正的时间。
用余数求 84 和 30 的最大公因数。每换一组数，都说明公因数为什么没有变化。
计算 84=2×30+24，再算 30=1×24+6，最后 24=4×6+0，得到最大公因数 6。原来两个数的公因数，能整除拿走完整份数后留下的余数；反过来，较小数和余数的公因数，也能整除重新拼回的总数。这种双向检查保证每次替换都保留完全相同的公因数。
有人把 12 和 18 的所有质因数都放在一起相乘，得到了 216。它确实是公倍数，为什么却不是最小公倍数？
把两列直接合并，会有三个 2、三个 3。但只需要两个 2、两个 3，两个原数就都能整除结果：36=12×3=18×2。多出的一个 2、一个 3 没有必要。最小公倍数取每种质因数所需的较多份数，不是把两边相加，因此是 36，不是 216。
