Find the GCD of the given complex numbers (Gaussian Integers)

In summary: The Euclidean Algorithm gives us a way to find a GCD of two elements of a ring, if such a GCD exists. This algorithm uses Euclidean division iteratively until the at some iteration, the resulting remainder is zero.
  • #1
chwala
Gold Member
2,647
350
Homework Statement
Kindly see attached.
Relevant Equations
Complex Numbers
1678792627830.png
Hello guys,
I am able to follow the working...but i needed some clarification. By rounding to the nearest integer...did they mean?

##z=1.2-1.4i## is rounded down to ##z=1-i##?

I can see from here they came up with simultaneous equation i.e

##(1-i) + (x+iy) = \dfrac{6}{5} - \dfrac{7i}{5}## to realise,

##x+iy=\dfrac{1}{5} - \dfrac{2i}{5}##

...the other steps seem clear...any reason why they make use of the so called second summand? One thing i have noted with pure maths- is that its quite easy- the only challenge i seem to use a lot of effort on is understanding the notations and the language used...why did they have to check the other norms i.e for ##a## and ##b## for instance the

##|a|=5^2+14^2##?

...are there cases where the norms may be small...

...I can see gaussian integers in some literature...the bit on the norms is now clearer...Will read on this some more...

cheers.
 
Last edited:
Physics news on Phys.org
  • #2
chwala said:
Homework Statement:: Kindly see attached.
Relevant Equations:: Complex Numbers

z=1.2−1.4i is rounded down to z=1−i?
Rather than "the nearest integer", I prefer floor function
[tex]\lfloor x \rfloor[/tex]
, maximum integer that does not exceed x.
[tex]\lfloor 1.2 \rfloor=1,\ 1.2=1+0.2[/tex]
[tex]\lfloor -1.4 \rfloor=-2,\ -1.4=-2+0.6[/tex]
[tex]z=(1-2i)+(0.2+0.6i)[/tex]
 
Last edited:
  • Like
Likes chwala
  • #3
anuttarasammyak said:
Rather than "the nearest integer", I prefer floor function
[tex]\lfloor x \rfloor[/tex]
, maximum integer that does not exceed x.
[tex]\lfloor 1.2 \rfloor=1,\ 1.2=1+0.2[/tex]
[tex]\lfloor -1.4 \rfloor=-2,\ -1.4=-2+0.6[/tex]
[tex]z=(1-2i)+(0.2+0.6i)[/tex]
Looks good! I'll explore more... relatively a new area to me...
 
  • #4
##\mathbb Z[ i]## is the ring of Gaussian Integers, right? It's been a while.
 
Last edited by a moderator:
  • Like
Likes chwala
  • #5
chwala said:
Hello guys,
I am able to follow the working...but i needed some clarification. By rounding to the nearest integer...did they mean?

##z=1.2-1.4i## is rounded down to ##z=1-i##?
That does not correctly state what "they" (the author(s) of the attachment) mean. You shouldn't change the meaning of ##z## like that. The first ##z## corresponds to the complex division of ##a## by ##b##, the result being a Gaussian Rational, since ##a## and ##b## are Gaussian Integers. The "rounded" version of ##z## is actually the quotient, ##q##, proposed in the attachment. The goal is to find Gaussian Integers, ##q, \text{ and, } r,## so that the expression
##\quad \quad \quad \quad a=q\,b+r ##
can be used in the Euclidean Algorithm to get a GDC of ##a## and ##b##. Dividing the above equation by ##b## gives us
##\quad \quad \quad \quad \displaystyle \dfrac a b =q+\dfrac r b ##
I can see from here they came up with simultaneous equation i.e

##(1-i) + (x+iy) = \dfrac{6}{5} - \dfrac{7i}{5}## to realise,

##x+iy=\dfrac{1}{5} - \dfrac{2i}{5}##
For the values of ##a## and ##b## used in the attachment, we have:

##\quad \quad \quad \quad \displaystyle \dfrac a b = \dfrac{5+14i}{-4+7i}= \dfrac{6}{5} - \dfrac{7i}{5} =
(1-i) + \dfrac{1}{5} - \dfrac{2}{5}i ##

So, ##q=1-i## and ##\displaystyle \dfrac r b =\dfrac{1}{5} - \dfrac{2}{5}i ##

Multiplying ##r/b## by ##b## gives you ##r##. Try it.
...the other steps seem clear...any reason why they make use of the so called second summand? One thing i have noted with pure maths- is that its quite easy- the only challenge i seem to use a lot of effort on is understanding the notations and the language used...
The word "summand" may be unusual, but it's not some special word used only in pure maths. You had an equation with the sum of two terms on the right hand side. Each is a summand.
...why did they have to check the other norms i.e for ##a## and ##b## for instance the

##|a|=5^2+14^2##?

...Are there cases where the norms may be small?...I can see gaussian integers in some literature...The bit on the norms is now clearer...Will read on this some more...

cheers.
As to your questions about the Norms: No, you do not generally need to calculate or check the norms for ##a## or ##b## ; not for ##r## or ##q## either. However, the author of your attachment is making a point, saying,
"This just checks that the remainder has small enough Norm (as the rounding method is designed to ensure −− have a think about how it does this). "​

Complex numbers do not have order. It does not make sense to say that ##z_1>z_2## or ##z_1<z_2##.

We can't compare ##r## and ##b## directly with "greater than" or ""less than", but we can compare their relative size by comparing Norms. We could just a well use the modulus, but the Norm works out better. The Norm of a Gaussian Integer is itself an Integer − a non-negative Integer.

Added in Edit:
The Euclidean Algorithm gives us a way to find a GCD of two elements of a ring, if such a GCD exists. This algorithm uses Euclidean division iteratively until the at some iteration, the resulting remainder is zero.
So, if the Norm of the remainder decreases for each iteration and since the Norm is a non-negative Integer, the process is guaranteed to terminate in a finite number of steps.
 
Last edited:
  • Informative
Likes chwala

1. What are Gaussian Integers?

Gaussian Integers are complex numbers with real and imaginary parts that are both integers. They can be expressed in the form a + bi, where a and b are integers and i is the imaginary unit.

2. How do you find the GCD of two Gaussian Integers?

To find the GCD (Greatest Common Divisor) of two Gaussian Integers, we can use the Euclidean algorithm. This involves finding the remainder when dividing the larger number by the smaller number, and then repeating the process until the remainder is 0. The last non-zero remainder is the GCD.

3. Can the GCD of two Gaussian Integers be a complex number?

No, the GCD of two Gaussian Integers will always be a Gaussian Integer itself. This is because the Euclidean algorithm only involves division and subtraction, which can only result in integers.

4. Are there any shortcuts to finding the GCD of Gaussian Integers?

Yes, there is a shortcut known as the Euclidean algorithm for Gaussian Integers. This involves using the same steps as the Euclidean algorithm for regular integers, but with some modifications to account for the imaginary parts of the numbers.

5. Can the GCD of Gaussian Integers be negative?

Yes, the GCD of Gaussian Integers can be negative. This is because the GCD is defined as the largest number that can divide both Gaussian Integers without leaving a remainder, regardless of its sign.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
10
Views
920
  • Precalculus Mathematics Homework Help
Replies
19
Views
1K
  • Precalculus Mathematics Homework Help
Replies
12
Views
949
  • Precalculus Mathematics Homework Help
2
Replies
39
Views
4K
  • Precalculus Mathematics Homework Help
Replies
7
Views
2K
  • Calculus and Beyond Homework Help
Replies
2
Views
929
  • Precalculus Mathematics Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
  • Precalculus Mathematics Homework Help
Replies
31
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
669
Back
Top