# Use the Euclidean algorithm to find the GCD of $1 + 28i$ and $4 + 7i$

I am trying to learn how to use the Euclidean algorithm to find the GCD of $$1 + 28i$$ and $$4 + 7i$$. The question I am trying to answer is:

Apply the Euclidean algorithm to $$\alpha = 1 + 28i$$ and $$\beta = 4 + 7i$$ in the integers of $$Q[\sqrt{-1}]$$. Find quadratic integers $$\mu$$ and $$\nu$$ for which $$\mu \alpha + \nu\beta = \text{gcd}(\alpha, \beta)$$.

What I have done so far is divide $$\alpha$$ by $$\beta$$ to get $$\frac{200}{65} + \frac{105}{65}i$$. I used $$3 + 2i$$ as my nearest Gaussian integer, and then found $$1 + 28i - (4 + 7i)(3 + 2i) = 3 - i$$.

I am a bit unsure how to proceed. Is my work so far correct? How would I go about finding the GCD, and then the quadratic integers µ and ν?

• What are the divisors of 5, the gcd of the norms? – healynr May 15 '20 at 3:25

First let's do an example of the usual Euclidean algorithm so that it becomes easier to see what's going on for the Gaussian integers: suppose we want the gcd of 36 and 15. We have \begin{align*} 36 &= 2* 15 + 6 \\ 15 &= 6*2 + 3 \\ 6 &= 2*3 \end{align*} So 3 is the gcd. Working backwards: \begin{align*} 3 &= 15 - 6*2 \\ & = 15 - (36 - 2*15)*2 \\ & = 15 - 2*36 + 4*15 \\ & = 5*15 - 2*36 \end{align*}
Ok, now we do the analogous thing for Gaussian integers (to get the coefficients I always divide the bigger one by the smaller one and take the remainder, i.e. $$(1+28i)/(4+7i)$$ is close to $$3+i$$): \begin{align*} 1+2 8i &= (4+7i)*(3+i) + (-4 + 3i) \\ 4+7i &= (-4+3i)*(-i) + (1+3i) \\ -4+3i &= (1+3i)*i + (-1+2i) \\ (1+3i) &= (-1+2i)*(1-i) \end{align*}
So our gcd is $$-1+2i$$. Now we have to do a bunch of back substitution. \begin{align*} -1+2i &= (-4+3i) - (1+3i)*i \\ &= (-4+3i) - ((4+7i) - (-4+3i)*(-i))*i \\ &= (-4+3i)*2 + (4+7i)*(-i) \\ &= ((1+28i)-(4+7i)*(3+i))*2 + (4+7i)*(-i) \\ &= (1+28i)*(2) + (4+7i)*(-6-3i) \end{align*}