Hola,
Es inmediato usando el "Course-of-values recursion", esto es, que la clase de funciones recursivas primitivas es cerrada bajo recursiones que involucran no solo el valor anterior de la función, sino todos los anteriores. Más formalmente, si definimos \( \bar{f}(x,y)=\langle f(x,0),...,f(x,y) \rangle \) y \( f(x,y) \) se define de la siguiente manera:
\( f(x,0)=g(x) \)
\( f(x,y+1)=h(x,y,\bar{f}(x,y)) \)
donde tanto g como h son recursivas primitivas, entonces también lo es f.
Para demostrar este teorema lo único que necesitas es ver que \( \bar{f} \) es recursiva primitiva (pues \( f(x,y)=(\bar{f}(x,y))_{y+1} \) donde \( ( )_{y+1} \) es la función de decodificación, que se puede tomar recursiva primitiva), y esto se ve con una recursión primitiva usual usando que la concatenación es recursiva primitiva.
En nuestro caso, hay algún detalle que hace que la recursión sea un poco más complicada de lo que pensaba en un principio (el hecho de que puedes tener m>n o m<n). Esto se puede solventar por ejemplo introduciendo una función auxiliar. Aplicando este esquema tendríamos (revísalo porque lo he pensado rápido):
\( mcd'(m,0)=m \)
\( mcd'(m,n+1) = (\bar{mcd'}(m,n))_{resto(n+1,m)} \) si \( resto(n+1,m)<n+1 \)
\( mcd'(m,n+1) = n+1 \) si \( resto(n+1,m)=n+1 \)
mcd' es recursiva primitiva. Finalmente,
\( mcd(m,n)=mcd'(max \{m,n \}, min \{m,n \}) \) es recursiva primitiva y la función buscada.
Si no te gusta mucho esta aproximación (que reconozco que ha sido un poco más liada de lo que preveía en un principio, aunque igual se puede hacer mucho más directo), puedes irte por el camino de definir máximo común divisor como el producto de los factores primos comunes a m y n elevados al menor exponente. Para esto necesitas saber un par de cosas sobre primos (la función primo(n) es recursiva primitiva, etc), divisibilidad es recursiva primitiva, productorios acotados son recursivos primitivos y minimización acotada de predicados recursivos primitivos es recursiva primitiva (esto último para definir el mayor exponente de p que divide a n).
Saludos