In elementary school, our math teachers taught us the operation of division:
Dividend = Divisor \times Quotient + Remainder
where the remainder must be smaller than the divisor. However, we might not have realized that the validity of this operation is almost the foundation for all arithmetic (number theoretic) properties of the natural numbers \mathbb{N}! In algebra, the above operational equation is called the division algorithm. If the division algorithm holds in an integral domain, then that domain possesses almost all ideal properties, such as unique factorization, which we refer to as the Fundamental Theorem of Arithmetic. Such an integral domain is called a Unique Factorization Domain (UFD).
Euclidean Domains
The Unique Factorization Theorem states that within an integral domain, every element can be decomposed into a product of "prime elements" of that domain, and this decomposition is unique up to the order of the factors and multiplication by units. The natural numbers we usually discuss satisfy the unique factorization theorem; for example, 60=2^2\times 3\times 5. This decomposition is unique. While this seems quite obvious, the unique factorization theorem is actually not trivial at all. First, not all rings of integers satisfy the unique factorization theorem. Consider the ring 2\mathbb{Z} consisting of all even integers. Note that in 2\mathbb{Z}, the numbers 2, 6, 10, and 30 are "primes" because they cannot be decomposed into the product of two even integers. However, 60=6\times 10=2\times 30, meaning there are two different decompositions. Therefore, in such a ring, the unique factorization theorem does not hold.
Among all integral domains where the unique factorization theorem holds, there is a class that is relatively simple, which we call Euclidean Domains. These are integral domains where a division algorithm can be performed. However, before further discussion, we must properly define the division algorithm. As we mentioned, for rational integers, we can stipulate that the remainder is smaller than the divisor based on the well-ordering principle, but general integral domains lack such a direct comparison. The following definition is based on the ring of Gaussian integers but can be generalized to other integral domains. (In a general integral domain, the norm would involve absolute values, as the norm is not necessarily positive.)
Division Algorithm
Division Algorithm: Given any 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 provided below is also general. Consider the complex number \frac{\alpha}{\beta} = A + Bi, where A, B \in \mathbb{Q}. Round A and B to the nearest integers C and D, such that |A-C| \leq 1/2 and |B-D| \leq 1/2. Then we can let \kappa = C + Di. Thus: \begin{aligned} \lambda &= \alpha - \kappa\beta \\ &= \beta \left( \frac{\alpha}{\beta} - \kappa \right) \\ &= \beta \left[ (A-C) + (B-D)i \right] \end{aligned} Then: \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, an equivalent definition is that for any complex number \alpha, there exists a complex integer \beta such that N(\alpha - \beta) < 1.
Bézout’s Identity
With the division algorithm, we can use the Euclidean algorithm (successive division) to find the greatest common divisor of two numbers. It is for this reason that integral domains where the division algorithm holds are called Euclidean domains. By reversing the steps of the Euclidean algorithm and substituting back, we obtain Bézout’s identity.
If \alpha, \beta are two non-zero Gaussian integers and d is 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 is 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 the product of two Gaussian integers \alpha\beta, then the Gaussian prime must divide at least one of the factors; that is, at least one of \pi|\alpha or \pi|\beta must hold.
We only need to assume \pi \nmid \alpha and then prove \pi | \beta. Since \pi \nmid \alpha and \pi is a prime, the greatest common divisor of \pi and \alpha is 1 (or more generally, a unit like -1, \pm i). Thus, 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, the left side is divisible by \pi, which means the right side must also be divisible by \pi. Therefore, \pi | \beta.
At this point, the materials needed to prove the unique factorization theorem are ready. We can see that the three topics above are generalizations of obvious properties of natural numbers, and the important unique factorization theorem is hidden within these simple basic facts.
Unique Factorization Theorem
First, it should be noted that the unique factorization theorem ignores the distinction between unit factors. That is, the theorem holds only if we treat two numbers that are associates of each other as the same number. Otherwise, 9 = 3 \times 3 = (-3) \times (-3) would count as two different decompositions. However, since -3 and 3 differ only by a unit, if we ignore this difference, there is only one decomposition.
The proof uses mathematical induction. First, N(\pm 1 \pm i) = 2. These are the four Gaussian integers with the smallest norm, and they are all Gaussian primes. Thus, unique factorization holds for \pm 1 \pm i.
Assume the unique factorization theorem holds for all integers with a norm less than N(\alpha). For a Gaussian integer \alpha, suppose it can be decomposed into products of Gaussian primes as \alpha = \pi_1 \pi_2 \dots \pi_s and \alpha = \pi'_1 \pi'_2 \dots \pi'_t. This implies \pi_s | \pi'_1 \pi'_2 \dots \pi'_t. According to Euclid’s lemma, \pi_s must divide one of \pi'_1, \pi'_2, \dots, \pi'_t. Since all \pi'_i are Gaussian primes, \pi_s must be an associate of one of them. Without loss of generality, let \pi_s be 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. Since N(\pi_1 \pi_2 \dots \pi_{s-1}) < N(\alpha), unique factorization holds for this value. Therefore, the unique factorization theorem also holds for integers with a norm equal to N(\alpha).
Thus, the unique factorization theorem holds in the Gaussian integers.
Review
Reviewing our proof, we find that the foundation of the proof is the division algorithm. However, the existence of a division algorithm is only a sufficient condition for the unique factorization theorem. That is to say, there exist non-Euclidean domains that also satisfy the unique factorization theorem, which requires more advanced knowledge. When we encounter cases where the unique factorization theorem does not hold, we have methods to bypass this difficulty, such as introducing "ideal numbers." This was the idea introduced by Kummer to solve Fermat’s Last Theorem, which we will discuss when the opportunity arises. Next, let us try our hand at using Gaussian integers to prove that Fermat’s Last Theorem holds for n=4.
Reference: Lectures on Number Theory (Vol. 2) by Sun Qi and Ke Zhao, Chapter 9.
When reposting, please include the original address of this article: https://kexue.fm/archives/2819
For more detailed reposting matters, please refer to: Scientific Space FAQ