MHB Finding GCD in Gaussian Integers

[ArcanaNoir]

The problem asks to find a generator of the principal ideal <6+7i, 5+3i> in Z.

It is my understanding that such a generator must be a greatest common divisor of 6+7i and 5+3i. So, let's call this guy d, we should have d(a+bi)=6+7i and d(c+di)=5+3i.

I'm not really sure how to find d. If I divide 6+7i by a+bi I get \frac{(6a+7b)+(7a-6b)i}{a^2+b^2} and I don't see how this helps.

I'm new to Gaussian integers. Any hints on how to work with them would be appreciated.

 

[ArcanaNoir]

Okay I made "progress". Didn't solve it but I have more effort to offer.

I remembered the Euclidean algorithm can be used to find the gcd of two numbers.

it goes like this:
a=q_0b+r \\ b=q_1r_0+r_1 \\<br /> r_0 = q_2r_1+r_2
and so on until the last non-zero remainder, which will be the gcd.

So I did this:
6+7i=(5+3i)(1)+(1+4i) \\<br /> 5+3i=(1+4i)(1-i)+0
so I determined the gcd is 1+4i.
Then I wanted to check that this was actually a divisor of 6+7i, but I got a remainder >_<

So I will now be checking my calculations. Am I on the right track now?

Lol I fixed it! This has been a great help :) Sometimes just knowing you're listening gets the job done. (heart)

 

[I like Serena]

The problem asks to find a generator of the principal ideal <6+7i, 5+3i> in Z.

It is my understanding that such a generator must be a greatest common divisor of 6+7i and 5+3i. So, let's call this guy d, we should have d(a+bi)=6+7i and d(c+di)=5+3i.

I'm not really sure how to find d. If I divide 6+7i by a+bi I get \frac{(6a+7b)+(7a-6b)i}{a^2+b^2} and I don't see how this helps.

I'm new to Gaussian integers. Any hints on how to work with them would be appreciated.

The norm of a Gaussian integer $a+bi$ is defined as $N(a+bi)=a^2+b^2$.
If we can say $d\ |\ a+bi$, then it follows that $N(d)\ |\ N(a+bi)$.
\begin{array}{}
N(6+7i)&=&85&=&5\cdot 17 \\
N(5+3i)&=&34&=&2\cdot 17
\end{array}
Therefore $N(d)\ |\ 17$.

Furthermore, if we have $d = \gcd(u, v)$, then we also have $d = \gcd(u-v, v) = \gcd(u, v-u)$.
This is the basis of the euclidean algorithm, that can also be applied here.

Edit: Ah! I see you just did so. You'd be on the right track then.

 

[ArcanaNoir]

The norm of a Gaussian integer $a+bi$ is defined as $N(a+bi)=a^2+b^2$.
If we can say $d|a+bi$, then it follows that $N(d)\ |\ N(a+bi)$.
\begin{array}{}
N(6+7i)&=&85&=&5\cdot 17 \\
N(5+3i)&=&34&=&2\cdot 17
\end{array}
Therefore $N(d)\ |\ 17$.

Furthermore, if we have $d = \gcd(u, v)$, then we also have $d = \gcd(u-v, v) = \gcd(u, v-u)$.
This is the basis of the euclidean algorithm, that can also be applied here.

Edit: Ah! I see you just did so. You'd be on the right track then.

You're so inspirational ILS, you're at the level where you are feeding me insight telepathically!