Welcome to our community

Be a part of something great, join today!

Finding GCD in Gaussian Integers

ArcanaNoir

New member
Nov 17, 2013
4
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 [tex] \frac{(6a+7b)+(7a-6b)i}{a^2+b^2} [/tex] 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
Nov 17, 2013
4
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:
[tex] a=q_0b+r \\ b=q_1r_0+r_1 \\
r_0 = q_2r_1+r_2 [/tex]
and so on until the last non-zero remainder, which will be the gcd.

So I did this:
[tex] 6+7i=(5+3i)(1)+(1+4i) \\
5+3i=(1+4i)(1-i)+0 [/tex]
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
Mar 5, 2012
8,887
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 [tex] \frac{(6a+7b)+(7a-6b)i}{a^2+b^2} [/tex] 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. :eek:
 

ArcanaNoir

New member
Nov 17, 2013
4
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. :eek:
You're so inspirational ILS, you're at the level where you are feeding me insight telepathically!