Associated Topics || Dr. Math Home || Search Dr. Math

### Linear Congruences of Gaussian Integers

```Date: 04/11/2003 at 02:46:55
From: Alvin
Subject: Linear congruences of Gaussian integers

When does the linear congruence zx congruent to 1 (mod m), for z, x,
and m, all Gaussian integers, have a solution? Also, when do we say
that two Gaussian integers are relatively prime?

I know that for ordinary integers, the congruence given has a solution
when z and m are relatively prime, but I don't know if it works for
Gaussian integers, I hope you can help me.

Thanks!
```

```
Date: 04/13/2003 at 08:10:16
From: Doctor Jacques
Subject: Re: Linear congruences of Gaussian integers

Hi Alvin,

The Gaussian integers have the equivalent of Euclid's algorithm.
Therefore, everything that is based on that algorithm applies to the
Gaussian integers, including the solution of linear Diophantine
equations.

In particular, the congruence ax = 1 (mod m), where a, x, and m are
Gaussian integers, has a solution in x if and only if a and m are
relatively prime, (with an adequate definition of "relatively prime"
- see below).

There are a few differences, however.

First, Euclid's algorithm works a little differently for Gaussian
integers. (I'll give you an example below.)

Second, we can no longer restrict ourselves to positive integers
("positive" is meaningless for Gaussian integers).

For the normal integers, we usually define the gcd of two numbers as
a positive integer, but this is not really required. For example, we
may say that the gcd of 6 and 8 is either 2 or -2, because the sets
of integer multiples of 2 and -2 are the same.

The most general definition of the gcd of a and b is:

d = gcd(a,b) if d divides a and b and every number that divides a
and b divides d.

In the case of gcd(6,8), you can see that both 2 and -2 satisfy the
definition.

The reason behind this is that -1 has a multiplicative inverse in the
integers (we say it's a "unit") : (-1)(-1) = 1, and multiplying by -1
does not change the divisibility properties (the divisors and
multiples) of a number.

The same applies to Gaussian integers, but in this case we have four
units: 1, -1, i, -i (for example, i(-i)=1). In this case, the gcd of
two numbers is only defined up to a factor of -1, i, or -i.

With that in mind, we say that two Gaussian integers are relatively
prime if their gcd is 1, -1, i, or -i, which is the same as saying
that their gcd divides 1. In general, the congruence ax = b (mod m)
has a solution if gcd(a,m) divides b.

Let us now come to Euclid's algorithm with Gaussian integers.

In normal integers, when we divide a by b, we find q and r such that:

a = bq + r
0 <= r < |b|

In the Gaussian integers, the condition r >= 0 is meaningless. We
base the division algorithm on the concept of norm. The norm of a
Gaussian integer (or any complex number) (x + yi) is:

N(x + yi) = x^2 + y^2

i.e. the square of the complex absolute value. Note that the norm is
multiplicative:

N(ab) = N(a)N(b)

and it is always non-negative.

To divide a by b in Gaussian integers, we find q and r such that:

a = bq + r
N(r) < N(b)

and we find the quotient q by computing a/b and rounding the real and
imaginary parts to the nearest integers. Note that, in some cases,
there will be more than one possible quotient (for example, if a/b =
0.5), but that does not matter - the final gcd will be either the
same or multiplied by a unit (which, as we saw, is unimportant).

Let us work out an example in detail. We want to compute the gcd of
(-1 + 5i) and (7 - i). We start by comparing the norms:

N(-1 + 5i) = (-1)^2 + 5^2 = 26
N(7 - i) = 7^2 + 1^2 = 50

We start Euclid's algorithm by dividing the number with the larger
norm by the other one (in case of tie, either choice will do). In this
case, we divide (7 - i) by (-1 + 5i).

The first thing to do is to divide the numbers as simple complex
numbers:

(7-i)/(-1+5i) = (7-i)(-1-5i)/((-1+5i)(-1-5i)) = (-12-34i)/26

(Note how we multiplied both terms by the complex conjugate of the
denominator).

The real and imaginary parts of the quotient are -12/26 (=-0.46..)
and -34/26 (=-1.30..). We round these to 0 and -1, respectively. Our
quotient is thus (0-i), and we compute the remainder as:

r = a - bq = (7-i) - (-1+5i)(-i) = 2-2i

i.e. we have:

(7-i) = (-1+5i)(-i) + (2-2i)

the next step is to divide (-1+5i) by (2-2i). We proceed as before:

(-1+5i)/(2-2i) = (-12+8i)/8 = -1.5 + i, which we round to (-2 + i).

The new remainder is:

(-1+5i) - (2-2i)(-2+i) = 1 - i

The next division gives:

(2-2i)/(1-i) = 2 (exactly)

The complete calculation is given in the following table:

q      a
------------
7-i
-1+5i
-i      2-2i
-2+i    1-i
2  0

and, as in the normal algorithm, the gcd is the next to last
remainder, in this case (1-i). Note that we also have three other
"equivalent" gcd, obtained by multiplying (1-i) by -1, i, and -i.
These are (-1+i), (1+i) and (-1-i).

To solve the congruence ax = b (mod m), you can then proceed exactly
as with normal integers (the calculations will be more complicated,
but the method is the same).

If N(a) and N(b) are relatively prime (as normal integers), then a
and b are also relatively prime, but the converse is not true. For
example, N(2+i) = N(2-i) = 5, but gcd(2+i,2-i) = 1. More generally,
gcd(N(a),N(b)) divides N(gcd(a,b)).

Does this help?  Write back if you'd like to talk about this more, or
if you have any other questions.

- Doctor Jacques, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
College Definitions
College Imaginary/Complex Numbers
College Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search