MDC e Teorema de Bézout

Entre para nossa lista e receba conteúdos exclusivos!

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 que é MDC

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.

Outros Artigos

Saiba-mais-sobre-Bioquímica
Bioquímica

Saiba mais sobre Bioquímica

Saiba mais sobre a bioquímica e descubra como o estudo dos processos químicos abrangem um enorme campo de investigação.

Entre para nossa lista e receba conteúdos exclusivos!

contato@meuguru.com

CNPJ 42.269.770/0001-84

Nos siga nas redes!