Results 1 to 6 of 6

Math Help - Euclidean Algorithm

  1. #1
    Member
    Joined
    Jun 2010
    From
    United States
    Posts
    200

    Euclidean Algorithm

    Hello All,

    I have two questions:

    1. Can someone show me how to apply the Euclidean algorithm to 2 and 1-3i in the integers of Q[Sqrt(-1)] ?

    2. Assuming that Q[Sqrt(d)] is a Euclidean Field, and x,y are two quadratic integers in Q[Sqrt(d)] so that there exists a,b in Q[Sqrt(d)] so that x=a*y+g and Abs[N[g]] < Abs[N[y]]. How can we show that a,b are not necessarily unique?

    Thank you! - Samson
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by Samson View Post
    Can someone show me how to apply the Euclidean algorithm to 2 and 1-3i in the integers of Q[Sqrt(-1)] ? (I call these "Gaussian integers".)
    Since N(2) = 4 and N(13i) = 10, we must start by dividing 13i by 2, getting \tfrac12 - \tfrac32i. We now want the closest Gaussian integer to that quotient. There are four possible choices here, and it doesn't matter which one we take: the real part could be 0 or 1, and the imaginary part could be i or 2i. Let's take i as the Gaussian integer closest to the quotient. Then the first step in the Euclidean algorithm will look like this:

    1-3i = 2(-i) + (1-i) ... (i is the Gaussian quotient, 1i is the remainder).

    For the next step of the algorithm, we must divide 2 by 1i. But this time the quotient is a Gaussian integer, because 2 = (1i)(1+i). So the remainder is 0, and the gcd of 2 and 13i is the last nonzero remainder, namely 1i.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jun 2010
    From
    United States
    Posts
    200
    Quote Originally Posted by Opalg View Post
    Since N(2) = 4 and N(13i) = 10, we must start by dividing 13i by 2, getting \tfrac12 - \tfrac32i. We now want the closest Gaussian integer to that quotient. There are four possible choices here, and it doesn't matter which one we take: the real part could be 0 or 1, and the imaginary part could be i or 2i. Let's take i as the Gaussian integer closest to the quotient. Then the first step in the Euclidean algorithm will look like this:

    1-3i = 2(-i) + (1-i) ... (i is the Gaussian quotient, 1i is the remainder).

    For the next step of the algorithm, we must divide 2 by 1i. But this time the quotient is a Gaussian integer, because 2 = (1i)(1+i). So the remainder is 0, and the gcd of 2 and 13i is the last nonzero remainder, namely 1i.
    Thank you so much! Are you able to help with part 2 of this?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Samson View Post
    2. Assuming that Q[Sqrt(d)] is a Euclidean Field, and x,y are two quadratic integers in Q[Sqrt(d)] so that there exists a,b in Q[Sqrt(d)] so that x=a*y+g and Abs[N[g]] < Abs[N[y]]. How can we show that a,b are not necessarily unique?
    There is something wrong with the question. Maybe g is supposed to be b?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Jun 2010
    From
    United States
    Posts
    200
    Quote Originally Posted by undefined View Post
    There is something wrong with the question. Maybe g is supposed to be b?
    Okay, I"ll try to write it better.

    Assume Q[Sqrt(d)] is a Euclidean Field and \alpha, \beta are two quadratic integers in Q[Sqrt(d)], so that there exists integers \gamma and \delta in Q[Sqrt(d)] so that \alpha = \gamma \beta + \delta, and |N(\delta)|<|N(\beta)|. How can we prove by counterexample that \gamma and \delta are not necessarily unique?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Samson View Post
    Okay, I"ll try to write it better.

    Assume Q[Sqrt(d)] is a Euclidean Field and \alpha, \beta are two quadratic integers in Q[Sqrt(d)], so that there exists integers \gamma and \delta in Q[Sqrt(d)] so that \alpha = \gamma \beta + \delta, and |N(\delta)|<|N(\beta)|. How can we prove by counterexample that \gamma and \delta are not necessarily unique?
    All right, after working in your other thread on GCD of quadratic integers, this one is now obvious (and thanks for fixing the question). It is true even for \mathbb{Z}, which applies here since \mathbb{Z} is a subset of our ring.

    Consider integers 12 and 50. Now, 50 = 12*4 + 2 which is what we would typically use when doing the Euclidean algorithm. But it's also true that 50 = 12*3 + 14. So, that's all there is to it.
    Last edited by undefined; September 5th 2010 at 07:01 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euclidean Algorithm
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: September 30th 2010, 10:46 AM
  2. Euclidean Algorithm
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: September 14th 2010, 06:53 AM
  3. GCD and the Euclidean Algorithm
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: January 3rd 2010, 03:20 AM
  4. Euclidean algorithm
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: August 8th 2009, 08:28 AM
  5. Euclidean Algorithm
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: May 13th 2007, 07:20 AM

/mathhelpforum @mathhelpforum