大约公元前350年，欧几里得在他伟大的十三卷著作《原本》中，用了许多篇幅来讨论素数。特别是他证明了每一个比1大的数（即每个比1大的正整数）要么本身是一个素数，要么可以写成一系列素数的乘积，如果不考虑这些素数的在乘积中的顺序，那么写出来的形式是唯一的。例如：

14=2×7，21=3×7，等等。

等号右边的表达式分别是数14与21的“素数分解”。这样我们能把欧几里得的结果表达为：每一个大于1的奇数要么是素数，要么具有唯一的（次序变化不计）素数分解。这个事实被称为算术基本定理，它告诉我们素数好比化学家的原子——所有整数得以构成的基本砌块。

算术基本定理(The fundamental theorem of arithmetic) 即唯一分解定理, 告诉我们每一个大于1 的整数若不是质数都可以写成有限多个质因子的乘积且经过适当排序其写法唯一. 此定理看似自然且明显, 但仍需一个正式的证明.

这里我们又碰到一个典型的有关存在性与唯一性的问题. 这里的存在性指的就是对一大于1 的整数可以找到有限多个质数使其可以写成这些质数的乘积, 而唯一性就是指的就是写法唯一. 由于正整数和负整数的分解只差一个负号, 我们只需考虑正整数的情况.

Theorem 1.5.1(The Fundamental Theorem of Arithmetic) 假设 a且 a> 1, 则存在 p1,..., pr, 其中 pi 是相异的质数, 满足

a= p11prr, ni, i{1,..., r}.

如果 a 可以分解成另外的形式 a= q11qss, 其中 qi 是相异的质数, 则 r= s 且经过变换顺序可得 pi= qi, ni= mi, i{1,..., r}.

证 明. 我们分开来证存在性与唯一性.

首先来看存在性: 简单来说存在性就是要证明每一个大于1 的整数都可以写成有限多个(可以相同)质数的乘积. 如果 a 本身是个质数, 则 a= p1(即 r= 1, n1= 1), 得证存在性. 如果 a 不是质数呢? 由定义知存在 a1, b1且 a1 1, b1 1 满足 a= a1b1. 接下来就是看 a1, b1 是不是质数了. 如果其中有一个不是质数, 我们就继续分解下去直到得到质数为止. 这个过程一定会停下来因为每次分解后得的数越来越小. 当然最后就可以将 a 写成一些质数的乘积了. 这样的证明方式, 相信大家会有一种说不清楚的感觉, 所以我们还是用数学归纳法来证明. 当 a= 2 时由于2 是质数, 所以在这情况存在性是对的. 接着假设对所有从2 到 a- 1 的整数存在性是对的. 如果 a 是质数, 那存在性自然成立. 如果 a 不是质数, 则知 a= a1b1其中 a1, b1且1 < a1< a 及1 < b1< a. 故利用归纳假设知 a1 和 b1 都可写成有限多个质数的乘积, 所以得证 a 也可以写成有限多个质数的乘积.

我们依然用归纳法证唯一性, 假设

a= p11prr= q11qss,

其中 p1,..., pr 是两两相异的质数, 且 q1,..., qs 也是两两相异的质数. 由于 p1 是质数, 故由 p1| a= q11qss 以及Corollary 1.4.3 知存在某个 j{1,..., s} 满足 p1| qj. 变换一下顺序我们可以假设 p1| q1. 由于 q1 是质数, q1 的因子只能是±1 或±q1. 故由 p1| q1 知 p1= q1. 现在考虑

= p11prr= q11qss.

由于 a/p1< a, 故利用唯一性的归纳法假设我们得 r= s 且 p1= q1,..., pr= qr 以及 n1= m1, n2= m2,..., nr= mr, 故得证唯一性.

一般来说我们将一正整数 a 写成质数之乘积 a= p11prr时, 为了唯一性我们要求每个质数 pi 的次方 ni 都是正的, 也就是说我们只挑出 a 的质因子 p1,..., pr. 不过当要讨论两正数 a, b 时为了方便比较, 我们通常会挑出 a 和 b 所有的质因子再将 a, b 写成这些质数之乘积的样子. 也就是说可写成 a= p11prr以及 b= p11prr其中对于 i{1,..., r}, pi| a 或 pi| b, 且 ni 0, mi 0. 注意这里由于 a 的质因子未必就是 b 的质因子, 反之亦然, 所以 ni, mi 有可能为0. 这样写法的方便性就是我们不必区分哪些 pi 是 a 的质因子, 哪些是 b 的质因子. 利用这样的写法我们很容易将 a, b 的最大公因子表示出来.

Proposition 1.5.2 假设 a, b且 a, b> 1. 若 a= p11pr1且 b= p11prr, 其中 p1,..., pr 为相异质数且 ni, mi 0, 则 a, b 的正公因子都可写成 p11prr 的形式, 其中0 ti min{ni, mi}. 特别地, 我们有

gcd(a, b) = p111prrr.

证 明. 首先回顾一下min{x, y} 表示 x, y 中最小之数. 现假设 d 是 a, b 的正公因子, 则由 d| a 我们知若 p 是 d 的质因子, 则由 p| d 知 p| a. 故由Corollary 1.4.3 知存在 i{1,..., r} 使得 p| pi. 因此由 p, pi 皆为质数得 p= pi. 也就是说 d 的质因子必在{p1,..., pr} 中, 故 d 一定可以写成 p11prr 的形式, 其中 ti 0. 又由于对任意 i{1,..., r} 皆有 pii| d 故 pii| a, 亦即 pii| p11prr. 由于若 i j 则 pi pj, 知此时gcd(pii, pjj) = 1, 故由 1.2.7(1) 得 pii| pii, 也就是说 ti ni. 同理由 d| b 可得 ti mi, 故得证0 ti min{ni, mi}.

现令 d= p111prrr, 马上得知 d 为 a, b 之公因子. 又由上知任意 a, b 的公因子 d' 皆满足 d'| d, 故知 d= gcd(a, b).

虽然Proposition 1.5.2 也是一个求得两个数之最大公因子之方法, 不过在实际情况(尤其是处理很大的数时) 由于分解质因子是很困难的事情, 所以仍是以辗转相除法得最大公因子较管用. Proposition 1.5.2 重要之处是它很明确的告诉我们最大公因子长什么样子, 这在一些抽象理论的推导是有用的.

接下来我们可以利用Proposition 1.2.8 将最小公倍数写下.

Corollary 1.5.3 假设 a, b且 a, b> 1. 若 a= p11pr1且 b= p11prr, 其中 p1,..., pr 为相异质数且 ni, mi 0, 则

lcm(a, b) = p111prrr.

证 明. 由于 ab= p111prrr 利用Proposition 1.2.8 以及Proposition 1.5.2 知

lcm(a, b) = = p11111prrrrr.

对任意二数 x, y, 不失一般性我们假设 x y, 此时我们有min{x, y} = y 且max{x, y} = x, 因此得 x+ y= min{x, y} + max{x, y}. 所以对任意 i{1,..., r} 我们皆有max{ni, mi} = ni+ mi- min{ni, mi}, 因此得证本定理.

当我们有多于两个的整数时, 我们就可以利用质因子分解以及Proposition 1.2.12 和Proposition 1.2.13 将他们的最大公因子和最小公倍数写下. 例如若 a= p11pr1, b= p11prr且 c= p11prr, 其中 p1,..., pr 为相异质数且 ni, mi, ti 0, 则

gcd(a, b, c) = p1111prrrr,

lcm(a, b, c) = p1111prrrr.