I need help in calculating the gcd of complex numbers

For Example: $\gcd(3+i,1-i)$.

The problem is,I don't even know what's the algorithm for complex numbers...

  • 3
    $\begingroup$ Presumably this is in the Gaussian integers. See e.g. this post $\endgroup$ – Robert Israel Jun 23 '16 at 7:44

I assume that you want to compute with Gaussian integers, i.e. in $\mathbb{Z}[i]$.

Generally you compute the GCD similiar to the GCD in $\mathbb{Z}$, here is a short decsription additionally to the link given by @Robert Israel.

If you compute the first quotient $q\,$ for your example you get $q = \frac{3+i}{1-1}=1+2i$. This is already in $\mathbb{Z}[i]$ and therefore your specific GCD is $1-i,$ because $3+i = (1-i)(1+2i)$ is a multiple of $1-i$.

Note: Sometimes you will find the normalized answer $1+i\,$ for the GCD, this the Gaussian integer in the first quadrant associated with $1-i$.

  • $\begingroup$ And if q wasn't in Z[i], We had to repeat until it was right? $\endgroup$ – ChikChak Jun 23 '16 at 8:18
  • $\begingroup$ The Wiki reference says that The quotients $q_k$ are generally found by rounding the real and complex parts of the exact ratio to the nearest integers. $\endgroup$ – gammatester Jun 23 '16 at 8:26
  • $\begingroup$ Then how can I know when to stop?If I'll round it each time,I'll always get a q that is in Z[i].. $\endgroup$ – ChikChak Jun 23 '16 at 8:31
  • $\begingroup$ The norm of the remainders strictly decrease. You stop if you reach zero. Have a look at the link given in the mentioned answer: mathforum.org/library/drmath/view/67068.html $\endgroup$ – gammatester Jun 23 '16 at 8:43
  • $\begingroup$ I understand.Thank you! $\endgroup$ – ChikChak Jun 23 '16 at 8:51

Just to be a little clearer on the algorithm.

$3+i$ has a larger norm than $1-i$, $\sqrt{\mathstrut10}=|3+i|>|1-i|=\sqrt{2}$. So we will proceed by dividing the larger norm number by the smaller one.

Now I will from now on call $N(a+ib)=a^2+b^2$ the norm of a complex number, cf norm of a gaussian integer.

If both $a,b\neq0$, then $a+ib$ is a gaussian prime iff $N(a+ib)$ is an ordinary prime, again cf gaussian prime.

In the case of $1-i$, $N(1-i)=2$ which is a gaussian prime so we will be dividing by a prime number.

The same thing will happen therefore as with ordinary primes, either they will be co-prime or $1-i$ will be the gcd.


Now $1+2i\in \Bbb{Z}[i]$, so there is no remainder, it divided in exactly. Also $N(1+2i)=5$ which is prime so we have factored $$3+i=(1-i)(1+2i) \text{ into primes}$$

This isn't the only factorisation but the other differ by units, multiples of $1,-1,i,-i$.

Thus the $\gcd(3+i,1-i)=1-i$.


One more example which is a little less trivial is $\gcd(3+13i,4+3i)$.

Again divide the one with larger Norm by the one with smaller Norm, we can use $N(3+13i)=178>25=N(4+3i)$. So


Now since $2<\frac{51}{25}<2.5$ and $1.5<\frac{43}{25}<2$ take $\gamma_1=2(1+i)$

So $3+13i=(4+3i)\gamma_1+\rho_1$, where $\rho_1=1-i$.

Notice that $N(1-i)=2<25=N(4+3i)$, we're on the right track.

In the next step, like the ordinary euclidean algorithm write

$4+3i=(1-i)\gamma_2+\rho_2$ and $\frac{4+3i}{1-i}=\frac{1+7i}{2}$

so we'll take $\gamma_2=3i$, by rounding, and thus $\rho_2=1$. Now we could do the next step but since $\rho_2$ is a unit, we'll just get zero in the next step anyway for the remainder.

Thus the $\gcd(3+13i,4+3i)=1$, which is a bit anticlimactic but still.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.