# Finding GCD in Gaussian Integers

• MHB
• ArcanaNoir
In summary, 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.
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.

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:
ArcanaNoir said:
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.

I like Serena said:
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!

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.

## What are Gaussian Integers?

Gaussian Integers are complex numbers of the form a + bi, where a and b are both integers and i is the imaginary unit.

## What is the GCD of Gaussian Integers?

The GCD (Greatest Common Divisor) of Gaussian Integers is the largest integer that divides both Gaussian Integers without leaving a remainder.

## How do you find the GCD of Gaussian Integers?

To find the GCD of Gaussian Integers, you can use the Euclidean algorithm which involves dividing the larger number by the smaller number and using the remainder as the new divisor until the remainder is equal to 0. The last non-zero remainder is the GCD.

## Can the GCD of Gaussian Integers be expressed as a Gaussian Integer?

Yes, the GCD of Gaussian Integers can be expressed as a Gaussian Integer. This is because the GCD is the largest integer that divides both Gaussian Integers, so it must also be a Gaussian Integer.

## Why is finding the GCD of Gaussian Integers important?

Finding the GCD of Gaussian Integers is important in various mathematical applications, such as cryptography and signal processing. It is also a fundamental concept in number theory and can help simplify complex calculations involving Gaussian Integers.

• Linear and Abstract Algebra
Replies
6
Views
6K
• Precalculus Mathematics Homework Help
Replies
4
Views
1K
• Precalculus Mathematics Homework Help
Replies
39
Views
4K
• Calculus and Beyond Homework Help
Replies
1
Views
1K
• Calculus and Beyond Homework Help
Replies
6
Views
2K
• Linear and Abstract Algebra
Replies
4
Views
2K
• Engineering and Comp Sci Homework Help
Replies
2
Views
1K
• Linear and Abstract Algebra
Replies
6
Views
5K
• Engineering and Comp Sci Homework Help
Replies
27
Views
4K
• Linear and Abstract Algebra
Replies
2
Views
2K