Utilize o algoritmo de Euclides para encontrar o Máximo Divisor Comum:
Passo 1
O enunciado pede para encontrar o máximo divisor comum (mdc) de dois inteiros
e
usando o algoritmo de Euclides. Esse método consiste em dividir o número maior pelo menor, depois dividir o divisor pelo resto obtido, e assim por diante, até que o resto seja zero. O último resto não nulo será o mdc.
Passo 2
Dividimos
por
:
Aqui o resto é
.
Passo 3
Agora dividimos
pelo resto anterior
:
O novo resto é
.
Passo 4
Dividimos
por
:
O resto passa a ser
.
Passo 5
Dividimos
por
:
O resto agora é
.
Passo 6
Dividimos
por
:
Como o resto é zero, o algoritmo termina. O último resto não nulo é
, que é o mdc.