Lo unico que puedo darte por ahora es la funcion del mcd, como la acabo de hacer no se si tendrá algun fallo, de todas maneras espero que te sirva, antes de incorporarla a tu programa prueba todas la posibilidades para ver si mi funcion funciona perfectamente, bueno te dejo el codigo y un saludo.
int mcd(int a, int b)
{
int r;
if (b!=0)
r=mcd(b, a%b);
else r=a;
return r;
}