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/