Gaussian Integers &
Division Algorithm Project
By: Clay Kitchings
MATH 6000
(Also EMAT 6690)
Motivation
for this write-up comes from my MATH 6000 project/assignment on the Gaussian
Integers. This will become a webpage
essay for EMAT 6690. This
assignment makes use of the following technologies: TI84 Plus Silver Edition
(for efficient multiplication of complex numbers), Geometers Sketchpad (for
plotting points and for other graphics). Note: This link will NOT be activated
until after 11:00am, Thursday, May 3rd. No one (teacher, student, or other individual or group)
other than Clay Kitchings will view this document in any shape or form until
after the 11:00am deadline.
A
Gaussian Integer is a complex number a + bi where a and b are both
integers.
Let this
set be represented by Z[i] = {a+bi |
a, b are in Z}.
Like Z
and F[x] (and a few other rings) Z[i] has a division algorithm. Our first goal
is to see how the division algorithm works:
The
Division Algorithm, also known as Proposition 3.1 states the following: Let z = a + bi and w = c + di (z, w,
elements of Z[i]), 
.
Then there are Gaussian integers q and r so that z = qw + r with |r|2
< |w|2 (Shifrin, 1996, p. 140).
For our
first example, let z = 4 + 7i and w = -1 + 4i.
For the
record, well compute some multiples of w. Well use the TI84 to expedite the
process. L2 = L1*w:
1) On the following grid, we shall
mark all of the points in <w>, the ideal generated by w. Note that the horizontal axis is the
real axis and the vertical axis is the imaginary axis (though it is only labeled
as a typical x-y plane).
2) Well connect some of the points
in <w> and tile the plane with squares. This process was initiated by
drawing the polygon with vertices 0, w, iw, and (1+i)w.
3) Next, well plot z in the complex
plane (as shown below).
4) The yellow-colored point z now
lies in the interior of one of the squares above. Since the vertex is in
<w> it is of the form qw for some q in Z[i]. The vertex of the square nearest to z is (1-i), so q = 1-i.
5) Now let r = z – qw. What is
r?
6) Claim: We have just applied the division
algorithm to z and w.
Discussion: We have applied the division algorithm because
weve expressed z as a product of w and a Gaussian integer plus some remainder
(also a Gaussian integer). All of the vertices with blue points are in
<w>. The w vertex itself is also highlighted yellow.
Note
(visual observation): we may observe a pattern along each line passing through
the points in <w>. For
example, after calculating various multiples of w (i.e., various forms of qw),
we find that a pattern exists within the real and imaginary parts of the
complex number q. For example, the points which are collinear with w and (1+i)w
all have 1 as the real part of q. Well call that line L1. The parallel line immediately below
L1 has 0 for all the real parts of each complex number q. Immediately below and
parallel to that line, we find a similar result for the real parts of q,
except for now it is -1. As we proceed downward in the plane, we find that for
each line the real part of the number q decreases by one.
There is
a similar pattern that occurs for those lines which are perpendicular to
L1. As one moves further to the
left in the plane, one finds the imaginary part of the number q increases by
one (or rather, the coefficient of i increases by one for the complex number
q). Moving to the right causes the coefficient of i to decrease by one with
each additional line to the right in the plane. This pattern is useful in more
quickly determining the vertices of the squares (all of which are in <w>).
Now
repeat the steps above with z = -1 + 4i and w = 1 + 2i. Why are we using these
numbers? They come from the above problems continuation of the division
algorithm.
From
above, we have the following:
r = z – qw However,
if we are to continue to divide, we would then repeat the process as follows:
z = w – qw for
some new q, w that are in Z[i].
This process is somewhat analogous to finding the gcd(14, 35) among the
integers by using the Euclidean Algorithm.
The above
graphic illustrates the complex number w along with the ideal generated by w
(or <w>). The pink-colored point z lies in the interior of one of the
squares, and it is closest to the vertex (1+i)w. This vertex is a part of
<w>, so it is of the form qw for some q in Z[i]. This means q=1+i.
Let r = z
– qw, and solve for r: r=
(-1+4i) – (1+i)(1+2i) r=
i = (0 + 1i)
Calculate
gcd(4+7i, -1+4i).
z = (q) (w) +
r
4+7i =
(-1+4i)(1-i) + (1+2i)
-1+4i =
(1+2i)(1+i) + i
1+2i =
i(-i+2) + 0
So,
gcd(4+7i, -1+4i) = i.
Now,
write the gcd as a linear combination of (4+7i) and (-1+4i). Let these two complex numbers be z and
w as they were earlier in the problem.
So now we need to write i as a linear combination of z and w.
i = w
– (1+2i)(1+i)
i = w
– [z – w(1-i)] [1+i] = w – [z(1+i) – w(1-i)(1+i)] = w
– z(1+i) + w(2) = 3w – z(1+i)
So i =
(3+0i)(-1+4i) + (4+7i)(-1-i)
Next, we
shall find the gcd (7-4i, 1+3i).
7-4i =
(1+3i)( q ) + r
Use a
diagram/grid:
Note: z may
not have one unique nearest vertex, so this number need not be unique.
Take q =
-3i.
7-4i =
(1+3i)( q ) + r
7-4i =
(1+3i)(-3i) + r r = -2-i.
So,
7-4i =
(1+3i)(-3i) + (-2-i)
Now we
consider dividing (1+3i) and (-2-i):
It appears
Z may actually be one of the vertices of a square in the ideal this time.
(Note: this z and w are different from the ones we started with.) The vertex
nearest z is (-1-i)w, so q=(-1-i). Lets now divide again:
7-4i =
(1+3i)(-3i) + (-2-i)
1+3i =
(-2-i)(-1-i) + r where
r is some new remainder
r = 0
Therefore,
the gcd(7-4i, 1+3i)
= -2-i. Now we shall write it as a linear combination of z and w:
-2-i = z
– (-3i)(1+3i) -2-i
= (7-4i) + (3i)(1+3i)
References
Shifrin,
Theodore. (1996). Abstract algebra: A geometric approach. Upper Saddle River, NJ. Prentice
Hall.