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.
Is there a way to easily know when these two numbers $m$ and $n$ are relatively prime, again without converting back to base-$10$ representations?
To implement the Euclidean algorithm we require only an effective (Euclidean) "division with smaller remainder" algorithm, and this can be implemented the same way in any radix - in analogy with the grade school long-hand decimal division algorithm (for integers - unlike polynomials - it suffices to have a subtraction algorithm and, of course, a comparison test, to determine the least).
Your prior answers imply you know some algebraic number theory so you must be familiar with basic ring theory, so let's view it from that perspective. The "representation" in radix representation means we have have a ring ${\rm\color{#c00}{isomorphism}}\ h\,$ that maps integers into their radix reps, with the radix arithmetic operations.
This ring isomorphism necessarily preserves the division algorithm: $ $ in the division $\,a\div b,\,$ if $\, a = q\,b+r,\ 0\le r < b\,$ $\rm\color{#c00}{then}$ $\,h(a) = h(q)h(b) + h(r),\ 0\le h(r) < h(b).\,$ By uniqueness of the quotient and remainder, $\,h(q)\,$ and $\,h(r)\,$ are the quotient and remainder of $\,h(a)\div h(b).\,$ This implies that the Euclidean remainder sequence of $\,\gcd(h(a),h(b))\,$ is the image under $h$ of the sequence for that of $\,\gcd(a,b).\,$ Thus the Euclidean algorithm works exactly the same in any isomorphic ring representation (though the "internal" calculations in the (radix) long division algorithm will differ because they do depend on the radix digits).
Of course it's easy to directly deduce that that ring isomorphisms preserve gcds and ideals (and their generators), but your question concerns specifically how the Euclidean algorithm maps under an isomorphism, so I focused on that.