# Thread: GCD between a complex and integer

1. ## GCD between a complex and integer

Suppose I wanted to find the GCD between a complex integer z and an integer. How would I go about doing this?

For instance, suppose $z = 6 + 4i$ and $I = 39$.

We know that 13 divides 39 and $13 = (3 + 2i) \cdot (3 - 2i)$.

Similarily $6 + 4i = 2 \cdot (3 + 2i)$

thus $gcd(z,I) = 3 + 2i$.

How the heck would I figure this out though without having to first factor z and I separately into they're irreducible/prime factors?

2. How about using the Euclidean Algorithm? To carry out the divisions, you can look at $(3+2i)/39$. The (non-unique) remainder can be found by choosing one of the four nearby integral complex numbers.

3. To expand on what roninpro has said, you can apply the euclidean algorithm, except that it is a bit more complicated than in the case of real integers.

The basic step in the algorithm is to divide a larger number $a$ by a smaller number $b$, getting a quotient $q$ and a remainder $r$. In the case of real integers, $q$ is the integer part of the fraction $a/b$, and the remainder $r$ has the crucial property that it is smaller than $b$.

In the case of Gaussian (complex) integers, some of those terms need redefining. First, you need a definition of the size of a Gaussian integer, so that you can make sense of the words "larger" and "smaller" in the above description of the euclidean algorithm. For a Gaussian integer $z = x+iy$, its size, or norm, is defined to be $x^2+y^2$.

Given Gaussian integers $z$ and $w$, with $z$ larger than $w$ in that sense, you can divide $z$ by $w$ to get a (fractional) complex number. As roninpro indicates, there could be up to four choices for the nearest Gaussian integer to this fractional number. Take any one of these to be the quotient.

To illustrate this process, take your numbers 39 and 6+4i. The norm of 39 is $39^2$, which is a lot bigger than $6^2+4^2$. So 39 is the larger number, and we start by dividing it by 6+4i (using the the usual technique of rationalising the denominator):

$\dfrac{39}{6+4i} = \dfrac{39(6-4i)}{52} = \frac92 - 3i.$

For the quotient, we take a Gaussian integer nearest to $\frac92 - 3i$. This could equally well be 4-3i or 5-3i. It doesn't matter which one you choose. Let's take 5-3i as the quotient. Then $39 = (5-3i)(6+4i) + (-3-2i)$. So the remainder is –3–2i (notice that this has norm less than the norm of 6+4i).

The next stage of the euclidean algorithm is to take the previous denominator (6+4i) and divide it by this remainder –3–2i. This time, the quotient is –2 and the remainder is 0. So the algorithm is complete, and it gives the gcd as the last nonzero remainder, namely –3–2i.

As a final detail, the gcd is not unique, because you can multiply it by any unit. A unit is an element of norm 1 (in the case of the Gaussian integers, the units are $\pm1$ and $\pm i$). Just as a matter of style, most people would prefer to give the gcd in this example as 3+2i rather than –3–2i. Less obviously, you could multiply it by i, and give the gcd as 2–3i, which would be an equally correct answer.

4. Thanks Opalg. Sorry for the late response. I read your post the other day, but didn't want to respond just yet because I needed time to wrap my head around what you were saying.

1) Its not intuitively obvious what the "Largest Common Denominator" should be defined to be. Its clearly implicitly implied in your post that greatest, smallest is defined by the norm of a complex number.

2) By your definition of distance, would the sequence $r_1, r_2, ...... r_n$ in this Euclidean Algorithm, be a sequence of strictly decreasing terms (which would eventually go to zero)?

3) Suppose $r_n = 0$. How do we know that $r_{n-1}$ is equal to the gcd as apose to some Larger Gaussian integer for which the gcd divides?

5. In general, the GCD between two elements $a,b$ is an element $d$ such that $d|a$ and $d|b$ and if $d_1|a$ and $d_1|b$, then $d_1|d$ (i.e. any other common divisor must divide $d$).
In general, the GCD between two elements $a,b$ is an element $d$ such that $d|a$ and $d|b$ and if $d_1|a$ and $d_1|b$, then $d_1|d$ (i.e. any other common divisor must divide $d$).
Given that $c = a \cdot b$ implies $N(c) = N(a) \cdot N(b)$ I can see why using the norm is useful in this problem.