O objetivo deste texto é mostrar ao leitor as bases para o Algoritmo de Euclides para mdc, ele é parte 1 de uma série que ao final o leitor estará dominando o algoritmo. Essa algoritmo é bastante poderoso, pois, pode ajudar a calcular o MDC entre dois números em situações em que não é fácil encontrar seus divisores, e também é utilizado para resolver vários problemas matemáticos.
Revisão MDC
Antes de partir para o algoritmo em si é importante que o leitor tenha domínio do conceito de MDC, e aqui vamos fazer uma breve revisão dessa ideia.
O máximo divisor comum(MDC) entre dois números naturais a e b é denotado mdc(a, b) e é igual ao maior número natural que dívida a e b ao mesmo tempo. Daí o nome máximo divisor comum.
É importante notar que o número 1 divide todos os números, logo ele sempre é divisor comum de dois números naturais, o que faz que quaisquer dois números naturais possuam pelo menos um divisor em comum, que é o 1.
Quando o mdc entre dois números é igual a 1 dizemos que esses números são primos entre si. Se um dos números for divisor do outro então ele será igual ao mdc desses dois números.
Caso o leitor queira saber mais sobre o MDC pode conferir o seguinte texto:
Teorema para Algoritmo de Euclides para mdc
Agora que já revisamos o que é MDC vamos ver o teorema que motiva o desenvolvimento do Algoritmo de Euclides para MDC.
Teorema. Dados dois números naturais, a e b, então o mdc(a, b)=mdc(a, b-a).
Demonstrar esse fato é relativamente simples, basta observar que os divisores comuns de a e b são os mesmos divisores comuns de a e b-a.
De fato, se d é divisor de a e b, então particularmente d divide a e se d divide a e b então divide b-a. Portanto, se d é divisor de a e b então ele é divisor de a e b-a.
Reciprocamente, se d é divisor de a e b-a, em particular d divide a, e se d divide a e b-a então d divide a+(b-a)=b. Portanto, se d é divisor de a e b-a entao ele é divisor de a e b.
Isto é suficiente, pois se esses dois pares têm exatamente os mesmos divisores em comum, em particular o maior divisor comum entre eles também será o mesmo.
Próximos textos.
Este Teorema permite que a cada passo diminuamos a dificuldade em encontrar o MDC entre dois números e é justamente seguir esses passos que nos dão o algoritmo de euclides para o mdc.
Nos próximos textos vamos ver aprender o algoritmo em si, ver exemplos aplicados a números, exercícios e uma aplicação em linguagem C dele.
