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 \\ 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)

 

[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!

 

[blue_raver22]

I would suggest starting by breaking down the problem into smaller, more manageable steps. First, we can use the Euclidean algorithm to find the greatest common divisor of the two Gaussian integers. This involves repeatedly dividing the larger number by the smaller number and using the remainder as the new divisor until we reach a remainder of 0. This final nonzero remainder will be the greatest common divisor.

Once we have the greatest common divisor, we can then check if it is also a generator of the principal ideal <6+7i, 5+3i>. This can be done by seeing if the greatest common divisor can be expressed as a linear combination of 6+7i and 5+3i, with coefficients in Z. If it can, then it is a generator of the principal ideal.

In terms of working with Gaussian integers, it may be helpful to remember that they are complex numbers of the form a+bi, where a and b are integers. This means that the usual rules of arithmetic still apply, but we must also consider the unique properties of Gaussian integers, such as the fact that they form a unique factorization domain.

Overall, solving this problem involves using both algebraic and number-theoretic techniques, and as a scientist, it is important to approach the problem systematically and carefully to ensure a correct solution.