Demuestre que $gcd(x,y)$ y $z = lcm(x,y)$ es primitivo recursivo

Question

Para el $gcd(x,y)$ observamos:

$gcd(x,0) = x$

$gcd(x,succ(y)) = gcd(succ(y),mod(x,succ(y)))$

$succ(x)$ y $mod(x,y)$ son ambas recursivas primitivas, por lo que $gcd(x,y)$ también debe serlo.

$z = lcm(x,y)$ si $x|z$ y $y|z$ y cuando $x|w$ y $y|w$ , $z \leq w$ . Demuestre que $z = lcm(x,y)$ es recursivo primitivo.

¿Podemos definir $lcm(x,y)$ de la misma manera $gcd$ se define más arriba? Creo que debería haber alguna manera de incorporar los dos juntos (de tal manera que $lcm$ depende de $gcd$ ). ¿Cómo podemos demostrar que $lcm$ ¿es primitiva recursiva?

Answer 1

¿Qué te parece esto? $$\operatorname{lcm}(x,y) = \frac{xy}{\gcd(x,y)}?$$