Teoria de números/Máximo divisor comum

• Ver como deveria funcionar a predefinição em: http://pt.wikibooks.org/wiki/Teoria_de_n%C3%BAmeros/M%C3%A1ximo_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.

1 Divisores comuns

Definição

Um divisor comum de $a$ e $b$ é um número inteiro que é divisor tanto de $a$ quanto de $b$.

1.1 Exemplos

1.1.1 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)$.

1.1.2 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.

1.2 Definição de MDC

Definição

O máximo divisor comum (abreviadamente MDC) entre dois números inteiros $a$ e $b$, em que pelo menos um deles não é zero, é o maior elemento do conjunto $D(a,b)$, e será denotado por $mdc(a,b)$, ou simplesmente $(a,b)$.

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.

Este livro tem a seguinte tarefa pendente: Unificar a notação utilizada ao longo do livro para denotar o MDC. Pode ser mais adequado utilizar sempre mdc(a,b), em vez de (a,b), para evitar confusões. Em caso de dúvida, pode-se discutir o assunto.

1.2.1 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{\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:

2 Teorema de Bézout

Teorema

Se $d=mdc(a,b)$, então existem inteiros $x$ e $y$ tais que $d=ax+by$.

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.

2.1 Corolário

Corolário

Se $m|ab$ e $(a,m)=1$ então $m|b$.

Demonstração
Pelo teorema anterior, o máximo divisor comum entre $a$ e $m$ pode ser escrito como: $1=ax+my$, com $x$ e $y$ inteiros. Multiplicando cada membro da equação anterior por $b$, obtem-se $b=(ba)x+bmy$. Claramente, $m$ divide cada parcela desta soma. Consequentemente deve dividir $b$.

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:

2.2 Propriedade fundamental dos primos

Teorema

Se um número primo divide o produto de dois números inteiros, então ele é divisor de um dos dois.

Demonstração

Sejam $a,b\in \mathbb{\mathbb{Z}}$ e $p$ um número primo que divide o produto $ab$. Será provado que se $p$ não divide $a$, então deve necessariamente dividir $b$. De fato, como $p$ é primo, o conjunto de seus divisores é $D(p)=\{\pm 1,\pm p\}$. Além disso, $p|a$, logo $p$ não pode ser um divisor comum de $a$ e $b$. Segue que $(a,b)=1$. De acordo com o corolário acima, isso implica que $p$ divide $b$.

2.3 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:

Demonstração

A prova será feita por indução em $a+b$. Obviamente, se $a+b=0$, tem-se $a=b=0$, e a propriedade é válida pois sempre que $b=0$ tem-se: $(a,b)=(a,0)=a=a\cdot 1+b\cdot 0$ Logo, pode ser suposto que $b>0$ (e portanto, $a+b>0$). Será tomada como hipótese de indução que: os pares de números inteiros $m,n$, cuja soma seja menor que $a+b$, têm $(m,n)=mx+ny$. Como $(a,b)=(a-b,b)$, e $a-b$ somado com $b$ é menor que $a+b$, a hipótese de indução garante que $(a-b,b)=(a-b)u+bv$. Então: $(a,b)=(a-b)u+bv=au+b(v-u)$

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)$

2.4 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.

3 Algoritmo de Euclides para o MDC

Este livro tem a seguinte tarefa pendente: Adicionar informações históricas sobre o algoritmo e também uma referência às aplicações atuais em música, descrita nos artigos do Brun, e do Toussaint. Consulte a Bibliografia

Teorema

Dados $a,b\in \mathbb{\mathbb{Z}}$, com $a\ge b\ge 0$, verifique se $b=0$. Em caso afirmativo, o máximo divisor comum é o próprio $a$. Caso contrário, repita o processo usando $b$ e o resto da divisão de $a$ por $b$. Simbolicamente: 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-bq,b)$, onde $0\le a-bq<b$

Observe que esta é simplesmente uma generalização do algoritmo apresentado logo após a demonstração do teorema de Bézout.

É preciso verificar que o algoritmo irá parar, e ainda mais importante, que fornecerá a resposta correta.

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 >{\mathbf{r}}_{\mathbf{𝐤}}>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 =({\mathbf{r}}_{\mathbf{𝐤}},r_{k+1})=({\mathbf{r}}_{\mathbf{𝐤}},0)={\mathbf{r}}_{\mathbf{𝐤}}$

Portanto o valor fornecido pelo algoritmo corresponde a $(a,b)$, e foi obtido através de exatamente $k$ divisões.

3.1 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+\mathbf{𝟔}$

$12=\mathbf{𝟔}\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.

3.2 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{\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:

Definição

O mínimo múltiplo comum dos inteiros $a$ e $b$, $mmc(a,b)$, é o menor elemento positivo do conjunto $M(a,b)=\{x\in \mathbb{\mathbb{Z}}:a,b|x\}$

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

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

Justificativa
Fica a cargo do leitor justificar este fato. Sinta-se livre para melhorar a qualidade deste texto, incluindo a justificativa neste módulo.

3.2.1 Exemplificando

Anteriormente foi visto que:

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

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

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

Utilizando esses valores, segue que:

$\left[\begin{array}{c}30\\ 18\end{array}\right]=\overbrace{\left[\begin{array}{cc}\mathbf{𝟏}& 1\\ 1& 0\end{array}\right]\cdot \left[\begin{array}{cc}\mathbf{𝟏}& 1\\ 1& 0\end{array}\right]\cdot \left[\begin{array}{cc}\mathbf{𝟐}& 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.$

4 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.

Demonstração

Sendo $a,b$ números inteiros, considere $J=\{ax+by:x,y\in \mathbb{\mathbb{Z}}\}$. Então, $J$ é um subgrupo aditivo de $\mathbb{\mathbb{Z}}$ (um ideal), ou seja, $J$ possui as seguintes propriedades: $0\in J$; Dados $z,z^{\prime }\in J$, tem-se $z+z^{\prime }J$. De fato, se $z,z^{\prime }\in J$ então: $z=ax+by$ $z^{\prime }=a{x}^{\prime }+b{y}^{\prime }$ com $x,x^{\prime },y,y^{\prime }\in \mathbb{\mathbb{Z}}$. Então: $z+z^{\prime }=(ax+by)+(a{x}^{\prime }+b{y}^{\prime })=a(x+x^{\prime })+b(y+y^{\prime })\in J$ Mas todo subgrupo (aditivo?) de $\mathbb{\mathbb{Z}}$ é escrito como $J=m\mathbb{\mathbb{Z}}=\{0,\pm m,\pm 2m,\pm 3m,\dots \}$, com $m\ge 0$, pois: Se $J$ é subgrupo de $\mathbb{\mathbb{Z}}$, então $J$ possui elementos não-negativos. Em particular, $J$ possui um menor elemento não-negativo $m$. Se $z\in J$ então pelo algoritmo de divisão, $z=mq+r$, com $0\le r<m$. Donde $r=z-mq\in J$. Como $0\le r<m$, segue que $r=0$, ou seja, $z=mq\in \mathbb{\mathbb{Z}}$. Para provar que se tem $m=(a,b)$, escreva $m=a{x}_0+b{y}_0$ (isso é possível, já que $m\in J$). Observe que: $a=a\cdot 1+b\cdot 0$ $b=a\cdot 0+b\cdot 1$ Então, tem-se $a,b\in J=m\mathbb{\mathbb{Z}}$, ou seja, $m$ é divisor de $a,b$. Mas $m$ é o maior divisor porque, dado qualquer outro divisor $\delta \in D(a,b)$, tem-se $\delta |a{x}_0+b{y}_0=m$ Logo, $|\delta |\le |m|$, ou seja, $m=(a,b)$.

5 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

6 Ver também

6.1 Wikipedia

• Máximo divisor comum