# Calculating the gcd of complex numbers

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...

• Presumably this is in the Gaussian integers. See e.g. this post – 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$.

• And if q wasn't in Z[i], We had to repeat until it was right? – ChikChak Jun 23 '16 at 8:18
• 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. – gammatester Jun 23 '16 at 8:26
• 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].. – ChikChak Jun 23 '16 at 8:31
• 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 – gammatester Jun 23 '16 at 8:43
• I understand.Thank you! – 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.

$$\frac{3+i}{1-i}=\frac{(3+i)(1+i)}{2}=\frac{2+4i}{2}=1+2i$$

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$.

Edit

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

$$\frac{3+13i}{4+3i}=\frac{(3+13i)(4-3i)}{25}=\frac{51}{25}+\frac{43}{25}i$$

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.