Euclidean Algorithm Gaussian Integers

In summary: then the greatest common divisor of x and y is the product of the primes in parentheses: (abcdefghi).
  • #1
8
0
Hi,

Just wondering when using the Euclidean Algorithm to find gcd of 4+7i and 1+3i. Where does 2 and 2+i come from in the follwoing?

4+7i = 2*(1+3i)+(2+i)
1+3i=(1+i)*(2+i) +0?

I know you didvide them to get (5-i)/2 and then take closest Gaussian integer then not sure where to go.
 
Physics news on Phys.org
  • #2
If these are complex numbers you are talking about, I'm not sure that the GCD has the same meaning as it does for integers. Complex numbers can't be ordered as 'lesser' or 'greater' like integers and real numbers can.
 
  • #3
I think the size is relative to their Norm x^2 + y^2 if that makes sense.
 
  • #4
There are many different complex numbers which all have the same norm. You still can't say if one complex number is 'greater than' or 'less than' another complex number.
 
  • #5
The greatest common divisor is a well-defined notion in any unique factorization domain.

http://en.wikipedia.org/wiki/Greatest_common_divisor#The_gcd_in_commutative_rings

The greatest common divisor is unique up to multiplication by a unit; in the case of gaussian integers, this means one of ##\pm 1## or ##\pm i##.

A euclidean domain is a special case of a unique factorization domain, one in which the euclidean algorithm works, meaning essentially that we can divide any element ##a## by any nonzero element ##b## and get a quotient and a remainder, where the remainder is "smaller" than ##b##. Part of the definition of euclidean domain is a "norm" function which quantifies what we mean by smaller. It can be any function ##f## from the ring to the nonnegative integers, such that for every ##a## and every nonzero ##b##, there exist ##q,r## satisfying ##a = qb + r##, with either ##r = 0## or ##f(r) < f(b)##.

The gaussian integers are an example of a euclidean domain, with norm function ##f(x+iy) = x^2 + y^2##.

To address the OP's question, if ##a = 4 + 7i## and ##b = 1 + 3i## then for the first step of the euclidean algorithm, we seek ##q## and ##r## satisfying
$$4 + 7i = q(1+3i) + r$$
such that either ##r = 0## or the norm of ##r## is strictly smaller than ##1^2 + 3^2 = 10##. To find a candidate for ##q##, we can carry out the division as complex numbers (not constrained to be gaussian integers):
$$\frac{4+7i}{1+3i} = \frac{(4+7i)(1-3i)}{(1+3i)(1-3i)} = \frac{25 - 5i}{10} = \frac{5}{2} - \frac{1}{2}i$$
If we round the real part ##5/2## down to ##2## and the imaginary part ##-1/2## up to ##0##, we get a candidate ##q = 2 + 0i = 2##. Multiplying this candidate by ##1+3i##, we get ##2 + 6i##, and subtracting this from ##4+7i##, we end up with ##r = 2 + i##, which indeed satisfies the desired norm inequality ##2^2 + 1^2 < 1^2 + 3^2##.

Note that we could equally well have tried rounding the real part ##5/2## down to ##2## and the imaginary part ##-1/2## down to ##-1##, in which case we would have a candidate ##q = 2 - i##. Multiplying by ##1+3i## gives ##5 + 5i##, and subtracting this from ##4+7i##, we end up with ##r = -1 + 2i##, which also satisfies the norm inequality: ##1^2 + 2^2 < 1^2 + 3^2##. So this shows that the ##q## and ##r## at each step are not necessarily unique. This is OK, because at some point we must still end up with ##r=0## since at each step the norm of ##r## is a nonnegative integer which is strictly smaller than in the previous step.

Let's say we chose ##q=2## and ##r = 2+i## as in the OP. Then at the second step, we need to find ##q## and ##r## satisfying
$$1+3i = q(2+i) + r$$
where either ##r=0## or the norm of ##r## is strictly less than ##2^2 + 1^2 = 5##. To find a candidate ##q##, we can once again carry out the division in ##\mathbb{C}##:
$$\frac{1 + 3i}{2 + i} = 1 + i$$
No rounding is needed this time: we got an exact gaussian integer with no remainder. So this is the final step: ##q = 1 + i## and ##r = 0##, and the gcd is ##1+i## times any unit (##\pm 1## or ##\pm i##).
 
Last edited:
  • Like
Likes 1 person
  • #6
Note that if we had chosen ##q=2-i## and ##r = -1 + 2i## in the first step, then in the second step we would need to solve
$$1+3i = q(-1+2i) + r$$
where either ##r = 0## or the norm of ##r## is strictly less than ##1^2 + 2^2 = 5##. Carrying out the division in ##\mathbb{C}##:
$$\frac{1+3i}{-1+2i} = 1 - i$$
and again we got an exact answer with no remainder. At first glance the answer looks different: we obtained ##1 - i## versus ##1 + i## in the previous post. But note that ##(1 - i)(i) = 1 + i##, so the two answers agree up to multiplication by the unit ##i##.
 
Last edited:
  • #7
jbunnill is right, if x = abcdefghi, and y = efghiklmn, where all letters are non associate primes, then the gcd(x,y) is efghi.the confusing part is the language "greatest", whereas the correct terminology is "universal". I.e. a gcd of x aND Y IS A NUMBER z such that z is a common divisor of x and y, and such that z divides all common divisors of x and y.
 

1. What is the Euclidean Algorithm Gaussian Integers?

The Euclidean Algorithm Gaussian Integers is a mathematical method used to find the greatest common divisor (GCD) of two Gaussian integers. Gaussian integers are complex numbers of the form a + bi, where a and b are integers and i is the imaginary unit.

2. How does the Euclidean Algorithm Gaussian Integers work?

The algorithm works by repeatedly dividing the larger number by the smaller number and finding the remainder. This process is continued until the remainder is equal to 0. The last non-zero remainder is the GCD of the two numbers.

3. Why is the Euclidean Algorithm Gaussian Integers important?

Finding the GCD is an essential step in many mathematical calculations, such as simplifying fractions or solving equations. The Euclidean Algorithm Gaussian Integers is particularly useful for finding the GCD of complex numbers.

4. What are some applications of the Euclidean Algorithm Gaussian Integers?

The Euclidean Algorithm Gaussian Integers has applications in number theory, cryptography, and signal processing. It is also used in various algorithms for solving problems in computer science and engineering.

5. Are there any limitations to the Euclidean Algorithm Gaussian Integers?

Yes, the Euclidean Algorithm Gaussian Integers can only find the GCD of two numbers. It cannot be used to find the GCD of more than two numbers. It also does not work for finding the GCD of irrational or transcendental numbers.

Suggested for: Euclidean Algorithm Gaussian Integers

Replies
12
Views
876
Replies
8
Views
886
Replies
25
Views
1K
Replies
4
Views
793
Replies
16
Views
2K
Replies
33
Views
3K
Replies
14
Views
1K
Replies
26
Views
4K
Back
Top