Understanding the Euclidean Algorithm for Finding GCDs in Q[sqrt 3]

[squelchy451]

Hi.

I need to find the GCD of two numbers in Q[sqrt 3]. Let's suppose these two numbers are 12 and 35. How would you go about finding the GCD of those in Q[sqrt 3]?

thanks~

 

[Hurkyl]

Is Z[sqrt 3] a unique factorization domain? (Or are the integers \mathbb{Z}[(1 + \sqrt{3}) / 2]?) I confess I haven't memorized my small number fields.

Anyways, what ways might you find the GCD over the integers? Would any of those work in this number field?

 

[squelchy451]

Q[sqrt 3] is all the numbers in the form (a + b sqrt3)/2 where a and b are rational integers, both even or both odd.

 

[squelchy451]

I COULD use the euclidean algorithm, but I wouldn't know where to start, as these numbers are rational primes, and I need to find solutions in Q[sqrt 3]

 

[Hurkyl]

Sure, 12 is a rational integer. But that doesn't matter, does it? What part of the Euclidean algorithm over Q(sqrt 3) prevents it from working with algebraic integers that happen to also be rational integers?

 

[squelchy451]

I know what you are trying to say but in terms of rational numbers, there are no factors in common between 24 and 49, but according to this problem, there might be a factor that is a quadratic integer in Q[sqrt3]. The question is which numbers do we know is a factor or not? Since 3 is not congruent to 1 sqrt3, the integers are in the form a + b sqrt3, where a and b are rational integers.

 

[Hurkyl]

There are some typos in your post...

If you are unsure about the Euclidean algorithm (or any other method for finding GCDs), then why not review the argument why it works? That way, you will either gain confidence that it works, or find a specific reason why it should not.