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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.