# arithmetic – How does one calculate gcd of two numbers if they are not written in base 10, without converting it to base 10 and converting back?

Let us say that I have two numbers $$m$$ and $$n$$ and $$a$$ is a positive number bigger than 2. Also assume that base-$$a$$ representations of $$m$$ and $$n$$ are:

$$m = r_{M}a^{M} + r_{M-1}a^{M-1} + … + r_{1}a + r_{0}$$ and $$n = s_{N}a^{N} + s_{N-1}a^{N-1} + … + s_{1}a + s_{0}$$

where all the $$r_{j}$$ and $$s_{j}$$ are in $${0, 1, … , a-1}$$.

I was wondering if I could calculate the quantity $$gcd (m, n)$$, without going back to base-$$10$$ representations? I have never even heard of $$gcd$$ in other bases before. I would really appreciate any suggestions or help.