Euclidean Algorithm

Printable View

August 26th 2010, 07:25 AM
Samson

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
August 27th 2010, 10:43 AM
Opalg

Quote:

Originally Posted by Samson

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(1–3i) = 10, we must start by dividing 1–3i 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, 1–i is the remainder).

For the next step of the algorithm, we must divide 2 by 1–i. But this time the quotient is a Gaussian integer, because 2 = (1–i)(1+i). So the remainder is 0, and the gcd of 2 and 1–3i is the last nonzero remainder, namely 1–i.
August 27th 2010, 02:20 PM
Samson

Quote:

Originally Posted by Opalg

Since N(2) = 4 and N(1–3i) = 10, we must start by dividing 1–3i 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, 1–i is the remainder).

For the next step of the algorithm, we must divide 2 by 1–i. But this time the quotient is a Gaussian integer, because 2 = (1–i)(1+i). So the remainder is 0, and the gcd of 2 and 1–3i is the last nonzero remainder, namely 1–i.

Thank you so much! Are you able to help with part 2 of this?
September 5th 2010, 07:27 AM
undefined

Quote:

Originally Posted by Samson

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?
September 5th 2010, 03:16 PM
Samson

Quote:

Originally Posted by undefined

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?
September 5th 2010, 06:45 PM
undefined

Quote:

Originally Posted by Samson

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.