# Need help with Euclidean Algorithm in $\mathbb{Z}[i]$

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

• 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. – Hw Chu Sep 29 '18 at 23:24
• 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? – Math is hard Sep 29 '18 at 23:26
• 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. – Hw Chu Sep 29 '18 at 23:28
• 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? – Math is hard Sep 29 '18 at 23:37
• Whichever is fine, as long as the remainder you get is less than the original numbers. – 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)$$
• 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 – Math is hard Sep 29 '18 at 23:50