# Euclidean Algorithm

• Aug 26th 2010, 08: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
• Aug 27th 2010, 11: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.
• Aug 27th 2010, 03: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?
• Sep 5th 2010, 08: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?
• Sep 5th 2010, 04: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?
• Sep 5th 2010, 07: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.