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 Z[i] = {a+bi: a,bZ, i = (-1)}. This is the set of complex numbers with integer coefficients. In his honor the numbers are called the Gaussian Integers.

Extension of Euclid's Algorithm to Z[3] was made possible with the introduction of the function N and the establishment of an inequality that ensured convergence of Euclid's Algorithm.

For A = a+ bi from Z[i], define A' = (a+bi)' = a-bi and N(A) = AA' = a² + b². For Z[i], N(A) is never negative and is only 0 for A = 0, i.e. when a = b = 0. For thus defined N, the following holds

The proof follows that for Z[3] but is a little simpler. The inequality (4) is replaced with a more straightforward

(2)	|(x-r)2 + (y-s)2| (½)2 + (½)2 = ½ < 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.

1. Z[i] has just four unities: ±1 and ±i.

2. 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. 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) = 3 has 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.

4. 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.

5. 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) = 1 implies 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.

Question

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 m < 0, Z[m] has the unique factorization property only for either m = -1 or m = -2. For m > 0, Z[m] does not have that property if m = 1 (mod 4).

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.)

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), E.E.Kummer (1810-1893) developed the whole new branch of mathematics - the theory of ideals - to tackle the problem of unique factorization. In 1857, his contribution to mathematics has been acknowledged with a gold medal from the French Academy of Science.

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 J.Liouville (1809-1882) to whom he ascribed the method of solution. In a subsequent talk, Liouville brushed aside the praise and pointed out that the assumption of unique factorization made by Lamé had invalidated the proof. Lamé left his mark in the Theory of Elasticity and Mathematical Physics, he introduced curvilinear coordinates, and in his honor were named an equation, a set of coefficients, and a special class of functions.

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² + 5b² = ±2 and a² + 5b² = ±3 have no integer solutions. This is easily established considering the equations modulo 5. Indeed, modulo 5 we have just two equations a² = 2 and a² = 3. Both are impossible since, for any a, a² = 0, 1, or 4 (mod 5).

Reference

1. A.D.Aczel, Fermat's Last Theorem, Four Walls Eight Windows, 1996
2. A.H.Beiler, Recreations in The Theory of Numbers, Dover, 1966
3. J.H.Conway and R.K.Guy, The Book of Numbers, Springer-Verlag, NY, 1996.
4. H.M.Stark, An Introduction to Number Theory, The MIT Press, 1995, Ninth printing.

• Strange Integers
  • Divisors and Primes
  • Fundamental Theorem of Arithmetic
  • Gaussian Integers
  • Remarks and Examples
• Constructible Numbers
  • Examples
  • Four Problems of Antiquity
  • A Property of Cubic Equations