• MDC eu sei que significa o Máximo Divisor Comum entre dois ou mais números naturais. |
Esse algoritmo é uma importante ferramenta da Teoria de Números e é muito simples de ser executado. |
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á… |
O primeiro passo você já deu: entendeu a propriedade que gera o algoritmo… |
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… |
Isso mesmo! |
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. |
Sonia Regina Di Giacomo
Equipe COM – OBMEP
Setembro de 2016.