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):
-
: quociente 2 , resto 12 .
-
: quociente 1 , resto 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,
e no enunciado). - Saída esperada: um inteiro que é o MDC desses dois números (por exemplo,
para e ). - Informação extra do enunciado (exemplo dado):
Resultado do exemplo: MDC é
.
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
e com , Explicação simples do porquê: se um número divide e , então divide qualquer combinação linear inteira de e , em particular divide (onde é o quociente inteiro de por ). O resto é exatamente . Assim os divisores comuns de são os mesmos de , então o maior divisor comum também é o mesmo. - Consequência prática: substituindo o par
por repetidamente reduzemos os valores até obter resto zero; o último divisor não nulo é o .
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
e . Se necessário, troque para garantir . - Enquanto
: - Calcule
(o resto da divisão inteira de por ). - Substitua
e .
- Calcule
- Quando o loop terminar (isto é, quando
), o valor de é o procurado. - Observação: se algum dos valores iniciais for
, vale a regra .
Passo 4
Explicando o operador “resto” (
) e como fazer as divisões sem calculadora.
- A operação
é o resto da divisão inteira de por . Pode pensar como: encontre o maior inteiro tal que , então o resto é com . - Exemplo numérico do enunciado (mostrando cada passo com conta):
Portanto . Portanto . Portanto . Como o resto é , o algoritmo termina e o MDC é o último divisor não nulo, que é .
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
: recebe dois inteiros e . a = abs(a)eb = abs(b)garantem que estamos trabalhando com valores não negativos (já queé definido para valores absolutos). while b != 0:implementa o passo repetitivo “enquanto”. a, b = b, a % bcorresponde exatamente à operação:Em Python a % bé o resto, e a atribuição simultânea troca os valores sem precisar de uma variável temporária. return ano final devolve o MDC quandoficou . - 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
e , a sequência interna será: Quando , o algoritmo retorna . - Portanto a saída mostrada pelo programa para a entrada
e será:
Passo 7
Casos especiais, validações e complexidade.
- Caso algum número seja
: . O código já lida com isso corretamente. - Números negativos: o uso de
absgarante 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
por 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
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))
x = int(input("Digite o primeiro inteiro: "))
y = int(input("Digite o segundo inteiro: "))
print(mdc(x, y))