Teoria de números/Máximo divisor comum

No capítulo anterior, foi demonstrado o [[../Números primos#Teorema fundamental da aritmética|teorema fundamental da aritmética]]. No entanto, a prova apresentada, utilizou-se de um resultado cuja prova apresentaremos neste capítulo. Para tanto, será preciso definir o conceito de máximo divisor comum entre dois números inteiros.

Este é o conteúdo da próxima seção.

Divisores comuns

Exemplos

Quem são os divisores comuns de a e b?

O conjunto formado pelos divisores comuns de $a$ e $b$ será denotado por $D(a,b)$.

No primeiro capítulo, [[../Divisibilidade#Propriedades da divisibilidade|mostrou-se]] que o número $1$ é divisor de qualquer número inteiro. Em particular, se forem escolhidos números $a$ e $b$, certamente $1$ será um divisor comum de ambos.

Logo, o conjunto $D(a,b)$ é não vazio, pois $1\in D(a,b)$.

O maior dos divisores comuns

Se $a\ne 0$ e $d$ for um divisor comum de $a$ e de $b$, então $|d|\le |a|$. Logo o conjunto $D(a,b)$ é limitado superiormente e deve ter um elemento máximo, ou seja, existe um divisor comum de $a$ e $b$ maior que todos os demais. Analogamente, para $b\ne 0$, o conjunto $D(a,b)$ também tem um elemento máximo. O único caso que $D(a,b)$ não é limitado superiormente é o conjunto $D(0,0)$, já que zero é múltiplo de qualquer inteiro não-nulo.

Isso motiva a próxima definição.

Definição de MDC

Predefinição:Definição Predefinição:Wikipedia Quando o conjunto $D(a,b)$ possui apenas um elemento positivo, ou seja, quando $(a,b)=1$, os números $a$ e $b$ são ditos primos entre si, relativamente primos ou simplesmente co-primos.

Exemplo

Qual é o máximo divisor comum entre $12$ e $15$?

Considerando que os divisores de $12$ são os elementos do conjunto $D(12)=\{\pm 1,\pm 2,\pm 3,\pm 4,\pm 6,\pm 12\}$ e que os divisores de $15$ formam o conjunto $D(15)=\{\pm 1,\pm 3,\pm 5,\pm 15\}$, tem-se que $D(12,15)=\{\pm 1,\pm 3\}$, cujo maior elemento é $3$. Portanto, $mdc(12,15)=3$.

Embora ainda não tenha sido explicado como encontrar o máximo divisor comum de dois números inteiros (isso será feito mais adiante), mostra-se que ele é um dos elementos do conjunto $\{ax+by:x,y\in \mathbb{Z}\}$. Este resultado é um teorema surpreendente, pois relaciona a estrutura multiplicativa do conjunto dos números inteiros que foi estudada até agora, com sua estrutura aditiva:

Teorema de Bézout

Predefinição:Teorema Predefinição:Wikipedia O resultado também é conhecido como identidade de Bézout.

Antes de apresentar qualquer justificativa (construtiva ou puramente algébrica) dessa identidade, serão mostradas suas consequências imediatas mais importantes.

Corolário

Predefinição:Corolário Predefinição:Demonstração Predefinição:Wikipedia Com essa propriedade, devida a Euclides de Alexandria, já é possível demonstrar o teorema que [[../Números primos#Teorema fundamental da aritmética|ficou pendente]] no capítulo anterior:

Demonstração do teorema de Bézout

Uma observação crucial para a demonstração do teorema de Bézout é que, para quaisquer números inteiros $a,b$, tem-se a igualdade $(a,b)=(a-b,b)$.

De fato, para que tal propriedade se verifique, é suficiente que os conjuntos $D(a,b)$ e $D(a-b,b)$ sejam iguais. Isso é verdade, pois:

• Se um deles está definido, então o outro também está. De fato, para b diferente de zero ambos conjuntos são definidos; para b igual a zero temos que a deve ser diferente de zero, e os dois conjuntos são iguais.
• Se $d\in D(a,b)$, então $d|a$ e $d|b$.

Donde, $d|a-b$.

Assim, $d\in D(a-b,b)$.

• Reciprocamente, se $d\in D(a-b,b)$, então $d|a-b$ e $d|b$. Logo, deve dividir a soma:

$d|(a-b)+b=a$,

ou seja, $d\in D(a,b)$.

Outra propriedade do máximo divisor comum é a seguinte:

$(b,a)=(a,b)=(-a,b)=(a,-b)$

Por causa dela, pode ser suposto que $a\ge b\ge 0$, e obter a demonstração: Predefinição:Demonstração Predefinição:Wikipedia Como toda prova por indução, a demonstração anterior fornece um algoritmo. No caso, trata-se de um procedimento para o cálculo de $(a,b)$:

Dados de entrada
  Os inteiros $a$ e $b$.

Saída
  $(a,b)$.

Procedimento
* Se $a<b$, então $(a,b)=(b,a)$;
* Se $b=0$, então $(a,b)=a$;
* Senão $(a,b)=(a-b,b)$

Exemplos numéricos

Usando o procedimento sugerido, pode-se calcular $(30,18)$ facilmente. Acompanhe:

$(30,18)=(12,18)=(18,12)=(6,12)=(6,6)=(0,6)=(6,0)=6$

No entanto, quando se tem $a$ bem maior que $b$, a igualdade mais utilizada será $(a,b)=(a-b,b)$.

Por exemplo, se $a=100$ e $b=3$ as etapas serão:

$(100,3)=(97,3)=(94,3)=\dots =(4,3)=(1,3)$ $=(3,1)=(2,1)=(1,1)=(0,1)=(1,0)=1$

Neste caso, parece razoável subtrair $3$ de $100$ tantas vezes quanto for possível, em uma única etapa:

$(100,3)=(100-3\cdot 33,3)=(1,3)=1$

Em geral, será buscado um valor $q$ tal que $0\le a-bq<b$, pois assim a igualdade $(a,b)=(a-bq,b)$ (que é sempre verdadeira, para qualquer valor inteiro de $q$) reduz o cálculo de $(a,b)$ a um caso bem mais simples.

A existência de um número $q$, satisfazendo ambas as desigualdades é garantida pelo algoritmo da divisão apresentado em um capítulo anterior. Se precisar relembrar os detalhes, consulte a seção "Algoritmo da divisão (de Euclides)".

De posse deste algoritmo, pode-se fazer uma melhoria no algoritmo sugerido anteriormente para o cálculo do MDC.

Algoritmo de Euclides para o MDC

Observe que esta é simplesmente uma generalização do algoritmo apresentado logo após a demonstração do teorema de Bézout. Predefinição:Wikipedia É preciso verificar que o algoritmo irá parar, e ainda mais importante, que fornecerá a resposta correta. Predefinição:Demonstração/Início Considere $r_0=a$ e $r_1=b$, e a seguinte sequência de igualdades (obtidas pelo algoritmo da divisão):

$r_0=$	$r_1{q}_0+r_2$	$0\le r_2<r_1$
$r_1=$	$r_2{q}_1+r_3$	$0\le r_3<r_2$
$⋮$
$r_{k-2}=$	$r_{k-1}{q}_{k-2}+r_k$	$0\le r_k<r_{k-1}$
$r_{k-1}=$	$r_k{q}_{k-1}+r_{k+1}$	$0\le r_{k+1}<r_k$
$⋮$

Juntando as desigualdades anteriores, tem-se uma sequência decrescente de números não negativos:

$r_1>r_2>r_3>\dots >r_k>\dots \ge 0$

No entanto, só existe uma quantidade finita de números positivos menores que $r_1$. Logo, depois de algum resto $r_k$, tem-se $r_{k+1}=0$, ou seja:

$r_1>r_2>r_3>\dots >{𝐫}_{𝐤}>r_{k+1}=0$

É nesse ponto que o algoritmo para: quando o resto $r_{k+1}=0$. Segundo o enunciado, o resultado fornecido será então $r_k$.

Será que este é realmente o valor de $(a,b)$?

A resposta é sim, pois $(a,b)=(a-b,b)=(a-2b,b)=(a-3b,b)=\dots =(a-bq,b)$.

Logo, obtem-se sucessivamente:

$(a,b)=(r_0,r_1)=(r_1,r_2)=\dots =({𝐫}_{𝐤},r_{k+1})=({𝐫}_{𝐤},0)={𝐫}_{𝐤}$

Portanto o valor fornecido pelo algoritmo corresponde a $(a,b)$, e foi obtido através de exatamente $k$ divisões. Predefinição:Demonstração/Fim

Exemplo numérico

Quanto é $(30,18)$?

Aplicando o processo usado na demonstração do algoritmo de Euclides para o MDC, tem-se:

$30=18\cdot 1+12$

$18=12\cdot 1+\mathrm{𝟔}$

$12=\mathrm{𝟔}\cdot 2+0$

Logo, $(30,18)=6$.

Para que não seja preciso explicitar cada uma das igualdades, pode-se dispor as informações de cada etapa em uma tabela como a seguinte:

quociente	1	1	2
30	18	12	6
Resto	12	6	0

É importante notar que, embora os quocientes apareçam indicados, o interesse está no valor dos restos.

Para obter automaticamente todas as etapas da aplicação do algoritmo de Euclides a outros pares de números inteiros, pode-se utilizar este recurso on-line, desenvolvido em javascript.

Interpretação matricial

Na demonstração de que o algoritmo de Euclides funciona, aparecem várias igualdades da forma:

$r_{j-1}=r_j{q}_{j-1}+r_{j+1}$

O índice $j$ indica que esta é a $j$-ésima divisão efetuada no algoritmo.

Cada uma dessas equações é uma equação de diferenças de segunda ordem, em que cada termo é descrito em função de dois anteriores. No caso, cada resto depende dos próximos dois restos, e reciprocamente, cada resto depende dos dois anteriores.

Tal relação de recorrência pode também ser expressa como:

$\left[\begin{array}{c}{r}_{j-1}\\ r_j\end{array}\right]=\left[\begin{array}{cc}{q}_{j-1}& 1\\ 1& 0\end{array}\right]\cdot \left[\begin{array}{c}{r}_j\\ r_{j+1}\end{array}\right]$, sempre que $1\le j\le k$

Com essa notação, os cálculos que aparecem no algoritmo de Euclides para o MDC tornam-se mais sucintos. Por exemplo:

$\left[\begin{array}{c}{r}_0\\ r_1\end{array}\right]$	$=\left[\begin{array}{cc}{q}_0& 1\\ 1& 0\end{array}\right]\cdot \left[\begin{array}{c}{r}_1\\ r_2\end{array}\right]$
	$=\left[\begin{array}{cc}{q}_0& 1\\ 1& 0\end{array}\right]\cdot \overbrace{\left[\begin{array}{cc}{q}_1& 1\\ 1& 0\end{array}\right]\cdot \left[\begin{array}{c}{r}_2\\ r_3\end{array}\right]}$
	$=\left[\begin{array}{cc}{q}_0& 1\\ 1& 0\end{array}\right]\cdot \left[\begin{array}{cc}{q}_1& 1\\ 1& 0\end{array}\right]\cdot \overbrace{\left[\begin{array}{cc}{q}_2& 1\\ 1& 0\end{array}\right]\cdot \left[\begin{array}{c}{r}_3\\ r_4\end{array}\right]}$

Para facilitar ainda mais a escrita, pode-se adotar a seguinte convenção:

$Q_j=\left[\begin{array}{cc}{q}_j& 1\\ 1& 0\end{array}\right]$

Se o cálculo anterior for efetuado para todas as etapas do algoritmo, o resultado final será:

$\left[\begin{array}{c}{r}_0\\ r_1\end{array}\right]=Q_0\cdot Q_1\cdot \dots \cdot Q_{k-1}\cdot \left[\begin{array}{c}d\\ 0\end{array}\right]=M\cdot \left[\begin{array}{c}d\\ 0\end{array}\right]$, sendo que $d=(a,b)$.

Perceba que assim não há uma confusão tão grande com os índices dos sucessivos quocientes e restos.

Como a matriz $M$ é um produto de matrizes com entradas inteiras e não-negativas, nenhuma de suas entradas deverá ser negativa. Assim, é possível escrever $M$ da seguinte forma:

$M=\left[\begin{array}{cc}{a}^{\prime }& u\\ b^{\prime }& v\end{array}\right]$, com $a^{\prime },b^{\prime },u,v\in \mathbb{N}$

Disso se conclui que

$\left[\begin{array}{c}{r}_0\\ r_1\end{array}\right]=\left[\begin{array}{c}a\\ b\end{array}\right]=\left[\begin{array}{cc}{a}^{\prime }& u\\ b^{\prime }& v\end{array}\right]\cdot \left[\begin{array}{c}d\\ 0\end{array}\right]=\left[\begin{array}{c}{a}^{\prime }d\\ b^{\prime }d\end{array}\right]$

Escrevendo $\mathrm{\Delta }=det(M)=a^{\prime }v-b^{\prime }u$, tem-se

$\mathrm{\Delta }=det(Q_0\cdot Q_1\cdot \dots \cdot Q_{k-1})=det(Q_0)\cdot det(Q_1)\cdot \dots \cdot det(Q_{k-1})=(-1{)}^k$, pois cada matriz $Q_i$ tem determinante igual a $-1$.

Logo, a matriz $M$ é invertível e $M^{-1}=\frac{1}{\mathrm{\Delta }}\left[\begin{array}{cc}v& -u\\ -b^{\prime }& a^{\prime }\end{array}\right]=\mathrm{\Delta }\left[\begin{array}{cc}v& -u\\ -b^{\prime }& a^{\prime }\end{array}\right]$. Esta última igualdade se justifica pois $\mathrm{\Delta }={\mathrm{\Delta }}^{-1}$.

Dessas considerações, resulta que:

$\left[\begin{array}{c}d\\ 0\end{array}\right]=M^{-1}\left[\begin{array}{c}a\\ b\end{array}\right]=\mathrm{\Delta }\left[\begin{array}{cc}v& -u\\ -b^{\prime }& a^{\prime }\end{array}\right]\cdot \left[\begin{array}{c}a\\ b\end{array}\right]$

Fazendo o produto, e igualando cada componente, conclui-se que:

$\{\begin{array}{ccc}d& =& a(\mathrm{\Delta }v)+b(-\mathrm{\Delta }u)\\ 0& =& \mathrm{\Delta }(-b^{\prime }a+a^{\prime }b)\end{array}$

A primeira destas equações corresponde ao teorema de Bézout, com $x=\mathrm{\Delta }v$ e $y=-\mathrm{\Delta }u$. Já a segunda, implica em $b^{\prime }a=a^{\prime }b$. Esse valor coincide com o conhecido mínimo múltiplo comum entre $a$ e $b$, definido a seguir:

Segundo o comentário que precede esta definição, tem-se:

$mmc(a,b)=\frac{ab}{(a,b)}$

Exemplificando

Anteriormente foi visto que:

$30=18\cdot \mathrm{𝟏}+12$

$18=12\cdot \mathrm{𝟏}+6$

$12=6\cdot \mathrm{𝟐}+0$

Utilizando esses valores, segue que:

$\left[\begin{array}{c}30\\ 18\end{array}\right]=\overbrace{\left[\begin{array}{cc}\mathrm{𝟏}& 1\\ 1& 0\end{array}\right]\cdot \left[\begin{array}{cc}\mathrm{𝟏}& 1\\ 1& 0\end{array}\right]\cdot \left[\begin{array}{cc}\mathrm{𝟐}& 1\\ 1& 0\end{array}\right]}\cdot \left[\begin{array}{c}6\\ 0\end{array}\right]=\left[\begin{array}{cc}5& 2\\ 3& 1\end{array}\right]\cdot \left[\begin{array}{c}6\\ 0\end{array}\right]$.

Para este exemplo, a matriz inversa é

$M^{-1}=(-1{)}^3\left[\begin{array}{cc}1& -2\\ -3& 5\end{array}\right]=\left[\begin{array}{cc}-1& 2\\ 3& -5\end{array}\right]$

Logo,

$\left[\begin{array}{c}6\\ 0\end{array}\right]=\left[\begin{array}{cc}-1& 2\\ 3& -5\end{array}\right]\cdot \left[\begin{array}{c}30\\ 18\end{array}\right]=\left[\begin{array}{cc}-1\cdot 30& 2\cdot 18\\ 3\cdot 30& -5\cdot 18\end{array}\right]$, ou seja

• $(30,18)=6=30\cdot (-1)+18\cdot 2$
• $mmc(30,18)=3\cdot 30=-5\cdot 18=90$

Note que, quando $a,b$ são positivos, a expressão $d=a(\mathrm{\Delta }v)+b(-\mathrm{\Delta }u)=ax+by$ deve ter exatamente um dos valores $x,y$ menor que zero, para que a combinação linear de $a,b$ não seja maior que qualquer um deles.

Considere uma outra situação: como encontrar o mínimo múltiplo comum entre $7$ e $5$?

Primeiramente, pelo algoritmo de Euclides tem-se:

$7=5.1+2$

$5=2.2+1$

$2=1.2+0$

Logo $mdc(7,5)=1.$

Daí tem-se que $mmc(7,5)=\frac{7\times 5}{1}=35.$

Uma demonstração alternativa do teorema de Bézout

Agora será apresentada uma prova não construtiva do teorema de Bézout. Isso significa que, embora a mesma assegure a validade do teorema, ela não fornece um método para a obtenção do MDC (ao contrário do que foi feito anteriormente).

Além disso, são utilizados alguns conceitos que certamente são conhecidos por aqueles que possuem conhecimentos básicos de álgebra. Se este não for o seu caso, você poderá pular esta seção, e não haverá prejuizo na leitura do restante deste livro. Predefinição:Demonstração

Exercícios

1. O algoritmo da divisão estabelece que dados os inteiros $a,b$, existem inteiros $q,r$ tais que $a=bq+r$, com $0\le r<b$. Utilize uma calculadora comum (e apenas as quatro operações elementares) para obter os valores de $q,r$ correspondentes a alguns pares de inteiros $a,b$.
2. Dados a e b, determine o valor de mdc(a,b) e números inteiros x, y tais que d = xa + yb, para os seguintes valores de a e b:
   1. a = 299 e b = 161
   2. a = 435 e b = 232
   3. a = 101 e b = 33
   4. a = 145 e b = 48

Ver também

Wikipedia

• Máximo divisor comum