Neste texto o leitor vai encontrar uma relação entre o cálculo do MDC entre dois números através do Algoritmo de Euclides para MDC e o Teorema de Bézout que trata de casos de equações diofantinas lineares.
Revisão MDC
Nesta introdução vamos relembrar como funciona o algoritmo de euclides para cálculo do MDC.
Primeiro, o Teorema que sustenta o Algoritmo de Euclides para divisão diz que: dados dois números a e b, então o mdc(b, a)=mdc(a, r), onde r é o resto na divisão de b por a.
E, isto permite que, assim, sigamos uma série de passos para encontrar o mdc entre dois números sem necessariamente fatorá-los, o que é uma tarefa bastante trabalhosa até para um computador dependendo dos números.
Por exemplo, vamos calcular o mdc de 70 e 40.
mdc(70, 40)
Como 70=1·40+30
mdc(70, 40) = mdc(40, 30)
Como 40=1·30+10
mdc(70, 40) = mdc(40, 30) = mdc(30, 10)
E, como 30=3·10
mdc(70, 40) = mdc(40, 30) = mdc(30, 10) = 10.
Fácil, né? Assim basta fazer a divisão euclidiana de forma recursiva até encontrarmos dois números em que um deles seja divisor do outro.
Caso haja dúvidas sobre a divisão euclidiana, o MDC e o algoritmo de Euclides, o leitor pode consultar os seguintes textos:
Algoritmo da divisão euclidiana
O Algoritmo de Euclides para mdc. Parte 1
O Algoritmo de Euclides para mdc. Parte 2
Teorema de Bézout
Agora, vamos ver o que diz o Teorema de Bézout.
Teorema. Dados a e b, inteiros não ambos nulos, existem n e m, inteiros, tais que mdc(a, b) = a·n + b·m.
Esse Teorema nos diz que é possível de alguma maneira escrever o mdc(a, b) como uma combinação com coeficientes inteiros de a e b. É um resultado bastante importante e está enunciado com os elementos que iremos usar nesse texto, mas o leitor pode ver em outros textos aqui do blog que é possível obter resultados mais gerais que esse.
O leitor sabe que é possível escrever mdc(a, b) = a·n + b·m, com n e m inteiros, a pergunta natural a se fazer agora é: mas como eu encontro esses m e n?
Veja, essa pergunta não tem necessariamente uma resposta fácil. Em matemática é comum conseguirmos afirmar a existência de objetos que não conseguimos descrever explicitamente. Neste caso, veremos a seguir que basta inverter o algoritmo de euclides para achar m e n.
MDC e Teorema de Bézout
Para aprender como usar o algoritmo de euclides para encontrar m e n vamos utilizarmos de um exemplo, o que deixará a tarefa mais prática.
Vamos utilizar o que já calculamos mdc(70, 40) = 10. Portanto, queremos achar m e n, tais que;
10 = 70m + 40n.
Antes do último passo para achar esse mdc no nosso exemplo, nós nos utilizamos que:
40 = 1·30+10
Agora, vamos isolar o 10, que é o mdc:
10 = 40 – 1·30 (1)
Daí, voltando um passo temos que: 70=1·40+30, e portanto agora, isolando o 30:
30 = 70-1·40
Daí, substituindo em (1):
10 = 40 – 1 (70-1·40)
Assim, 10 = 40 -1·70 + 1·40
10 = (1+1)·40 – 1·70
10 = -1·70 + 2·40
Assim, m=-1 e n=2.
Agora é sua vez, ache m e n tal que mdc(72, 28) = m·72 + n·28 e você pode conferir se sua resposta está correta aqui.
