Complex Extensions, Adjoining sqrt(-3)

Adjoining sqrt(-3)

Let q be the square root of -3, as we did in the previous section, but this time simply adjoin q, rather than (1+q)/2. Half the points in the previous lattice go away, leaving a lattice of rectangles. The points that are missing are the centers of these rectangles. If we put these back in, the previous lattice appears, as though we had adjoined (1+q)/2.

These missing centers are important for another reason; their absence derails the gcd algorithm, which use to work. Try running gcd(2,1+q). If 2 starts a series of rectangles, 1+q lands smack in the center of the first cell, and is exactly 1+q distant from all four corners. Once again the gcd algorithm is stuck, and we don't have a ufd.

As if in confirmation, 4 = 2×2 = (1+q)×(1-q). The numbers 2 and 1+q have norm 4, and there is no a+bq such that a2+3b2 = 2, so 2 and 1+q are irreducible, and 4 factors in two different ways.

By definition, let an odd prime in the ufd have odd norm. This is really any prime other than 2, for if p times p conjugate equals 2 times something else, then either p or p conjugate is an associate of 2, (by unique factorization), and we're talking about 2 after all.

Boldly try to factor x in Z[q] by factoring x in the underlying ufd, where we adjoined (1+q)/2. As you write down the factorization of x, select associates that don't use half integer coefficients. You can always do this, as demonstrated in the previous section. All these primes are in Z adjoin q, and their product is in Z adjoin q. If we ignore sign, the selections of the odd primes are unambiguous. Each has but one associate, up to sign, in Z[q]. The exception is 2, which we'll get to in a minute. Thus we have completely and uniquely factored x, or an associate of x, using primes that happen to live in Z[q].

If the product of primes gives -x, negate one of the primes to produce x. That really doesn't change the factorization. If the product of primes is some other associate, not -x, then that product is off by a factor of (1±q)/2. Let x consist of odd primes, hence |x| is odd. We showed in the last section that 4 of the six associates of x have half integers. The product of primes is one of these associates, and does not have half integers, hence it is x or -x. Therefore, if the product is off by some unit other than ±1, then x includes a factor of 2. In this case we chose the wrong associate of 2. Select the correct associate, ±2, 1±q, or -1±q, and the product equals x, exactly.

In summary, Z[q] is almost a ufd. Every number factors uniquely into a product of odd primes, but if x is "even", any of the six elements that are 2 units from the origin can be used interchangeably to build the powers of 2.

Let's try to characterize the integer solutions to x2 + 3y2 = z2.

To be coprime, 3 cannot divide x or z.

Look mod 4 to show x cannot be even.

Look mod 16 to show 4 cannot divide z. If z is even it only has one factor of 2. That's good, since 2 is our trouble maker.

Split x2+3y2 into (x+yq)×(x-yq). If these have a common factor, it also divides x and 2yq. We're postponing 2 for the moment, and if q divides x then 3 divides x, which we ruled out. Thus all odd primes dividing x+yq are squared, and we can work with (u+vq)2 as before.

If z is odd then we are done, and the following formulas apply.

u > 0, v > 0, u and v coprime, u and v of different parity:
x ← u2 - 3v2
y ← 2uv
z ← u2 + 3v2

When z is odd, x is odd and y is even (look mod 4), so our components are in the right places. Make u and v positive, and understand that x might come out negative. Show that u and v are coprime, and have opposite parity. When u = 5 and v = 2, x = 13, y = 20, and z = 37. Swap u and v to get x = -71, y = 20, and z = 79.

If z is even we need an associate of 2. We can't use 2, because then x and y would be even. Since x+yq and x-yq have the same norm, we need to assign one associate to each factor. Multiply the above formulas by 1+q or 1-q to get the following.

u > 0, v ≥ 0, u and v coprime, u and v of different parity:
x ← u2 - 3v2 - 6uv
y ← u2 - 3v2 + 2uv
z ← 2u2 + 6v2

x ← u2 - 3v2 + 6uv
y ← u2 - 3v2 - 2uv
z ← 2u2 + 6v2

This time v can be 0, making u = x = y = 1, and z = 2. In this case 1 + q is the one and only prime. Assuming u+vq gathers up some odd primes, make u and v positive. This might swap the two solutions. Note that the two triples are always different, since uv is nonzero. Given a triple, u and v are determined, because we have unique factorization on the odd primes. Thus the map is 1-1, and all triples have been characterized.

When u = 5 and v = 2, x = -47, y = 33, z=74, or, x = 73, y = -7, and z = 74.

Factoring p

If p is an odd prime, when does x2+3y2 = p have a solution? In other words, when does p split into x+yq times x-yq? This was solved by Fermat, and it is similar to the splitting of p in the gaussian integers.

Reduce mod p, and -3 has to be a square. By quadratic reciprocity, this happens iff p = 1 mod 3. So we don't have to worry about p = 2 mod 3; that has no solution. Thus 11, for instance, is still prime.

Since -3 is a square, write u2+3 = 0 mod p. Thus u+q times u-q is a multiple of p. Unique factorization applies for odd primes, so p divides u+q, or p divides u-q, or p splits. The first two choices are impossible, so p factors into a product of conjugate primes. Factorization is unique, hence there is one solution, up to sign, for x2+3y2 = p.

As with the gaussian integers, p can be split efficiently, even if it is huge. Find u such that u3-1 = 0 mod p. Factor out u-1, which leaves u2+u+1. This splits into u+(1±q)/2. Take either of these factors and run gcd with p to find the prime over p.

If the prime is x+yq, then x/y is the square root of -3 mod p.