Results 1 to 6 of 6

Math Help - GCD Question

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

    GCD Question

    Hello All,

    My book is going over finding the GCD[x,y] in the integers of some Q[Sqrt(d)].

    One example states: Find the GCD of 24 and 49 in the integers of Q[Sqrt(3)]. It states that GCD is already assumed as defined and there is no need to decompose 24 or 49 into primes in Q[Sqrt(3)]].

    Can anyone help me find this?

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

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Samson View Post
    Hello All,

    My book is going over finding the GCD[x,y] in the integers of some Q[Sqrt(d)].

    One example states: Find the GCD of 24 and 49 in the integers of Q[Sqrt(3)]. It states that GCD is already assumed as defined and there is no need to decompose 24 or 49 into primes in Q[Sqrt(3)]].

    Can anyone help me find this?

    Thank you, -Samson
    What critereon is used to determine whether a common divisor is "greatest"?

    Edit: These look like nice resources

    http://arxiv.org/abs/1002.4487
    http://en.wikipedia.org/wiki/Euclide...ratic_integers
    http://demonstrations.wolfram.com/Ex...raticIntegers/
    Last edited by undefined; September 5th 2010 at 08:32 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jun 2010
    From
    United States
    Posts
    200
    Quote Originally Posted by undefined View Post
    What critereon is used to determine whether a common divisor is "greatest"?
    I assume that it would stick with the traditional version of GCD, So GCD[6,12] = 6.

    Could you help with this discrete example?
    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
    I assume that it would stick with the traditional version of GCD, So GCD[6,12] = 6.

    Could you help with this discrete example?
    There could be common denominators not in \mathbb{Z}, then how do you know which one to pick?

    I think when you say "discrete" you mean "concrete".
    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 could be common denominators not in \mathbb{Z}, then how do you know which one to pick?

    I think when you say "discrete" you mean "concrete".
    Yes, I mean this specific examples using these specific numbers. As far as the GCD goes, the book did make the statement that "[the] GCD is already assumed as defined and there is no need to decompose 24 or 49 into primes in Q[Sqrt(3)]]".

    So can someone show me how to find the GCD of those two numbers within the respective field mentioned?
    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
    Yes, I mean this specific examples using these specific numbers. As far as the GCD goes, the book did make the statement that "[the] GCD is already assumed as defined and there is no need to decompose 24 or 49 into primes in Q[Sqrt(3)]]".

    So can someone show me how to find the GCD of those two numbers within the respective field mentioned?
    Assuming it's already defined isn't very helpful in regards to my question.

    I think what your book means by that is that we assume the ring of integers in question is a GCD domain and in particular a Euclidean domain (and even more in particular, a norm-Euclidean domain).

    And I think we use the definition that an integer g is the gcd of two integers x,y if and only if for for all integers d: d divides x and d divides y implies that d divides g.

    Using this definition I think the gcd will be unique up to multiplication by units.

    I've been looking at the two subheadings "Euclidean domains" and "Unique factorization of quadratic integers" here at Wikipedia. (And also the subheadings before that.) And it seems in general that the Euclidean algorithm produces the desired result whether or not at each step we choose a remainder as small as possible (here, smallness given by the norm), as long the sequence of remainders is strictly decreasing.

    At any rate, 49 = 24 * 2 + 1. And 2 = 1 * 2 + 0. So I think the gcd is just 1, same as in \mathbb{Z}.

    Hope you don't mind my constantly saying "I think" and "it seems". Truth is I have little experience in this, so while I believe I've come to correct conclusions, I'm not as sure as I would be with experience.
    Follow Math Help Forum on Facebook and Google+


/mathhelpforum @mathhelpforum