Results 1 to 6 of 6

Math Help - GCD between a complex and integer

  1. #1
    Member
    Joined
    Jun 2008
    Posts
    148

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member roninpro's Avatar
    Joined
    Nov 2009
    Posts
    485
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    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.
    Last edited by Opalg; March 27th 2011 at 12:51 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Jun 2008
    Posts
    148
    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.

    Upon thinking about the question after reading your post I realize the following:

    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?


    I'll think about this myself, and post if I get any answers.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member roninpro's Avatar
    Joined
    Nov 2009
    Posts
    485
    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).
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Jun 2008
    Posts
    148
    Quote Originally Posted by roninpro View Post
    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).
    Ah right.

    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 13
    Last Post: August 3rd 2010, 04:16 AM
  2. Integer Raised To Complex Number Power
    Posted in the Pre-Calculus Forum
    Replies: 13
    Last Post: April 23rd 2010, 08:55 PM
  3. Integer roots of integer polynomials
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 3rd 2009, 01:39 PM
  4. Raise integer to positive integer power
    Posted in the Algebra Forum
    Replies: 2
    Last Post: May 21st 2009, 01:20 PM
  5. [SOLVED] even integer and odd integer
    Posted in the Algebra Forum
    Replies: 2
    Last Post: October 1st 2008, 09:35 PM

Search Tags


/mathhelpforum @mathhelpforum