Hola
Está bien la idea de pasar de la instancia (a,b) a una más chica (a, b-1). Pero están los problemas matemáticos que señala Nicolás. No se cumple que mcd(a,b) = mcd(a,b-1).
Sea m = mcd(a,b), o sea, existen a' y b' tal que a = m a' y b = m b'.
Supongamos sin pérdida de generalidad que a > b y sea r = a % b, o sea existe q tal que a = q b + r, con 0<= r < b.
Entonces r = a - q b = (a' - q b') m. Por lo tanto m es también factor común de b y de r. Y se puede demostrar que es el máximo de los factores comunes.
De aquí se puede obtener una instancia más chica. Y hay que manejar bien el caso base.
Está bien la idea de pasar de la instancia (a,b) a una más chica (a, b-1). Pero están los problemas matemáticos que señala Nicolás. No se cumple que mcd(a,b) = mcd(a,b-1).
Sea m = mcd(a,b), o sea, existen a' y b' tal que a = m a' y b = m b'.
Supongamos sin pérdida de generalidad que a > b y sea r = a % b, o sea existe q tal que a = q b + r, con 0<= r < b.
Entonces r = a - q b = (a' - q b') m. Por lo tanto m es también factor común de b y de r. Y se puede demostrar que es el máximo de los factores comunes.
De aquí se puede obtener una instancia más chica. Y hay que manejar bien el caso base.