Usando o algoritmo de Euclides calcule
\operatorname{mdc}(75,45)

Passo 1

O enunciado pede para calcular \gcd(75,45) usando o algoritmo de Euclides, que consiste em fazer divisões sucessivas: em cada etapa dividimos o maior número pelo menor, anotamos o resto e substituímos o par (a,b) por (b,r) até obter resto zero.

Passo 2

Dividimos 75 por 45:
75 = 45 \times 1 + 30
Como o resto é 30, temos
\gcd(75,45) = \gcd(45,30).

Passo 3

Agora dividimos 45 por 30:
45 = 30 \times 1 + 15
O resto é 15, então
\gcd(45,30) = \gcd(30,15).

Passo 4

Em seguida dividimos 30 por 15:
30 = 15 \times 2 + 0
O resto é zero, portanto o algoritmo termina e o máximo divisor comum é o último divisor não nulo, que é 15.

Resposta

\gcd(75,45)=15

Exercícios relacionados