MDC e o Algoritmo de Euclides Escreva um programa que calcule o Máximo Divisor Comum (MDC) entre dois números inteiros positivos utilizando o Algoritmo de Euclides.
Explicação do Método: O algoritmo baseia-se no princípio de que o MDC de dois números não muda se o maior número for substituído pelo resto da sua divisão pelo menor. O processo é repetido (divisões sucessivas) até que o resto seja zero. O último resto não nulo é o MDC.
  • Passo a passo (Exemplo MDC de 48 e 18):
  • 48 \div 18 : quociente 2 , resto 12 .
  • 18 \div 12 : quociente 1 , resto 6 .
  • 12 \div 6 : quociente 2 , resto 0 .
  • Resultado: O MDC é 6 .

Passo 1

O que o enunciado pede e quais são os dados.
  • Pedido: escrever um programa que calcule o Máximo Divisor Comum (MDC) entre dois inteiros positivos usando o Algoritmo de Euclides.
  • Entrada esperada: dois inteiros positivos (por exemplo, 48 e 18 no enunciado).
  • Saída esperada: um inteiro que é o MDC desses dois números (por exemplo, 6 para 48 e 18).
  • Informação extra do enunciado (exemplo dado): 48 \div 18:\\ \text{quociente }2,\\ \text{resto }12.
18 \div 12:\\ \text{quociente }1,\\ \text{resto }6.
12 \div 6:\\ \text{quociente }2,\\ \text{resto }0.
Resultado do exemplo: MDC é 6.

Passo 2

Entendendo a ideia matemática por trás do Algoritmo de Euclides (intuição e justificativa).
  • Propriedade central: para inteiros não-negativos a e b com a\ge b, \gcd(a,b)=\gcd\bigl(b,\,a\bmod b\bigr).Explicação simples do porquê: se um número d divide a e b, então divide qualquer combinação linear inteira de a e b, em particular divide a - q b (onde q é o quociente inteiro de a por b). O resto r=a-qb é exatamente a\bmod b. Assim os divisores comuns de (a,b) são os mesmos de (b,r), então o maior divisor comum também é o mesmo.
  • Consequência prática: substituindo o par (a,b) por (b,a\bmod b) repetidamente reduzemos os valores até obter resto zero; o último divisor não nulo é o \gcd.

Passo 3

Descrição passo a passo do algoritmo (versão iterativa, que é a mais simples e direta para implementar).
  • Comece com dois números inteiros não-negativos a e b. Se necessário, troque para garantir a\ge b.
  • Enquanto b\neq 0:
    1. Calcule r = a \bmod b (o resto da divisão inteira de a por b).
    2. Substitua a \leftarrow b e b \leftarrow r.
  • Quando o loop terminar (isto é, quando b=0), o valor de a é o \gcd procurado.
  • Observação: se algum dos valores iniciais for 0, vale a regra \gcd(a,0)=|a|.

Passo 4

Explicando o operador “resto” ( \bmod) e como fazer as divisões sem calculadora.
  • A operação a \bmod b é o resto da divisão inteira de a por b. Pode pensar como: encontre o maior inteiro q tal que qb \le a, então o resto é r=a-qb com 0\le r<b.
  • Exemplo numérico do enunciado (mostrando cada passo com conta): 48 \div 18:\quad q=\left\lfloor\frac{48}{18}\right\rfloor=2,\qquad r=48-2\cdot 18=48-36=12.Portanto 48\bmod18=12. 18 \div 12:\quad q=\left\lfloor\frac{18}{12}\right\rfloor=1,\qquad r=18-1\cdot 12=6.Portanto 18\bmod12=6. 12 \div 6:\quad q=\left\lfloor\frac{12}{6}\right\rfloor=2,\qquad r=12-2\cdot 6=0.Portanto 12\bmod6=0. Como o resto é 0, o algoritmo termina e o MDC é o último divisor não nulo, que é 6.

Passo 5

Implementação prática em Python (explicação linha a linha).
  • Aqui está um programa simples e robusto em Python que implementa o Algoritmo de Euclides de forma iterativa e lê dois inteiros do usuário:
def mdc(a, b):
    a = abs(a)
    b = abs(b)
    while b != 0:
        a, b = b, a % b
    return a

if __name__ == "__main__":
    x = int(input("Digite o primeiro inteiro: "))
    y = int(input("Digite o segundo inteiro: "))
    print(mdc(x, y))
Explicação das partes importantes (usando a notação matemática):
  • A função \text{mdc}(a,b): recebe dois inteiros a e b.
  • a = abs(a) e b = abs(b) garantem que estamos trabalhando com valores não negativos (já que \gcd é definido para valores absolutos).
  • while b != 0: implementa o passo repetitivo “enquanto b\neq 0”.
  • a, b = b, a % b corresponde exatamente à operação: r = a\bmod b,\quad a \leftarrow b,\quad b \leftarrow r.Em Python a % b é o resto a\bmod b, e a atribuição simultânea troca os valores sem precisar de uma variável temporária.
  • return a no final devolve o MDC quando b ficou 0.
  • O bloco if __name__ == "__main__": faz o programa ler dois inteiros do utilizador e imprimir o resultado.

Passo 6

Executando o programa com o exemplo do enunciado.
  • Se executar a função com a=48 e b=18, a sequência interna será: (a,b)=(48,18)\\ \xrightarrow{a\bmod b=12}\\ (18,12)\\ \xrightarrow{a\bmod b=6}\\ (12,6)\\ \xrightarrow{a\bmod b=0}\\ (6,0).Quando b=0, o algoritmo retorna a=6.
  • Portanto a saída mostrada pelo programa para a entrada 48 e 18 será: 6

Passo 7

Casos especiais, validações e complexidade.
  • Caso algum número seja 0: \gcd(a,0)=|a|. O código já lida com isso corretamente.
  • Números negativos: o uso de abs garante que o sinal não afete o resultado.
  • Complexidade: o Algoritmo de Euclides é muito eficiente. Em termos grosseiros, o número de iterações é proporcional ao número de dígitos (logaritmo dos valores). Para números grandes, é rápido na prática.
  • Dica para prova: se pedirem para aplicar manualmente, faça divisões sucessivas calculando quociente inteiro e resto como mostrado no exemplo; pare quando o resto for zero.

Passo 8

Encorajamento final (você consegue!)
  • O Algoritmo de Euclides é superfácil de entender e de implementar. Na prova, basta lembrar a regra de substituir (a,b) por (b,a\bmod b) até o resto ser zero, e escrever o loop (ou aplicar as divisões manualmente). Se ficar nervoso, faça as divisões com calma e anote quociente e resto passo a passo como no exemplo.

Resposta

def mdc(a, b):
a = abs(a)
b = abs(b)
while b != 0:
a, b = b, a % b
return a
if name == “main”:
x = int(input("Digite o primeiro inteiro: "))
y = int(input("Digite o segundo inteiro: "))
print(mdc(x, y))

Exercícios relacionados