Dejo mi solución, que también utiliza el algoritmo de Euclides(aunque iterativo). Es lo más eficiente, pues ponerte a factorizar los números y luego hallar el MCD y el mcm como tipicamente enseñan en escuela sólo tiene sentido didáctico.
http://jsfiddle.net/jefebrondem/8NEUJ/1/
Mi ejemplo cumple las especificaciones pero he debilitado un poco las condiciones para los argumentos de MCD y mcd, pues no he visto la necesidad de que fueran tan estrictas.