Starting from Fermat's Last Theorem (Part 4): Unique Factorization Domains

从费马大定理谈起（四）：唯一分解整环 苏剑林 · 2014-08-17 · Mathematics number theory fermat's last theorem decomposition ring theory

Back in elementary school, our math teacher taught us the operation of division:

Dividend = Divisor × Quotient + Remainder

where the remainder must be smaller than the divisor. However, we probably never realized that this operation is, in essence, the foundation on which almost all arithmetic (number-theoretic) properties of the natural numbers$\mathbb{N}$ rest! In algebra, the equation above is called the division algorithm. If the division algorithm holds in an integral domain, then that domain enjoys almost all the properties we'd want from an "ideal" ring, including unique factorization — what we call the fundamental theorem of arithmetic. Such an integral domain is called a unique factorization domain (UFD).

Euclidean Domains

Euklid-von-Alexandria_1

Unique factorization says that in an integral domain, every element can be decomposed into a product of certain "prime elements" of that domain, and up to the order of multiplication and multiplication by units, this decomposition is unique. The natural numbers, as we usually understand them, satisfy unique factorization — for example $60=2^2\times 3\times 5$, and this decomposition is unique. This seems fairly obvious, but in fact unique factorization is far from trivial. First of all, not every ring of integers satisfies unique factorization. Consider the ring of all even numbers, $2\mathbb{Z}$. Notice that in $2\mathbb{Z}$, the numbers 2, 6, 10, 30 are all "prime," since none of them can be factored into a product of two even numbers. But $60=6\times 10=2\times 30$ has two genuinely different factorizations, so in a number ring like this, unique factorization fails.more

Among all the integral domains where unique factorization holds, there is a class that is comparatively simple, which we call Euclidean domains. These are the integral domains where a division algorithm (division with remainder) can be carried out. Before going further, though, we need to pin down exactly what "division with remainder" means, because — as we mentioned — the ordinary integers rely on the well-ordering principle to guarantee that the remainder is smaller than the divisor, but general integral domains have no natural notion of "smaller." The definition below is stated for the ring of Gaussian integers, but it generalizes readily to other domains. (In a general integral domain, the norm should be replaced by its absolute value, since the norm need not always be positive.)

Division with Remainder

Division algorithm: For any given complex integers $\alpha,\beta$, with $\beta\neq 0$, there exist complex integers $\kappa,\lambda$ such that
$$\alpha=\kappa\beta+\lambda$$
where $N(\lambda) < N(\beta)$.

The proof given below is also of a general nature. Consider the complex number $\frac{\alpha}{\beta}=A+B i,\ A,B\in \mathbb{Q}$, and round both $A,B$ to the nearest integers, i.e., choose an integer $C,D$ such that $|A-C| \leq 1/2,\ |B-D| \leq 1/2$. We can then take $\kappa=C+Di$, so that

$$\begin{aligned}\lambda=&\alpha-\kappa\beta\\ =&\beta\left(\frac{\alpha}{\beta}-\kappa\right)\\ =&\beta\left[(A-C)+(B-D)i\right]\end{aligned}$$

Consequently,

$$\begin{aligned} N(\lambda)=&N\left(\beta\left[(A-C)+(B-D)i\right]\right)\\ =&N(\beta)N\left((A-C)+(B-D)i\right)\\ =&N(\beta)\left[(A-C)^2+(B-D)^2\right]\\ \leq &N(\beta)\left[(1/2)^2+(1/2)^2\right]\\ < &N(\beta) \end{aligned}$$

From this we see that an equivalent formulation is: for any complex number $\alpha$, there exists a complex integer $\beta$ such that $N(\alpha-\beta) < 1$.

Bézout's Identity

Once we have the division algorithm, we can use the Euclidean algorithm (successive division, or "mutual subtraction/division") to find the greatest common divisor of two numbers. The Euclidean algorithm is precisely why domains admitting a division algorithm are called Euclidean domains. If we run the Euclidean algorithm process in reverse, substituting step by step, we obtain Bézout's identity.

Let $\alpha,\beta$ be two nonzero Gaussian integers, and let $d$ be their greatest common divisor. Then there exist Gaussian integers $\xi,\eta$ such that
$$\alpha \xi +\beta \eta=d$$
In other words, the greatest common divisor of two numbers can be written as a linear combination of those two numbers.

Euclid's Lemma

Euclid's Lemma
(also known as Euclid's First Theorem) states that if a Gaussian prime $\pi$ divides a product of two Gaussian integers $\alpha\beta$, then that Gaussian prime must divide at least one of the two factors — that is, at least one of $\pi|\alpha$ and $\pi|\beta$ holds.

We only need to assume $\pi\nmid \alpha$ and then prove $\pi |\beta$. Since $\pi\nmid \alpha$, and $\pi$ is itself a prime, the greatest common divisor of $\pi$ and $\alpha$ must be 1 (or, equivalently, it could be stated as $-1,\pm i$, a unit). So there exist Gaussian integers $\xi$ and $\eta$ such that

$$\xi \pi+\eta\alpha=1$$

Multiplying both sides by $\beta$,

$$\xi \pi \beta+\eta\alpha\beta=\beta$$

Since $\pi|\alpha\beta$, i.e., the left-hand side is divisible by $\pi$, the right-hand side must be too, and hence $\pi|\beta$.

At this point we have assembled all the ingredients needed to prove unique factorization. Notice that the three results above are each a generalization of some fairly obvious property of the natural numbers — and yet the important theorem of unique factorization is hiding precisely within these simple basic facts.

The Unique Factorization Theorem

First, note that unique factorization ignores differences arising from unit factors — that is, unique factorization holds only once we regard two numbers that are associates (differing by a unit) as "the same" number. Otherwise, $9=3\times 3=(-3) \times (-3)$ would have two different factorizations. But since -3 and 3 differ only by a unit, once we disregard that difference, there is really only one factorization.

The proof proceeds by mathematical induction. First, $N(\pm 1\pm i)=2$ — these are the four Gaussian integers of smallest norm, and they are all Gaussian primes. In other words, unique factorization holds for $\pm 1\pm i$.

Now suppose unique factorization holds for all integers of norm less than $N(\alpha)$. Consider a Gaussian integer $\alpha$, and suppose it can be factored into products of Gaussian primes in two ways, $\alpha=\pi_1 \pi_2 \dots \pi_s$ and $\alpha=\pi'_1 \pi'_2 \dots \pi'_t$. Then we have $\pi_s|\pi'_1 \pi'_2 \dots \pi'_t$. By Euclid's lemma, $\pi_s$ must divide one of the factors in $\pi'_1,\pi'_2,\dots,\pi'_t$, and since $\pi'_1,\pi'_2,\dots,\pi'_t$ are all Gaussian primes, $\pi_s$ must be an associate of one of them. Without loss of generality, say $\pi_s$ is an associate of $\pi'_t$. Then $\pi_1 \pi_2 \dots \pi_{s-1}$ and $\pi'_1 \pi'_2 \dots \pi'_{t-1}$ are associates as well, and $N(\pi_1 \pi_2 \dots \pi_{s-1}) < N(\alpha)$, so by the induction hypothesis unique factorization holds for this smaller number. Hence unique factorization also holds for integers of norm equal to $N(\alpha)$.

Therefore, unique factorization holds in the Gaussian integers.

Recap

Looking back over our proof, we see that its foundation is the division algorithm. However, the existence of a division algorithm is only a sufficient condition for unique factorization — that is, there exist non-Euclidean integral domains that still satisfy unique factorization, and understanding those cases requires more machinery. And when we do run into situations where unique factorization fails, there is a way around the difficulty: introducing "ideal numbers." This is precisely the idea Kummer introduced in his attempt to resolve Fermat's Last Theorem, and we will discuss it when the opportunity arises. For now, let's try out our new tools: we'll use the Gaussian integers to prove that Fermat's Last Theorem holds for the case $n=4$.

Reference: Chapter 9 of Lecture Notes on Number Theory (Vol. 2) by Sun Qi and Ke Zhao.