Thread: 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

Originally Posted by Samson

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/

Originally Posted by undefined

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?

Originally Posted by Samson

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 , then how do you know which one to pick?

I think when you say "discrete" you mean "concrete".

Originally Posted by undefined

There could be common denominators not in , 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?

Originally Posted by Samson

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 .

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.