Ejercicios de El algoritmo de Euclides

Calcula el máximo común divisor entre $$252$$ y $$198$$ mediante el algoritmo de Euclides, y escríbelo también como la suma $$mcd(252,198)=s_n\cdot 252+t_n\cdot 198$$.

Ver desarrollo y solución

Desarrollo:

  • En este caso se tiene: $$a = 252$$ y $$b = 198$$.

  • Se define: $$$r_0=252, \ r_1=198$$$ $$$s_0=1, \ s_1=0$$$ $$$t_0=0, \ t_1=1$$$

  • Ahora se calcula la división entera entre $$r_0$$ y $$r_1$$. Se tiene que el resultado es $$1$$, y el residuo $$45$$. Por lo tanto: $$$q_1=1, \ r_2=54$$$ Por otro lado: $$$s_2=s_0-s_1\cdot q_1=1-0\cdot1=1$$$ $$$t_2=t_0-t_1\cdot q_1=0-1\cdot1=-1$$$

Como $$r_2\neq0$$, se tiene que continuar. Se hace la división entera entre $$198$$ (es decir $$r_1$$) y $$54$$ (es decir $$r_2$$), y se obtiene de resultado $$q_2=3$$ y residuo $$r_3=36$$. Entonces: $$$s_3=s_1-s_2\cdot q_2=0-1\cdot3=-3$$$ $$$t_3=t_1-t_2\cdot q_2=1-(-1)\cdot3=4$$$ Como $$r_3\neq0$$, se realiza un paso más. Ahora la división entera entre $$54$$ (que es $$r_2$$) y $$36$$ ($$r_3$$) y se obtiene: $$q_3=1$$ y el residuo es $$r_4=18$$. Ahora: $$$s_4=s_2-s_3\cdot q_3=1-(-3)\cdot1=4$$$ $$$t_4=t_3-t_2\cdot q_2=-1-4\cdot1=-5$$$ Como $$r_4\neq0$$, se vuelve a repetir el proceso. La división entera de $$r_3=36$$ y $$r_4=18$$ da como resultado $$q_4=2$$, y el residuo es $$r_5=0$$. Así pues, ¡ya no se tiene que seguir más!

  • Entonces se tiene que $$$mcd(252,198)=r_4=18$$$ (porque es el del penúltimo paso). Por otro lado: $$$mcd(252,198)=s_4\cdot252+t_4\cdot198=4\cdot252-5\cdot198$$$

Solución:

$$mcd(252,198)=18=4\cdot252-5\cdot198$$

Ocultar desarrollo y solución
Ver teoría