I'm trying to find the GCD of $(85,1+13i)$ and $(47-13i,53+56i)$. I've tried, but to no avail. I keep setting it up and trying to do it with the same mindset as if i'm doing polynomial division, is this incorrect? I believe I need to do "synthetic division", is that correct? Yeah, if somebody could help me out that'd be great

  • 1
    $\begingroup$ To use the Euclidean Algorithm to find $\gcd(a,b)$ in $\mathbb Z[i]$, assuming $|a| > |b|$, what you need to do is to divide $a$ by $b$, get the quotient $a = qb$, where $q \in \mathbb Q[i]$. Then you need to round $q$ to the nearest $q' \in \mathbb Z[i]$ and get the residue. $\endgroup$ – Hw Chu Sep 29 '18 at 23:24
  • $\begingroup$ Okay, so the process is indeed a little different than doing synthetic division in $\mathbb{R}[i]$ or polynomial long division in that you get a quotient in $\mathbb{Q}$ and then round it to get a remainder? $\endgroup$ – Math is hard Sep 29 '18 at 23:26
  • 1
    $\begingroup$ Yes. The main ingredient is that you need to get $a = q'b + r$ where $|r| < |b|$. It is not hard to see that the $q', r$ obtained this way satisfy our needs. $\endgroup$ – Hw Chu Sep 29 '18 at 23:28
  • $\begingroup$ So I divided $85$ by $1+13i$ and got $85 - (1105/(1+13i))$ and now $(1105/(1+13i))$ = $(221/34) - (2873/34)i$.. where these rational numbers are $6.5$ and $8.5$, so I should round them up to $7$ and $9$ and get negative remainders? Or should I round them down? $\endgroup$ – Math is hard Sep 29 '18 at 23:37
  • $\begingroup$ Whichever is fine, as long as the remainder you get is less than the original numbers. $\endgroup$ – Hw Chu Sep 29 '18 at 23:38

$$ \frac{85}{1+13i} = \frac{85}{1+13i} \frac{1-13i}{1-13i}\\ = \frac{85 - 85*13 i}{1+169} = \frac{85}{170} + \frac{-1105}{170}\\ = (0 - 7 i) + (\frac{85}{170} + \frac{1}{2}i)\\ (1+13i)(-7i) = 91-7i\\ 85 - (91 - 7i) = -6 + 7i\\ GCD(85,1+13i) = GCD(85-(1+13i)(-7i),1+13i)\\ =GCD(-6+7i,1+13i) $$

Keep going like this. I suggest writing a script to do this automatically as part of the exercise.

  • $\begingroup$ editing in progress sorry $$ \frac{85}{1+13i} = (0 - 7 i) + (\frac{85}{170} + \frac{1}{2}i)\\ $$ I get what you did to get this far, and then after this you wrote: $$ (1+13i)(-7i) = 91-7i\\ 85 - (91 - 7i) = -6 + 7i\\ (85,1+13i) = (-6+7i,1+13i) $$ Do you also need to multiply $(1+13i)$ by $(\frac{85}{170} + \frac{1}{2}i)$? I'm a bit confused what you did from there $\endgroup$ – Math is hard Sep 29 '18 at 23:50

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.