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 . . .

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

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]?

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.

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: