Sala de Estudo: Algoritmo de Euclides para determinação de MDC

MDC eu sei que significa o Máximo Divisor Comum entre dois ou mais números naturais.
Algoritmo é uma sequência finita de passos a serem seguidos para a execução de uma tarefa.
Euclides foi um importante matemático grego da antiguidade.
Mas eu não conheço o Algoritmo de Euclides para determinação de MDC . . .

Probleminha2

Esse algoritmo é uma importante ferramenta da Teoria de Números e é muito simples de ser executado.
Vamos estudá-lo; mas, antes, é bom recordar que o máximo divisor comum de dois números naturais [tex]a[/tex] e [tex] b [/tex] é o maior dos números que dividem tanto [tex]a[/tex] quanto [tex] b [/tex].
Nas nossas discussões, vamos indicar o MDC de [tex]a[/tex] e [tex]b[/tex] por [tex]mdc(a,b)[/tex].

Algoritmo de Euclides para determinação de MDC



F1
 

Antes de prosseguirmos, observe que, no cálculo do MDC dos números naturais [tex]a[/tex] e [tex]b[/tex], não precisamos nos preocupar quando a condição [tex]\boxed{a>b>0}[/tex] não for satisfeita, uma vez que:
[tex] \, \, \, (i) \, \, mdc(0,0)[/tex] não está definido;
[tex] \, \, \, (ii) \, \, mdc(n,n) = n[/tex], para qualquer natural não nulo [tex]n[/tex];
[tex] \, \, \, (iii) \, \, mdc(m,n) = mdc(n,m)[/tex], para quaisquer números naturais não ambos nulos [tex]m[/tex] e [tex]n[/tex];
[tex] \, \, \, (iv) \, \, mdc(n,0) = n[/tex], para qualquer número natural não nulo [tex]n[/tex].

Vocês saberiam justificar essas quatro afirmações?

Tá…
Mas como calcular o máximo divisor comum de números naturais [tex]m[/tex] e [tex]n[/tex], com [tex]m \gt n\gt0[/tex], sabendo que se [tex]r[/tex] é o resto da divisão de [tex]m[/tex] por [tex]n[/tex], então [tex]mdc(m,n)=mdc(n,r)[/tex]?

Desafio2

O primeiro passo você já deu: entendeu a propriedade que gera o algoritmo…
E, neste momento, não é necessário saber justificar essa propriedade. Basta entendê-la e aplicá-la com cuidado, conforme veremos a seguir.
Mas, antes, vamos destacar mais uma vez essa propriedade, pois é ela que garante o sucesso do processo!

IMPORTANTE

O máximo divisor comum entre dois números naturais não nulos e distintos é igual ao máximo divisor entre o menor e o resto da divisão do maior pelo menor.
Em símbolos, se [tex]x \, [/tex] e [tex] \, y \, [/tex] são números naturais tais que [tex] \, x\gt y\gt 0 \, [/tex], e se

[tex]x[/tex] [tex]y[/tex]
[tex]r [/tex] [tex]q[/tex]

então [tex]\fcolorbox{black}{#CDC9C9}{$mdc(x,y)=mdc(y,r)$}[/tex].

O Processo



1) Pelo até agora exposto, para calcularmos o MDC de dois números naturais [tex]a[/tex] e [tex]b \, [/tex] tais que [tex]a \gt b \gt 0[/tex], fazemos a divisão euclidiana de [tex]a[/tex] por [tex]b \, [/tex]:

[tex]a[/tex] [tex]b[/tex]
[tex]r_1 [/tex] [tex]q_1[/tex]

com [tex]0\le r_1 \le b[/tex].

[tex] \, \, \bullet[/tex] Se o resto dessa divisão for zero, então [tex]mdc(a,b) = mdc(b,0)=b[/tex] e acabou o problema. (veja [tex](iv)[/tex])
[tex] \, \, \bullet[/tex] Caso o resto [tex]r_1[/tex] seja diferente de zero, então [tex]mdc(a,b) = mdc(b, r_1)[/tex] e passamos a nos preocupar agora com o MDC de [tex]b[/tex] e [tex]r_1[/tex].
 
2) Façamos, então, a divisão euclidiana de [tex]b[/tex] por [tex]r_1[/tex]:

[tex]b[/tex] [tex]r_1[/tex]
[tex]r_2 [/tex] [tex]q_2[/tex]

com [tex]0\le r_2 \le r_1[/tex].

[tex] \, \, \bullet[/tex] Se o resto dessa divisão for zero, então [tex]mdc(a,b) = mdc(b, r_1)= mdc(r_1, 0)=r_1[/tex] e acabou o problema.
[tex] \, \, \bullet[/tex] Caso o resto [tex]r_2[/tex] seja diferente de zero, então [tex]mdc(b, r_1)= mdc(r_1, r_2)[/tex] e agora vamos determinar o MDC de [tex]r_1[/tex] e [tex]r_2[/tex].
 
3) Façamos, pois, a divisão euclidiana de [tex]r_1[/tex] por [tex]r_2[/tex]:

[tex]r_1[/tex] [tex]r_2[/tex]
[tex]r_3 [/tex] [tex]q_3[/tex]

com [tex]0\le r_3 \lt r_2[/tex].

[tex] \, \, \bullet[/tex] Se o resto dessa divisão for zero, então [tex]mdc(a,b) = mdc(b, r_1)= mdc(r_1, r_2)= mdc(r_2, 0)=r_2[/tex] e acabou o problema.
[tex] \, \, \bullet[/tex] Se o resto [tex]r_3[/tex] for diferente de zero, então [tex]mdc(r_1, r_2)= mdc(r_2, r_3)[/tex] e agora passamos a nos preocupar com o MDC de [tex]r_2[/tex] e [tex]r_3[/tex].
 
4) Façamos, agora, a divisão euclidiana de [tex]r_2[/tex] por [tex]r_3[/tex]:

[tex]r_2[/tex] [tex]r_3[/tex]
[tex]r_4 [/tex] [tex]q_4[/tex]

com [tex]0\le r_4 \lt r_3[/tex].

[tex] \, \, \bullet[/tex] Se o resto dessa nova divisão for zero, então o problema está resolvido, pois
[tex]\quad\quad\quad mdc(a,b) = mdc(b, r_1)= mdc(r_1, r_2)=mdc(r_2, r_3)=mdc(r_3, 0)=r_3[/tex].
[tex] \, \, \bullet[/tex] Se o resto [tex]r_4[/tex] for diferente de zero, então [tex]mdc(r_2, r_3)= mdc(r_3, r_4)[/tex] e agora passamos a nos preocupar com o MDC de [tex]r_3[/tex] e [tex]r_4.[/tex]

Esse processo de divisões sucessivas não terá fim?

Observe que, se nas nossas divisões obtivermos um resto [tex]r_{n+1}[/tex] igual a zero, o processo termina pois
[tex] \, \, \, \, \, \, mdc(a,b) = mdc(b, r_1)= mdc(r_1, r_2)=mdc(r_2, r_3)=\cdots=mdc(r_{n-1}, r_{n})=\\ \, \, \, \, \, \, \, \, \, \, \, \, \, \, \qquad \; \; \; =mdc(r_{n}, r_{n+1})=mdc(r_{n}, 0)=r_ n[/tex]
Assim, esse processo de divisões sucessivas só não irá terminar se não obtivermos um resto nulo.
Então, cabe a pergunta: é possível não obtermos um resto zero?
Observemos os restos obtidos até a quarta divisão: [tex]0\lt r_4 \lt r_3 \lt r_2 \lt r_1 \lt b[/tex].
De maneira geral, quando encontramos um resto não nulo efetuamos uma divisão cujo resto é menor do que o resto anterior, que já era menor que o seu anterior.
Assim, se não encontrarmos um resto zero, obteremos uma sequência decrescente de infinitos números naturais não nulos, todos menores do que [tex]b [/tex]:
[tex] \, \, \, \, \, \, b>r_1>r_2>r_3>r_4>\cdots>0[/tex]
o que não é possível, pois sabemos que existem apenas [tex]b-1[/tex] números naturais não nulos que são menores do que [tex]b[/tex].

Ufa…., então o processo acaba e o [tex]mdc(a,b)[/tex] é o último resto não nulo do processo de divisões sucessivas.

Hummmmm, acho que entendi…
A ideia é dividir o maior número pelo menor, e depois fazer divisões sucessivas do último divisor pelo último resto, até obtermos uma divisão exata.

carinha4

Isso mesmo!
Podemos, então, aplicar o processo.

Dois exemplos



1) Calcular mdc(32,12) .
 
Para tanto executaremos o processo das divisões sucessivas, iniciando pela divisão euclidiana de 32 por 12:

32 12      12 8      8 4
8 2      4 1      0 2

Assim, podemos afirmar que mdc(32, 12)=mdc(12, 8)=mdc(8,4)=mdc(4,0)=4 e, dessa forma, mdc(32,12)=4.
 
2) Calcular mdc(1320,25) .
 
Mais uma vez, vamos executar o processo das divisões sucessivas:

1320 35      35 25      25 10      10 5
25 37      10 1      5 2      0 2

Assim, mdc(1320, 35)=mdc(35, 25)=mdc(25,10)=mdc(10,5)=mdc(5,0)=5 e, então, mdc(1320,35)=5.

Podemos simplificar um pouco o processo.
Veja como, na próxima sala…
É só clicar AQUI!



Sonia Regina Di Giacomo
Equipe COM – OBMEP

Link permanente para este artigo: http://clubes.obmep.org.br/blog/sala-de-estudos-algoritmo-de-euclides-para-determinacao-de-mdc/

Algoritmo de Euclides para determinação de MDC – Utilizando Diagramas

Vamos apresentar um modo mais simples de indicar as divisões sucessivas do Algoritmo de Euclides. Observe… Utilizando Diagramas Podemos indicar as sucessivas divisões do Algoritmo de Euclides de uma maneira mais prática. Vamos exemplificar como isso pode ser feito, utilizando as divisões obtidas no segundo exemplo. 1320 35      35 25      25 10      …

Algoritmo de Euclides para determinação de MDC – Maquineta

  Estamos disponibilizando uma maquineta que calcula o MDC de dois números naturais não nulos com, até, dez dígitos cada. Maquineta A maquineta funciona adequadamente no Excel. A maquineta é bem legal. Faça bom proveito! Sonia Regina Di Giacomo Equipe COM – OBMEP Voltar para a Sala de Estudos sobre o Algoritmo de Euclides Ir …

Algoritmo de Euclides para determinação de MDC – Uma interpretação geométrica

Uma interpretação geométrica do MDC É importante saber calcular o MDC de dois números, e para isso o Algoritmo de Euclides e a Maquineta podem ajudá-los. Mas é igualmente importante vocês compreenderem o que significa o MDC de dois números. Vejam abaixo uma atividade com a qual vocês podem obter uma interpretação interessante do MDC. …

Algoritmo de Euclides para determinação de MDC – Material de apoio

Disponibilizamos aqui material de apoio para você aprender um pouco mais sobre MDC e, é claro, sobre o Algoritmo de Euclides.                 BONS ESTUDOS! Vídeo Divisores e MDC – Algoritmo de Euclides Professor Fabio Henrique Teixeira de Souza. Textos • Um Método para o cálculo do mdc e do mmc; Roberto Ribeiro Paterlini. • Uma interpretação …

Algoritmo de Euclides para determinação de MDC – Um segundo estudo

Disponibilizamos aqui material de apoio para um segundo estudo do Algoritmo de Euclides. Aqui vocês terão que se dedicar um pouco mais aos estudos; mas vale a pena, vocês vão aprender muito mais… Bom proveito! I – Vídeo Algoritmo de Euclides revisitado Professor Fabio Henrique Teixeira de Souza. II – Textos • MDC, MMC, Algoritmo …