# Finding GCD in Gaussian Integers

#### ArcanaNoir

##### New member
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, lets 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

##### New member
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 \\ 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) \\ 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)

Last edited:

#### Klaas van Aarsen

##### MHB Seeker
Staff member
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, lets 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

##### New member
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!