Division Algorithm

One of the most important and underappreciated theorems is the Division Algorithm. You can usually find it in any book on number theory as Theorem 1. The proof for the Division Algorithm for Integers can be found here.

It states that for any given integer and nonzero divisor, there exists two unique integers: a quotient and a remainder where the remainder is smaller than the divisor.

Perhaps this theorem gets underappreciated because it is so obvious. It does not seem on the surface that there is anything surprising about this statement. Likewise, the proof, when it is first seen, may appear to the amateur like an exercise in the obvious.

The standard division algorithm for rational integers (positive and negative whole numbers) is based on the Well Ordering Principle.

And yet, there are subtleties regarding this theorem that have important implications for the theory of numbers. Consider the situation where we add imaginary numbers (numbers in which -1 has a square root known as i, that is, i² = -1.

When a mathematician looks at a problem like x² + y², it would be really convenient if there was an easy way to factor it. If we extend integers to include Z[i], then we can. In this case, we have the following factor (note: Z[i] is used to define an extended set set of integers. These are integers that have the form a + bi where a,b are rational integers):

(x - iy)(x + iy) = x² + y².

And, then the question arises, are integers of the type Z[i] characerized by a Division Algorithm? If they are, we need a new proof because the Well-Ordering Principle only applies to rational integers.

The path to a Division Algorithm requires the introduction of a special function known as a norm. It applies to any Z[α] value where α² is a rational integer (such as i). It is based on the very simple identity:

(a - b)(a + b) = a² - b²

Since we know that α² is rational integer, we know that there exists a value c such that c = α².

So, let us assume that we have an integer of the form a + bα. If we multiply it with its conjugate (an equivalent value where we change the sign), then we get:

(a + bα)(a - bα) = a² - cb².

If we had a value of a - bα, then its conjugate would be a + bα. In either case, we have found a function that maps any Z[α] integer to a rational integer.

With this function in place, we can prove for that given any Gaussian Integer and a nonzero divisor, there exists two unique values: a quotient and a remainder where the absolute norm of the remainder is smaller than the absolute norm of the divisor. Here is the proof.

We might ask if we will always find a division algorithm for all possible values of α.

Let us consider this question with respect to quadratic integers. These are integers of the form Z[α] where α is a irrational solution to an equation of the form x² + bx + c = 0 where x = α and b,c are rational integers (an irrational number is any number that is not equal to a rational fraction. For example -3/4 is rational since it is a ratio of -3 to 4. i on the other hand is not rational).

In this situation, it turns out there are only 21 different nonsquare values where Z[α] has a division algorithm (by nonsquare, I am excluding values such as Z[√-4] because 4 is a square of 2 and √-4 = 2i.

The 21 values are based on: -11, -7, -3, -2, -1, 2, 3, 5, 6, 7, 11, 13, 17, 19, 21, 29, 33, 37,41, 57, and 73.

Now, here's one more of the subtleties. It turns out that the form of this integer depends on the remainder when the number is divided by 4. If the remainder is any value but 1, then the form is simple: Z[√-2], Z[i], Z[√2],Z[√3], Z[√6],Z[√7],Z[√11], Z[√19].

If the remainder with 4 is 1, then the value takes a stranger form: Z[(-1 + √-11)/2], Z[(-1 + √-7)/2], Z[(-1 + √-3)/2], Z[(-1 + √5)/2], Z[(-1 + √13)/2], Z[(-1 + √17)/2],
Z[(-1 + √21)/2], Z[(-1 + √29)/2], Z[(-1 + √33)/2]. The details for why these values have this form can be found here.

The proof that many of these values are characterized by a Division Algorithm can be found here.