0
$\begingroup$

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 ν?

$\endgroup$
1
  • $\begingroup$ What are the divisors of 5, the gcd of the norms? $\endgroup$ – healynr May 15 '20 at 3:25
2
$\begingroup$

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*}$$

$\endgroup$
1
  • $\begingroup$ I highly recommend that you use this forward version of the Extended Euclidean algorithm, which is simpler and far less error-prone than the common back-substitution version. For an example see here. $\endgroup$ – Bill Dubuque May 15 '20 at 4:03

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.