Exercicis de L'algorisme d'Euclides

Calcula el màxim comú divisor entre 252 i 198 mitjançant l'algorisme d'Euclides, i escriu-lo també com la suma $m c d (252, 198) = s_{n} \cdot 252 + t_{n} \cdot 198$ .

Veure desenvolupament i solució

Desenvolupament:

En aquest cas es té: $a = 252$ i $b = 198$ .
Es defineix: $r_{0} = 252, r_{1} = 198$ $s_{0} = 1, s_{1} = 0$ $t_{0} = 0, t_{1} = 1$
Ara es calcula la divisió entera entre $r_{0}$ i $r_{1}$ . El resultat és $1$ , i el residu $45$ . Per tant: $q_{1} = 1, r_{2} = 54$ Per altra banda: $s_{2} = s_{0} - s_{1} \cdot q_{1} = 1 - 0 \cdot 1 = 1$ $t_{2} = t_{0} - t_{1} \cdot q_{1} = 0 - 1 \cdot 1 = - 1$

Com que $r_{2} \neq 0$ , s'ha de continuar. Es fa la divisió entera entre $198$ (és a dir $r_{1}$ ) i $54$ (és a dir $r_{2}$ ), i s'obté de resultat $q_{2} = 3$ i residu $r_{3} = 36$ . Llavors: $s_{3} = s_{1} - s_{2} \cdot q_{2} = 0 - 1 \cdot 3 = - 3$ $t_{3} = t_{1} - t_{2} \cdot q_{2} = 1 - (- 1) \cdot 3 = 4$ Com que $r_{3} \neq 0$ , es realitza un pas més. Ara la divisió entera entre $54$ (que és $r_{2}$ ) i $36$ ( $r_{3}$ ) i s'obté: $q_{3} = 1$ i el residu és $r_{4} = 18$ . Ara: $s_{4} = s_{2} - s_{3} \cdot q_{3} = 1 - (- 3) \cdot 1 = 4$ $t_{4} = t_{3} - t_{2} \cdot q_{2} = - 1 - 4 \cdot 1 = - 5$ Com que $r_{4} \neq 0$ , es torna a repetir el procés. La divisió entera de $r_{3} = 36$ i $r_{4} = 18$ dóna com a resultat $q_{4} = 2$ , i el residu és $r_{5} = 0$ . Així doncs, ja no s'ha de seguir més!

Llavors $m c d (252, 198) = r_{4} = 18$ (perquè és el del penúltim pas). Per altra banda: $m c d (252, 198) = s_{4} \cdot 252 + t_{4} \cdot 198 = 4 \cdot 252 - 5 \cdot 198$

Solució:

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

Amagar desenvolupament i solució