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.