## How to Use Algebraic Number Theory

It occurred to me that I hadn’t written about number theory in a while. Here’s a good application of algebraic numbers, which gives a fairly simple proof of a theorem that has a very complicated elementary proof.

Let us look at primes that leave a remainder of 1 when divided by 4 (we say they’re equivalent to 1 mod 4). We have 5 = 1^2 + 2^2, 13 = 2^2 + 3^2, 17 = 1^2 + 4^2, and 29 = 2^2 + 5^2. This doesn’t always apply to composite numbers: there’s no way of expressing 15 as the sum of two squares.

Now, there’s an elementary proof of this due to Euler and a few more non-elementary ones, but they either rely on difficult concepts or are too long to remember. A better proof relies on algebraic number theory.

First, the ring Z[i] = {a + bi: a and b are in Z}, where i is the square root of -1, is a unique factorization domain, a fact I’ll prove shortly. So if a number p in the ring divides a product cd but not c or d, it’s reducible, say as qr where q and r are not units.

Second, we can define a function N on the ring by N(a+bi) = a^2 + b^2. Clearly, N(a+bi) will always be a positive (rational) integer, since a and b are integers. More interestingly, N is a multiplicative function – in other words, N(xy) = N(x)*N(y) for all x and y in the ring.

To see why that holds, let’s just do the calculation. N(a+bi)N(c+di) = (a^2 + b^2)(c^2 + d^2) = a^2*c^2 + a^2*d^2 + b^2*c^2 + b^2*d^2. On the other hand, since i*i = -1, we have N((a+bi)(c+di)) = N(acbd + (ad+bc)i) = (acbd)^2 + (ad+bc)^2 = a^2*c^2 – 2abcd + b^2*d^2 + a^2*d^2 + 2abcd + b^2*c^2 = a^2*c^2 + a^2*d^2 + b^2*c^2 + b^2*d^2.

Third, if N(a+bi) = 1, then a+bi is a unit. This is because 1 = a^2 + b^2 = (a+bi)(abi), so we have 1/(a+bi) = abi which is in the ring.

Fourth, if p is any prime integer, then p clearly doesn’t divide x+i or xi where x is any integer. On the other hand, if p is equivalent to 1 mod 4, then we can write p as 4n + 1, where n is an integer. But as I will show in a moment, p divides x^2 + 1 when x = (2n)!, which means it’s not prime in the ring. Therefore, it’s reducible, say to qr. N(p) is simply p^2, and qr are not units, so N(q), N(r) > 1. Therefore, N(q), N(r) = p. Writing q as a + bi, we get p = a^2 + b^2.

To see that p divides ((2n)!) ^2 + 1, note that k is equivalent to -(4n + 1 – k) mod p, so (2n)! is equivalent to ((-1)^2n)(2n+1)(2n+2)…(4n). We have (-1)^2n = 1^n = 1, so we get ((2n)!)^2 = (2n)! * (2n+1)…(4n) = (4n)! mod p.

Now, for each number c between 1 and 4n, we can find another number d such that cd = 1 mod p. If we can’t, then there exist no integers d and q such that cdpq = 1, so the ideal (c, p) in Z doesn’t contain 1, so it’s smaller than Z. But (p) is a maximal ideal in Z, so (c, p) = (p) and c = pq for some q. In particular, c is not in the range [1, 4n].

In fact, unless c is 1 or 4n, d will be different from c. Otherwise, we get c^2 = 1 mod p, so p divides c^2 – 1 = (c-1)(c+1). This means that p divides c-1 (in which case c = 1) or c+1 (in which case c = 4n). So we get 2n-1 pairs of numbers of the form {c, d}, cd = 1 mod p. In calculating the value of (4n)! mod p, we can ignore these pairs, since 1*x = x for all x. Then (4n)! = 4n mod p, and ((2n)!)^2 + 1 = (4n)! + 1 = 4n + 1 = 0 mod p, i.e. p divides ((2n)!)^2 + 1.

Actually, there’s an indirect way of showing that if p = 4n + 1 then we can always find some x such that x^2 = -1 mod p, but it requires me to talk a little bit about group theory and I don’t want to do that yet.