Topics in Commutative Rings: Unique Factorisation (3)

Example 1: The Gaussian Integers Z[i]

Let’s pick the norm function N : Z[i]-{0} → N where N(a+bi) = (a+bi)(a–bi) = a²+b². We know that N is a multiplicative function, i.e. N(r)N(s) = N(rs). Instead of checking this by brute force, we write N(x) = x·x^c, where (a+bi)^c = a-bi is the conjugate of a+bi. It’s easy to see that conjugation commutes with addition and multiplication:

$(x+y)^c = x^c + y^c,\ (xy)^c = x^c y^c$ , for all $x,y\in\mathbf{Z}[i].$

Then the norm map is multiplicative because:

$N(xy) = (xy)(xy)^c = (xy)(x^c y^c) = (xx^c)(yy^c) = N(x)N(y).$

N as an Euclidean Function

To prove that N is Euclidean, we need to show that for any two Gaussian integers, x, y (y≠0), we can write:

x = yq + r, where r=0 or N(r) < N(y).

[ Heuristically, r is the remainder and q is the quotient in the division x/y. ] Thus, write x/y = a+bi, where a and b are rational numbers. Taking out the integer part, we can write:

x/y = q + s, where q is a Gaussian integer, and -1/2 < Re(s), Im(s) ≤ 1/2.

Hence x = yq + (ys), where N(ys) = N(y)N(s). But N(s) = Re(s)² + Im(s)² ≤ (1/4) + (1/4) < 1 so N(ys) < N(y). Hence:

The ring of Gaussian integers, Z[i], is an Euclidean domain, and hence a principal ideal domain, and hence a unique factorisation domain.

The presence of an explicit Euclidean function is a wonderful thing from the computational point of view. For it allows us to explicitly perform the Euclidean algorithm. Let’s go back to the final example in the 3rd article in the series on Ring Theory.

Problem 1 : Given b = 8+i, a = 5-14i, compute gcd(a, b).

Answer : Apply the Euclidean algorithm.

(5-14i)/(8+i) = 0.4 – 1.8i, so we take q = 0 – 2i and r = a–bq = 3+2i.
(8+i)/(3+2i) = 2-i, so the gcd = 3+2i. ♦

Problem 2 : Classify all primes in Z[i].

Answer : Let x be prime in Z[i]. Then x divides x·x^c = N(x). Hence x must divide some integer. Since an integer is a product of prime integers, x | p for some prime integer p. So it suffices to consider how integer prime factors factor in Z[i]. (Sorry for the awkward sentence. )

p = 2 : 2 = (-i)(1+i)²
p ≡ 3 (mod 4) : if x|p, then N(x) divides N(p) which is p². Hence N(x) = p or p². If N(x) = p, then writing x=a+bi gives a²+b²=p which is unsolvable since p is 3 mod 4.
p ≡ 1 (mod 4) :
- First note that m² ≡ -1 (mod p) has a solution. [ This follows from Wilson’s theorem: let p=4k+1. Then (4k)! ≡ -1 (mod p). Prove that (4k)! ≡ (2k)!². ]
- Let y = m+1i. Now y and p share a common factor, for if y is coprime to p, then y^c is coprime to p^c = p, so N(y) = y·y^c is coprime to p as well (contradiction).
- Now consider x = gcd(y, p) ≠ 1. This x divides p, but it cannot be p since y is clearly not divisible by p. Thus x is a proper factor of p, i.e. N(x) = p.

In particular, we have proven as a corollary that every prime (integer) which is 1 mod 4 can be expressed as a sum of two squares.

Problem 3 : Express the prime p = 10061 as a sum of two squares.

Answer : The first step is to solve for m² ≡ -1 (mod p). Fortunately, there’s a fast general algorithm for computing square root modulo p : the Shanks-Tonelli algorithm. This gives us: 4602 mod 10061. Now it remains to compute gcd(4602+i, 10061) by Euclidean algorithm.

10061 ÷ (4602+i) gives quotient=2, remainder=857-2i.
(4602+i) ÷ (857-2i) gives quotient=5, remainder=317+11i.
(857-2i) ÷ (317+11i) gives quotient=3, remainder=-(94+35i).
(317+11i) ÷ (94+35i) gives quotient=3-i, remainder=0.

Hence, the gcd is 94+35i, which gives 10061 = 94² + 35².

Problem 4. Find the number of integer solutions to $x^2 + y^2 = n$ , where $n = 2^3\times 3^4\times 5^2 \times 7^2 \times 13 \times 17$ .

Answer: We need to count the number of Gaussian integers x for which N(x) = n. Factorise x as a product of primes. Recall that there’re three types of primes:

(1+i) : N(1+i) = 2;
p (a prime integer which is 3 mod 4) : N(p) = p²;
x_p = a+bi (a Gaussian integer prime, where a²+b²=p and p is 1 mod 4) : N(x_p) = p. There are two possibilities for x_p, after taking into account associates.

Hence, to obtain a norm of n we need to mix-and-match products of the form:

$\text{unit}\times (1+i)^3 \times 3^2 \times\left\{\begin{matrix} (1+2i)^2\\(1+2i)(1-2i)\\(1-2i)^2\end{matrix}\right\} \times 7 \times \left\{\begin{matrix}2+3i\\2-3i\end{matrix}\right\} \times \left\{\begin{matrix}1+4i\\1-4i\end{matrix}\right\}$

Since there’re 4 units, this gives 4×12 = 48 possibilities. For example, if we pick the top entry in all three cases, then we get:

$(1+i)^3 \times 3^2 \times (1+2i)^2 \times 7\times (2+3i)\times(1+4i) = 10962+7434i,$

which has norm = 175429800 = n. ♦

Example 2: The Ring Z[√-2]

Let R = Z[√-2], which is the set of all complex numbers x = a+b√-2. Once again, we define its conjugate to be x^c = a–b√-2 and the norm of x is N(x) := x·x^c = a²+2b². Things progress exactly following the case of the ring of Gaussian integers.

For starters, conjugate commute with addition and multiplication, so in particular, the norm is multiplicative:

$N(xy) = (xy)(xy)^c = (xy)(x^c y^c) = (xx^c)(yy^c) = N(x)N(y).$

Once again, N is an Euclidean function because if we write x/y = a+b√-2 for rational a and b, then we can express:

x/y = q + s, where -1/2 < Re(s) ≤ 1/2, and (-1/2)√-2 < Im(s) ≤ (1/2)√-2.

Thus N(s) ≤ 1/4 + 1/2 < 1. This enables us to write x = yq + (ys) where N(ys) = N(y)N(s) < N(y). Practice through the following problems. 🙂

Problem 1. Find gcd(32+37√-2, 83-2√-2).

Problem 2. Classify all primes in the ring Z[√-2]. [ You may need to consider quadratic residues modulo p. ]

Problem 3. Express the prime p = 10009 in the form a²+2b² for integers a and b. [ Hint: x=2835 is a solution to x² ≡ -2 (mod p). ]

Problem 4. Find the number of solutions to $a^2 + 2b^2 = n$ , where $n=2^4\times 3^3\times 5^2 \times 7^2 \times 11 \times 17$ . Give a sample solution.

Bonus Problem. Find all integer solutions to x² + 2 = y³.

Answer. By considering mod 4, we see that y must be odd. Hence x is odd. Now factor the equation in Z[√-2], as:

$\overbrace{(x+\sqrt{-2})}^a\overbrace{(x-\sqrt{-2})}^b = y^3.$

Since a – b = 2√-2, gcd(a, b) must divide 2√-2. But since x is odd, it is coprime to 2. Thus, x+√-2 is coprime to √-2. Now, a and b are two coprime elements whose product is a cube, so each of them must be a cube, i.e. a = u³, b = v³.

[ Subtle issue: to be specific, a and b are only associates with cubes. But the only units here are ±1, which are both cubes, so we may assume a and b are cubes. ]

This gives $2\sqrt{-2} = a-b = u^3 - v^3 = (u-v)(u^2+uv+v^2)$ . Now we only need to take all factors of 2√-2 and solve. E.g.:

$u-v=2\sqrt{-2}, u^2+uv+v^2=1$ . Solving them gives: $u=1+\sqrt{-2}$ and $v = 1-\sqrt{-2}$ which are legit elements of Z[√-2]. This gives $a = u^3 = -5+\sqrt{-2}$ and $b = -5-\sqrt{-2}$ . So x=-5, y = uv = 3.

Going through all possible cases, the only solutions are (x, y) = (-5, 3) and (5, 3). ♦

Other Euclidean Rings

Let’s consider other complex quadratic rings, i.e. rings of the form R = Z[α], where α is a non-real complex number which satisfies $\alpha^2 + m\alpha + n = 0$ for some integers m and n. The reader may check that Z[α] is an Euclidean ring for the following cases:

$\alpha = \sqrt{-1}, \sqrt{-2}, \frac{1+\sqrt{-3}}2, \frac{1+\sqrt{-7}}2, \frac{1+\sqrt{-11}}2,$

with the Euclidean function given by the norm N(x + yi) = x² + y². The final case is a bit tricky, so let’s plot out the set of all elements of Z[(1+√-11)/2] on the complex plane. This forms a lattice on the plane, as indicated by the black dots.

Now draw a circle of radius 1 around each of the points A(0, 0), B(1, 0), C(α, 0), D(1+α, 0), where α = (1+√-11)/2. Every complex number can be written in the form q+s, where $q\in \mathbf{Z}[\alpha]$ and s lies in ABCD. Since the four circles cover the parallelogram, it follows that we can pick s such that |s| < 1.

Conclusion: for any $x,y\in \mathbf{Z}[\alpha], y\ne 0$ , write x/y = q+s. Then the above observation tells us we can pick |s| < 1, or N(s) < 1. This gives: x = yq + ys, where N(ys) = N(y)N(s) < N(y). Thus N is still an Euclidean function for Z[(1+√-11)/2].

Finally, the following results are known, but we don’t have the tools to prove them for now.

Rings which are PIDs but not Euclidean. Above we’ve listed rings which are Euclidean. However, the rings Z[α] for $\alpha=\frac{1+\sqrt{-19}}2, \frac{1+\sqrt{-43}}2, \frac{1+\sqrt{-67}}2, \frac{1+\sqrt{-163}}2$ turn out to be PIDs as well. Unfortunately, they are known to be non-Euclidean, so Euclid’s algorithm doesn’t work here.
Rings which are UFDs but not PIDs. We had already seen some example in the previous post. E.g. Z[x] and R[x, y] are UFDs but not PIDs. However, in the case of quadratic rings, all UFDs are necessarily PIDs. This follows more generally from the theory of Dedekind domains, but that’s another story for another day.
Rings which are not even UFDs. For example Z[√-5] is not a UFD. To see why, factor 6 = 2·3 = (1+√-5)(1-√-5). Then the elements 2, 3, 1+√-5, 1-√-5 have norms 4, 9, 6, 6 respectively. If the expressions can be broken down any further, we would obtain irreducible elements with norm 2 or 3. But this is impossible since a²+5b² = 2 or 3 has no solution. It is known that any complex quadratic ring which is a UFD must be one of those in case 1 above.
Subrings of the above. As a general guide, a subring is even less likely to be a UFD than the ring itself. E.g. as stated above Z[(1+√-3)/2] is a UFD. But the subring Z[√-3] is not a UFD since 4 = 2·2 = (1+√-3)(1-√-3) cannot be factored any further. [ In the case of Z[(1+√-3)/2], this wouldn’t be a problem since 1+√-3, 1-√-3 and 2 are all associates. ]
Real quadratic rings. We’ve excluded rings of the form Z[√2], Z[√3], Z[(1+√5)/2] etc. Things are much stickier since the unit groups are infinite here. E.g. (2+√3) generates an infinite unit group in Z[√3]. So we’ll just have to defer these things till another time, when we have a more general theory.