Integral Domains, Gaussian Integer, Unique Factorization
Z[√3] is not the only algebraic construct for which Euclid's Algorithm and the Fundamental Theorem of Arithmetic (uniqueness of the prime factorization) make sense. The very first result in this spirit was obtained by Gauss who considered the ring
For A = a + bi from Z[i], define
For any given pair A and B from Z[i],
A = BQ + R, and N(R) < N(B)
|(2)|||(x - r)² + (y - s)²| ≤ (½)² + (½)² = ½ < 1|
Thus it follows that Euclid's Algorithm is applicable to the Gaussian integers. And, as a consequence, the prime factorization is unique in Z[i]. Let's briefly consider a few examples.
- Z[i] has just four unities: ±1 and ±i.
- 2 is composite (not prime) in Z[i].
Indeed, 2 = (1 + i)(1 - i), and N(1 + i) = N(1 - i) = 2, so none of the factors is a unity.
- 3 is prime in Z[i].
Assuming 3 = AB we first get N(3) = 9 = N(AB) = N(A)N(B). If neither A nor B is unity,
N(A) = N(B) = 3.Let's show that the equation N(A) = 3has no integer solutions. Unless a = b = 0 (mod 9), (a² + b²) (mod 9)is one of the sequence 1, 4, 7, (1 + 1) = 2, (1 + 4) = 5, (1 + 7) = 8, (4 + 4) = 1, (4 + 7) = 2, (7 + 7) = 5 (mod 9).But 3|a and 3|b implies 9|(a² + b²) and, hence, 9|3. A contradiction.
- 5 is composite (not prime) in Z[i].
Indeed, 5 = (1 + 2i)(1 - 2i), and N(1 + 2i) = N(1 - 2i) = 5, so none of the factors is a unity.
- Solve x² + y² = z² in integers.
To solve the Pythagorean equation, first assume that Pythagorean triples x, y, z exist. We may then restrict our search to triples with
gcd(x, y, z) = 1.This is the same as gcd(x, y) = 1.Factor the left hand side into (x + yi)(x - yi).I leave this without a proof that gcd(x, y) = 1implies gcd(x + yi, x - yi) = 1.It would be nice to conclude from (x + yi)(x - yi) = z²that for some Gaussian integers A and B, x + yi = A²and x - yi = B².But this may not be the case. In addition, we must consider, say, x + yi = iA² and x - yi = -iB² as valid possibilities.
In the first case, let A = u + vi, then
x + yi = (u² - v²) + 2uvi,and x = u² - v², y = 2uv.Substitution yields z = u² + v².In the second case, the roles of x and y are reversed.
5 = (1 + 2i)(1 - 2i) = (2 + i)(2 - i). Does this contradict the Fundamental Theorem of Arithmetic in Z[i]?
The ease with which Euclid's Algorithm was extended to Z[√3] and Z[i] might have created an illusion that the algorithm is valid in any Z[√m]. (The proof of the fundamental inequality (4) obviously works for m = -1, ±2.) However, it can be proven [Stark, Theorem 8.25] that, for
It's also possible to define Q[√m] where Q is the set of all rational numbers. (These are called quadratic fields.) A member of Q[√m] is called a (rational) integer if it's either a (regular) integer, i.e. belongs to Z, or is a root of a quadratic monic polynomial with integer coefficients. (See [Stark, p 265 and on] for the reason for such a definition.)For Q[√m], there exists only a finite set of numbers m for which Euclid's Algorithm works. These are -11, -7, -3, -2, -1, 2, 3, 5, 6, 7, 11, 13, 17, 19, 21, 29, 33, 37, 41, 57, and 73.
Interestingly, the prime factorization may be unique even without valid Euclid's algorithm. For negative m and in addition to the list above, this is true for m = -19, -43, -67, -163. It's an unsolved problem whether the number of positive such m's is finite.
The fact that the prime factorization is not always unique bedeviled the best mathematical minds. It was not realized, probably, until 1840s. Two famous attempts to prove Fermat's Last Theorem failed because of their authors' belief in the universality of the unique factorization.
After his mistake was discovered by Dirichlet (1843),
In 1847, G. Lamé (1795-1870) gave a talk at a meeting of the French Academy where he announced a solution to Fermat's Theorem and suggested that the glory of solving the famous theorem should be shared with
I'll end with an example of two prime factorizations that violate the Fundamental Theorem of Arithmetic. -5 is among those integers m for which Z[√m] does not have the property of unique factorization. Let's consider
|(2)||6 = 2×3 = (1 + √-5)(1 - √-5)|
All four factors involved are prime in Z[√m]. The proof of their primality is based on the fact that the equations
- A. D. Aczel, Fermat's Last Theorem, Four Walls Eight Windows, 1996
- A. H. Beiler, Recreations in The Theory of Numbers, Dover, 1966
- J. H. Conway and R. K. Guy, The Book of Numbers, Springer-Verlag, NY, 1996.
- H. M. Stark, An Introduction to Number Theory, The MIT Press, 1995, Ninth printing.