下载掌阅APP，畅读海量书库
立即打开
尽管一个整数除以另一个整数通常会得到一个并不属于整数的分数，但用一个整数除以另一个整数还是有可能得到一个整数的；而这是如何发生的，以及什么时候会发生，相关性质是很重要的，并且在我们将要遇到的其他代数系统如多项式中也会出现类似的问题。因此，我们现在就来说说整数除法的主要性质。我们要开始使用幂记号（比如把2×2×2写作2 3 ），还有“小于”号（<）和“小于等于”号（≤）（例如，4 < 7及—3 < 2，正如各个实例中那样，数轴上的第一个数都在第二个数的左侧）。当我们知道正在处理字母比如 a 、 b 所表示的数的乘法时，通常就把乘号看作默认的而把算式写成 ab 的形式，或者有时也写作 a · b ，而不是 a × b 。我们倾向于回避繁琐的乘号，所以有时也会把2×（—3）×4这样的算式写成（2）（—3）（4）。
我们有一个整数
a
及另一个整数
b
，若
b
能写成
b
=
ac
，那么
a
就是
b
的因数
或除数，此处
c
本身也是一个整数（同理，那么
c
当然也是
b
的因数）。素数是像71这样的整数，它恰有两个正因数，一个必须是1，另一个则必须是该数本身。大于1而不是素数的整数称为合数，因为它是由更小的因数组合而成的。例如，72=8×9。我们说8是72的因数，或者说8整除72，或者说72是8的倍数：我们有时把这种关系记作8|72，它仅是“8为72的因数”的简略表述形式而已。尽可能一步步地对给定某数的因数进行分解，最终会得出该数的素数分解。对于上例，72=8×9=2
3
×3
2
。我们本可以用另一种方式求出72的素数分解，即72=6×12=（2×3）×（4×3）=（2×3）×（2×2×3）；不过，将素因数从最小到最大重新排列，得到的是跟之前一样的结果；于是我们说2
3
×3
2
是72的素数分解。“算术基本定理”告诉我们，任意自然数
n
的素数分解（用按升序排列的素因数来表示）是唯一的。这种唯一性可以由数的更为基本的性质，即“欧几里得引理”
推导出来。该性质表明，若素数
p
整除
a
与
b
的乘积，记作
p
|
ab
，那么
p
或是
a
的因数或是
b
的因数（或者可能是二者的因数）。“欧几里得引理”的一个等价表述是，若
a
与
b
都不是素数
p
的倍数，那么它们的乘积
ab
也不是。这个性质尽管看起来合理可信，却并非不言自明，而我们在这里也不打算证明欧几里得引理。不过，我们稍后会在本节进一步解释该引理为什么成立。（本书关于数的章节详细阐释了整数的所有性质，而这些性质于此都被认为是成立的。）
一个自然数 a 除以另一个自然数 b ，一般用如下方法。即要用 b 除 a ，我们就从 a 中将 b 辗转减去多次，次数比如记作 q ，直到余项 r < b 。这样，我们便有 a = bq + r 。这个算式是唯一的： q 和 r 都只有唯一的值，使得该式成立；切记，我们要确保0≤ r ≤ b —1。也有些特殊情况：比如，恰好当 a < b 时， q =0，此时 r = a 。更有意思的是，正好当 b | a 时， r =0，此时 a / b = q 。
来看一个有代表性的示例，若
a
=72且
b
=13，那么72=13×5+7，这样我们有
q
=5而
r
=7。对于给定的
a
和
b
，来求算式
a
=
bq
+
r
的过程，被称为“带余除法”
。
我们在算术中首次遇到的一个基本代数思想，是关于两个正整数
a
和
b
的最大公约数的，它也被称为最大公因数
。顾名思义，
a
和
b
的最大公约数或最大公因数，就是
a
和
b
的公因数中最大的那个数
d
；因为
a
和
b
总有至少一个公因数，即1这个数，所以最大公因数必定存在。如果
a
和
b
两个数的最大公因数是1，那么我们就说这两个数互为素数
。例如，15=3×5与28=2
2
×7便互为素数（尽管15和28本身并非素数）。不管怎么样，剩下的问题就是我们可以如何计算给定两个数的最大公因数。
最大公因数 d 可以通过比较 a 与 b 的素数分解来求出，因为 d 的素因数恰是 a 与 b 的公因数。不过，求解最大公因数还有更好的方法，被称为“欧几里得算法”，它不仅更快，而且还揭示了其他有用的关系。我们稍后会解释该算法，但首先要关注公因数的某些基本性质。
比如，假设 c 是 a 和 b 的任意公因数，于是有 a = ct 及 b = cs 。接下来有任意一个数 r ， r = ax + by ，其中 x 和 y 本身是整数（可能是负数或零），那么 c 也是 r 的因数。为了看得更清楚，我们找到并“提取”算式 ax + by 的公因数 c ，如下所示：
r = ax + by = ctx + csy = c （ tx + s y ）。（1）
由于 tx + sy 也是整数，所以 c 实际上就是 r 的因数。
（1）式的一个直接结论是，它适用于我们以
r
=
a
—
bq
来表示的带余除法等式，因为它告诉我们，
a
和
b
的任意公因数也是
r
的因数。同理，由
a
=
bq
+
r
，可知
b
和
r
的任意公因数也是
a
的因数。因此，
a
和
b
的所有公因数的集合，等同于
b
和
r
的所有公因数的集合；特别地，
a
和
b
的最大公因数也是
b
和
r
的最大公因数。这让我们能处理
b
与
r
这两个数，而不是直接处理
b
和
a
。由于
r
<
b
，我们现在可以将带余除法应用于（
b
，
r
）这对数并重复该过程，直到
a
和
b
的最大公因数出现，这就简化了我们求解最大公因数的问题。这一过程被称为“欧几里得算法”
。
现在让我们用上述算法来处理 a =189和 b =105这两个数。每一步，我们给要计算的两个数标出下划线，并用小的数去除大的数，且从一行算式列到下一行时就舍弃大的数。余数为0时，表明上一行的余数就是所求的最大公因数，我们即终止该过程：
189=1×105+84，
105=1×84+21，
84=4×21，
所以，189和105的最大公因数就是21（189=9×21，105=5×21）。
这些算式本身是有用的，因为它们可以逆推，从而表示初始的两个数 a 和 b 的最大公因数 d 。我们从倒数第二个算式开始，并考察 d ，这种情况下求得21=105—84。接着，我们依次用每个等式来消除中间的余数：本例中，第一个算式给出84=189—105，于是最后我们有
21=105—（189—105）=2×105—1×189。
此外，有些有趣的理论成果，我们将在第六章来讨论。本节中，我们之前证明了 a 和 b 的任意公因数 c 也是任何形如 ax + by 的数之因数；由于 a 和 b 的最大公因数 d 可以表示成这种形式，即可通过倒推“欧几里得算法”的运算过程来求出，那么可知 a 和 b 的任何公因数 c 整除它们的最大公因数 d 。进一步说， a ′= a / d 及 b ′= b / d 有一个最大公因数1，因为比如假设 t 是 a ′和 b ′的一个公因数，那么 a ′= ta ″且 b ′= tb ″。我们要证明 t =1。（上撇号的使用是种提醒我们自己的方式，即 a ′和 a ″是 a 的因数：当然，任何新符号都可以使用。）前面的等式意味着 a = da ′= dta ″以及 b = db ′= dtb ″，由此可知 dt 是 a 和 b 的一个公因数。然而，由于 d 是 a 和 b 的最大公因数，于是有 t =1，而 a ′和 b ′实际上就互为素数。在我们的题例中， a =189， b =105，而 d =21；用这个最大公因数来做除法运算，便有189/21=9及105/21=5，而9和5没有公因数（除1之外）。
两个数 a 和 b 的最大公因数可以用 ax + by 这种形式来表示，这一事实处于众多与数相关的代数证明的中心位置，而“欧几里得引理”只是许多例子中的一个。