Numbers, Gaussian Integers

Gaussian Integers

Adjoin i to the integers, where i squared is -1. This forms the complex integers, or gaussian integers, named after the mathematician Carl Gauss (biography), who dabbled in just about everything. You can picture the gaussian integers as lattice points in the complex plane. If you connect the dots, you'll have an infinite checkerboard made up of unit squares.

The fact that the complex integers are commutative and associative is a direct result of their definition. We declare that 3×i is the same as i×3, and we multiply (q+ri)×(s+ti) by using the distributive property twice, and the resulting ring has all the desirable properties. You should probably prove all this algebraically, but I'll leave it to you. I just didn't want you to forget this important step.

Let the norm of the point q+ri be q² + r². You may recognize this as the square of the distance to the origin in the complex plane. You may also recall that complex numbers are multiplied by adding angles and multiplying radial distances. In other words, the norm of x×y is the norm of x times the norm of y. Let's pretend you haven't studied complex numbers before, and prove this algebraically. Expand (q+ri)×(s+ti) to get (qs-rt) + (qt+rs)i. Square these two components and add them together, giving q²s² + r²t² + q²t² + r²s². This simplifies to (q²+r²) × (s²+t²), which is the product of the two norms.

The Gaussian integers form a grid in the complex plane

side note. Other branches of mathematics use the word "norm" to indicate the distance to the origin, not the square of the distance. It all depends on context. In this case we prefer distance squared, because that is always an integer. In calculus, we set the norm to the distance, because that is compatible with the definitions of limits and continuity in n dimensional space. It really is confusing, and there's not much we can do about it. Oh well, back to the gaussian integers.

Except for the origin, the norm is always a positive integer. The units are ±1 and ±i, having norm 1. Every other number has a norm > 1, and as we multiply them together, the norms get even bigger.

Interestingly, 17 is no longer prime, as it is the product of 4+i × 4-i. Yet 4+i is prime. It has a norm of 17, and if it were the product of x and y, the norm of x times the norm of y would equal 17. Yet 17 is still prime in the positive integers, so we can't have |x|×|y| = 17, unless x or y is trivial, with norm 1. Thus 4+i and 4-i are both prime in the gaussian integers.

Can we still run the gcd algorithm? Let's look for a common divisor of 10 and 17+24i. If g divides both numbers, it divides 17+24i - 10×(2+2i). But how did I select 2+2i? The number 10 acts as a base for a lattice in the complex plane. Ten times the integers produces multiples of ten along the x axis. Ten times the integers times i produces multiples of ten up the y axis. Ten times the gaussian integers produces a grid in the complex plane. Connect the dots to produce an infinite checkerboard, where each square is ten units on a side. Find the square that contains 17+24i. Its coordinates run from 10 to 20 along the x axis, and from 20 to 30 along the y axis. Which corner is closes to 17+24i? The answer is 20+20i, being just 5 units away by the pythagorean theorem. Subtract this corner, and g divides -3+4i. This is a smaller number, i.e. closer to the origin, than 10, so we've made progress. Actually we were bound to make progress, because the distance from any point in a square to its nearest corner is always less than the side of the square.

Continue the gcd algorithm by using -3+4i as the base for a new checkerboard in the complex plane. This checkerboard is tilted with respect to the axes. Multiply the base vector -3+4i by 0, 1, i, and 1+i to build the base cell. This square, and the entire checkerboard, is tilted, but that doesn't matter. The squares are smaller, just 5 units on a side, and that's what counts. The point 10 on the x axis lies inside a square, and the corner closest to 10 is 11+2i. Subtract these two points, giving a difference of 1+2i. This is even closer to the origin. If this vector acts as the base for a smaller, tilted checkerboard, -3+4i lands smack on one of the grid points. In other words, 1+2i divides evenly into -3+4i, and we've found our gcd. Both 10 and 17+24i are divisible by 1+2i, and any other factor that divides both numbers divides into 1+2i.

Now we get unique factorization, almost for free. A reliable gcd algorithm means p divides st iff it divides s or t, and that means there is no smallest n with multiple factorizations. By smallest, we mean smallest norm, i.e. closest to the origin. Other than that, the proof is the same. Every gaussian integer splits uniquely into complex primes.

There are infinitely many gaussian primes, via the same argument as before. We can also find arbitrarily large areas of composite points in the plane by multiplying large blocks of numbers together, similar to n factorial in the integers.

Given a set of gaussian integers s₁ through s_n, one can solve the equation x₁s₁ + x₂s₂ + … + x_ns_n = z. As before, the solutions form an n-1 dimensional lattice, shifted away from the origin, but this time the numbers are all complex. If we want to picture the lattice in real space, with real variables, the dimension doubles to 2n-2.

The multiple of 10 closest to 17+24i is 20+20i

The multiple of -3+4i closest to 10 is 11+2i