MDC pelo algoritmo de Euclides
Calcule o máximo divisor comum com as divisões sucessivas, veja o retângulo ser coberto por quadrados, confira o MMC e os coeficientes de Bézout.
MDC pelo algoritmo de Euclides
O máximo divisor comum (MDC) de dois inteiros é o maior número que divide os dois. O algoritmo de Euclides o encontra sem fatorar nada: divide o maior pelo menor, troca o par pelo divisor e pelo resto, e repete até o resto zero. O último divisor não nulo é o MDC.
Por que funciona
Se d divide a e b, então d também divide a − q·b. Logo, o conjunto de divisores comuns de a e b é o mesmo de b e do resto r. A cada passo o número diminui, então o processo termina.
O retângulo
Um retângulo a × b pode ser coberto por quadrados. Coloque quantos quadrados de lado b couberem, depois o resto vira um novo retângulo, e assim por diante. O menor quadrado que aparece tem lado igual ao MDC: é o maior quadrado que cobre os dois lados sem sobras.
MMC e Bézout
O mínimo múltiplo comum satisfaz MDC × MMC = |a| × |b|. Por isso o MMC é calculado a partir do MDC.
A identidade de Bézout diz que existem inteiros x e y com a·x + b·y = MDC(a, b). O algoritmo de Euclides estendido encontra esses coeficientes ao acompanhar as divisões. Esses inteiros não são únicos: somando b/MDC a x e subtraindo a/MDC de y, obtém-se outro par.
Entradas
Use inteiros, com sinal opcional, de até 30 dígitos. Zero é aceito: MDC(a, 0) = |a|. Números decimais e textos são recusados com mensagem.
Desafios
Calcule o MDC de 1071 e 462 pelos passos. Quantas divisões foram necessárias?
Dica
Cada linha troca o par: o divisor vira dividendo e o resto vira divisor.
Por que o último lado do quadrado coincide com o MDC? Escolha um retângulo 21 × 13 e confira.
Dica
Observe o menor quadrado que cobre o retângulo sem sobras.
Encontre inteiros x e y com 240x + 46y = 2. Eles são únicos?
Dica
A tabela de Bézout mostra um par; somar 23 ao x e subtrair 120 ao y gera outro par.
Com a = 12 e b = 18, confira que MDC × MMC = a × b.
Dica
O MMC aparece nos resultados; multiplique os dois e compare com 12 × 18.
Continue daqui
Pré-requisitos
Próximos passos
Veja também
Conceitos
Cada conceito leva à lista de aulas que o usam, por disciplina.
Trilha de estudo: Números · Mapa de conceitos