Mostrar código-fonte de 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 ==

{{definição
|Um ''divisor comum'' de <math>a</math> e <math>b</math> é um número inteiro que é divisor tanto de <math>a</math> quanto de <math>b</math>.
}}

=== Exemplos ===
==== Quem são os divisores comuns de a e b? ====
O conjunto formado pelos divisores comuns de <math>a</math> e <math>b</math> será denotado por <math>D(a,b)</math>.

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

Logo, o conjunto <math>D(a,b)</math> é não vazio, pois <math>1 \in D(a,b)</math>.

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

Isso motiva a próxima definição.

=== Definição de MDC ===
{{Definição
|O ''máximo divisor comum'' (abreviadamente MDC) entre dois números inteiros <math>a</math> e <math>b</math>, em que pelo menos um deles não é zero, é o maior elemento do conjunto <math>D(a,b)</math>, e será denotado por <math>mdc(a,b)</math>, ou simplesmente <math>(a,b)</math>.
}}
{{Wikipedia|Números primos entre si}}
Quando o conjunto <math>D(a,b)</math> possui apenas um elemento positivo, ou seja, quando <math>(a,b)=1</math>, os números <math>a</math> e <math>b</math> são ditos ''primos entre si'', ''relativamente primos'' ou simplesmente ''co-primos''.

{{Tarefa| 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 [[Discussão:Teoria de números/Máximo divisor comum|discutir o assunto]].}}

==== Exemplo ====
Qual é o máximo divisor comum entre <math>12</math> e <math>15</math>?

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

Embora ainda não tenha sido explicado como encontrar o ''máximo divisor comum'' de dois números inteiros (isso será feito [[#Algoritmo de Euclides para o MDC|mais adiante]]), mostra-se que ele é um dos elementos do conjunto <math>\{ ax+by: x,y\in \mathbb{Z}\}</math>. 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 ==
{{Teorema
|Se <math>d=mdc(a,b)</math>, então existem inteiros <math>x</math> e <math>y</math> tais que <math>d=ax+by</math>.
}}
{{Wikipedia|Identidade de Bézout}}
O resultado também é conhecido como ''identidade de Bézout''.

Antes de apresentar qualquer justificativa ([[#Demonstração do teorema de Bézout|construtiva]] ou [[#Uma demonstração alternativa do teorema de Bézout|puramente algébrica]]) dessa identidade, serão mostradas suas consequências imediatas mais importantes.

=== Corolário ===
{{Corolário
|Se <math>m|ab</math> e <math>mdc(a,m)=1</math> então <math>m|b</math>.
}}
{{Demonstração
|Pelo teorema anterior, o máximo divisor comum entre <math>a</math> e <math>m</math> pode ser escrito como:
:<math>1=ax+my</math>, com <math>x</math> e <math>y</math> inteiros.

Multiplicando cada membro da equação anterior por <math>b</math>, obtem-se <math>b=(ba)x+bmy</math>.

Claramente, <math>m</math> divide cada parcela desta soma. Consequentemente deve dividir <math>b</math>.
}}
{{Wikipedia|Euclides}}
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:

=== 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 <math>a,b \in \mathbb{Z}</math> e <math>p</math> um número primo que divide o produto <math>ab</math>.

Será provado que se <math>p</math> não divide <math>a</math>, então deve necessariamente dividir <math>b</math>.

De fato, como <math>p</math> é primo, o conjunto de seus divisores é <math>D(p)=\{\pm 1,\pm p \}</math>. Além disso, <math>p\not|a</math>, logo <math>p</math> não pode ser um divisor comum de <math>a</math> e <math>b</math>.

Segue que <math>(a,b)=1</math>.

De acordo com o corolário acima, isso implica que <math>p</math> divide <math>b</math>.
}}

=== 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 <math>a,b</math>, tem-se a igualdade <math>(a,b)=(a-b,b)</math>.

De fato, para que tal propriedade se verifique, é suficiente que os conjuntos <math>D(a,b)</math> e <math>D(a-b,b)</math> 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 <math>d \in D(a,b)</math>, então <math>d|a</math> e <math>d|b</math>.

Donde, <math>d|a-b</math>.

Assim, <math>d\in D(a-b,b)</math>.

* Reciprocamente, se <math>d\in D(a-b,b)</math>, então <math>d|a-b</math> e <math>d|b</math>. Logo, deve dividir a soma:
:<math>d|(a-b)+b = a</math>,

ou seja, <math>d\in D(a,b)</math>.

Outra propriedade do máximo divisor comum é a seguinte:
:<math>(b,a) = (a,b) = (-a,b) = (a,-b)</math>

Por causa dela, pode ser suposto que <math>a\ge b\ge 0</math>, e obter a demonstração:
{{Demonstração
|A prova será feita por indução em <math>a+b</math>.

Obviamente, se <math>a+b = 0</math>, tem-se <math>a=b=0</math>, e a propriedade é válida pois sempre que <math>b=0</math> tem-se:
:<math>(a,b) = (a,0) = a = a\cdot 1 + b\cdot 0</math>

Logo, pode ser suposto que <math>b>0</math> (e portanto, <math>a+b > 0</math>).

Será tomada como hipótese de indução que: ''os pares de números inteiros <math>m,n</math>, cuja soma seja menor que <math>a+b</math>, têm <math>(m,n) = mx+ny</math>.

Como <math>(a,b) = (a-b,b)</math>, e <math>a-b</math> somado com <math>b</math> é menor que <math>a+b</math>, a hipótese de indução garante que <math>(a-b,b) = (a-b)u + bv</math>. Então:
:<math>(a,b) = (a-b)u+bv = au + b(v-u)</math>
}}
{{Wikipedia|Algoritmo}}
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 <math>(a,b)</math>:

 '''Dados de entrada'''
   Os inteiros <math>a</math> e <math>b</math>.
 
 '''Saída'''
   <math>(a,b)</math>.
 
 '''Procedimento'''
 * Se <math>a<b</math>, então <math>(a,b) = (b,a)</math>;
 * Se <math>b=0</math>, então <math>(a,b) = a</math>;
 * Senão <math>(a,b) = (a-b,b)</math>

=== Exemplos numéricos ===
Usando o procedimento sugerido, pode-se calcular <math>(30,18)</math> facilmente. Acompanhe:
:<math>(30,18) = (12,18) = (18,12) = (6,12) = (6,6) = (0,6) = (6,0) = 6 </math>

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

Por exemplo, se <math>a=100</math> e <math>b=3</math> as etapas serão:

:<math>(100,3) = (97,3) = (94,3) = \ldots = (4,3) = (1,3)</math> <math>= (3,1) = (2,1) = (1,1) = (0,1) = (1,0) = 1</math>

Neste caso, parece razoável subtrair <math>3</math> de <math>100</math> tantas vezes quanto for possível, em uma única etapa:
:<math>(100,3) = (100-3\cdot 33,3) = (1,3) = 1</math>

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

A existência de um número <math>q</math>, satisfazendo ambas as desigualdades é garantida pelo ''[[Teoria de números/Divisibilidade#Algoritmo da divisão (de Euclides)|algoritmo da divisão]]'' apresentado em um capítulo anterior. Se precisar relembrar os detalhes, consulte a seção "[[Teoria de números/Divisibilidade#Algoritmo da divisão (de Euclides)|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 ==
{{Tarefa|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 [[Teoria de números/Bibliografia|Bibliografia]]}}

{{Teorema
|Dados <math>a,b \in \mathbb{Z}</math>, com <math>a\ge b\ge 0</math>, verifique se <math>b=0</math>. Em caso afirmativo, o máximo divisor comum é o próprio <math>a</math>. Caso contrário, repita o processo usando <math>b</math> e o resto da divisão de <math>a</math> por <math>b</math>. Simbolicamente:
 '''Dados de entrada'''
   Os inteiros <math>a</math> e <math>b</math>.
 
 '''Saída'''
   <math>(a,b)</math>.
 
 '''Procedimento'''
 * Se <math>a<b</math>, então <math>(a,b) = (b,a)</math>;
 * Se <math>b=0</math>, então <math>(a,b) = a</math>;
 * Senão <math>(a,b) = (a-bq,b)</math>, onde <math>0 \le a-bq<b</math>

}}

Observe que esta é simplesmente uma generalização do algoritmo apresentado logo após a [[#Demonstração do teorema de Bézout|demonstração do teorema de Bézout]].
{{Wikipedia|Algoritmo de Euclides}}
É preciso verificar que <u>o algoritmo irá parar</u>, e ainda mais importante, que <u>fornecerá a resposta correta</u>.
{{Demonstração/Início}}
Considere <math>r_0 = a</math> e <math>r_1 = b</math>, e a seguinte sequência de igualdades (obtidas pelo [[Teoria de números/Divisibilidade#Algoritmo da divisão (de Euclides)|algoritmo da divisão]]):

:{| cellpadding=0px cellspacing=6px
|-
|align=right| <math>r_0 =</math> || width=150px | <math>r_1q_0+r_2</math> || <math>0 \le r_2<r_1</math>
|-
|align=right| <math>r_1 =</math> || <math>r_2q_1+r_3</math> || <math>0 \le r_3<r_2</math>
|-
|align=right| <math>\vdots</math> ||  || 
|-
|align=right| <math>r_{k-2} =</math> || <math>r_{k-1}q_{k-2}+r_{k}</math> || <math>0 \le r_{k}<r_{k-1}</math>
|-
|align=right| <math>r_{k-1} =</math> || <math>r_{k}q_{k-1}+r_{k+1}</math> || <math>0 \le r_{k+1}<r_{k}</math>
|-
|align=right| <math>\vdots</math> ||  || 
|}

Juntando as desigualdades anteriores, tem-se uma sequência decrescente de números não negativos:
:<math>r_1>r_2>r_3>\ldots >r_k>\ldots \ge 0</math>

No entanto, só existe uma quantidade finita de números positivos menores que <math>r_1</math>. Logo, depois de algum resto <math>r_k</math>, tem-se <math>r_{k+1} = 0</math>, ou seja:
:<math>r_1>r_2>r_3>\ldots >\mathbf{r_k}>r_{k+1}=0</math>

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

Será que este é realmente o valor de <math>(a,b)</math>?

A resposta é sim, pois <math>(a,b) = (a-b,b) = (a-2b,b) = (a-3b,b) = \ldots = (a-bq,b)</math>.

Logo, obtem-se sucessivamente:
:<math>(a,b) = (r_0, r_1) = (r_1, r_2) = \ldots = (\mathbf{r_k},r_{k+1}) = (\mathbf{r_k},0) = \mathbf{r_k}</math>

Portanto o valor fornecido pelo algoritmo corresponde a <math>(a,b)</math>, e foi obtido através de exatamente <math>k</math> divisões.
{{Demonstração/Fim}}

=== Exemplo numérico ===
Quanto é <math>(30,18)</math>?

Aplicando o processo usado na demonstração do algoritmo de Euclides para o MDC, tem-se:
:<math>30 = 18\cdot 1 + 12</math>
:<math>18 = 12\cdot 1 + \mathbf{6}</math>
:<math>12 = \mathbf{6}\cdot 2 + 0</math>

Logo, <math>(30,18) = 6</math>.

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:

:{| class="wikitable" style="text-align:center"
|-
! quociente
|width="40px"| 1 ||width="40px"| 1 ||width="40px"| 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 [http://www.math.sc.edu/~sumner/numbertheory/euclidean/euclidean.html 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:
:<math>r_{j-1} = r_{j}q_{j-1}+r_{j+1}</math>
O índice <math>j</math> indica que esta é a <math>j</math>-ésima divisão efetuada no algoritmo.

Cada uma dessas equações é uma [[w:equação de diferenças|equação de diferenças]] de <u>segunda ordem</u>, em que cada termo é descrito em função de <u>dois</u> 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:
:<math>\begin{bmatrix} r_{j-1} \\ r_{j} \end{bmatrix} = \begin{bmatrix} q_{j-1} & 1\\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} r_{j} \\ r_{j+1} \end{bmatrix}</math>, sempre que <math>1\le j \le k</math>

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

:{| cellpadding=0px cellspacing=6px
|-
| align=right | <math>\begin{bmatrix} r_0 \\ r_1 \end{bmatrix}</math>
| <math>= \begin{bmatrix} q_0 & 1\\ 1 & 0 \end{bmatrix}\cdot \begin{bmatrix} r_1 \\ r_2 \end{bmatrix}</math>
|-
|
| <math>= \begin{bmatrix} q_0 & 1\\ 1 & 0 \end{bmatrix}\cdot \overbrace{ \begin{bmatrix} q_1 & 1\\ 1 & 0 \end{bmatrix}\cdot \begin{bmatrix} r_2 \\ r_3 \end{bmatrix} }</math>
|-
|
| <math>= \begin{bmatrix} q_0 & 1\\ 1 & 0 \end{bmatrix}\cdot \begin{bmatrix} q_1 & 1\\ 1 & 0 \end{bmatrix}\cdot \overbrace{ \begin{bmatrix} q_2 & 1\\ 1 & 0 \end{bmatrix}\cdot \begin{bmatrix} r_3 \\ r_4 \end{bmatrix} } </math>
|}

Para facilitar ainda mais a escrita, pode-se adotar a seguinte convenção:
:<math>Q_j = \begin{bmatrix} q_j & 1\\ 1 & 0 \end{bmatrix}</math>

Se o cálculo anterior for efetuado para todas as etapas do algoritmo, o resultado final será:
:<math>\begin{bmatrix} r_0 \\ r_1 \end{bmatrix} = Q_0 \cdot Q_1 \cdot \ldots \cdot Q_{k-1} \cdot \begin{bmatrix} d \\ 0 \end{bmatrix} = M \cdot \begin{bmatrix} d \\ 0 \end{bmatrix}</math>, sendo que <math>d=(a,b)</math>.

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

Como a matriz <math>M</math> é um produto de matrizes com entradas inteiras e não-negativas, nenhuma de suas entradas deverá ser negativa. Assim, é possível escrever <math>M</math> da seguinte forma:
:<math>M = \begin{bmatrix} a' & u\\ b' & v \end{bmatrix}</math>, com <math>a',b',u,v \in \mathbb{N}</math>
Disso se conclui que
:<math>\begin{bmatrix} r_0 \\ r_1 \end{bmatrix} = \begin{bmatrix} a \\ b \end{bmatrix} = \begin{bmatrix} a' & u\\ b' & v \end{bmatrix} \cdot \begin{bmatrix} d \\ 0 \end{bmatrix} = \begin{bmatrix} a'd \\ b'd \end{bmatrix}</math>

Escrevendo <math>\Delta = det(M) = a'v-b'u</math>, tem-se
:<math>\Delta = det(Q_0 \cdot Q_1 \cdot \ldots \cdot Q_{k-1}) = det(Q_0) \cdot det(Q_1) \cdot \ldots \cdot det(Q_{k-1}) = (-1)^{k}</math>, pois cada matriz <math>Q_i</math> tem determinante igual a <math>-1</math>.

Logo, a matriz <math>M</math> é invertível e <math>M^{-1} = \frac{1}{\Delta}\begin{bmatrix} v & -u\\ -b' & a' \end{bmatrix} = \Delta\begin{bmatrix} v & -u\\ -b' & a' \end{bmatrix}</math>. Esta última igualdade se justifica pois <math>\Delta = \Delta^{-1}</math>.

Dessas considerações, resulta que:
:<math>\begin{bmatrix} d \\ 0 \end{bmatrix} = M^{-1}\begin{bmatrix} a \\ b \end{bmatrix} = \Delta\begin{bmatrix} v & -u\\ -b' & a' \end{bmatrix}\cdot\begin{bmatrix} a \\ b \end{bmatrix}</math>

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

<math>\left\{\begin{matrix}
d & = & a(\Delta v)+b(-\Delta u)\\
0 & = & \Delta(-b'a+a'b)\\
\end{matrix}\right.</math>

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

{{Definição
|O ''mínimo múltiplo comum'' dos inteiros <math>a</math> e <math>b</math>, <math>mmc(a,b)</math>, é o menor elemento positivo do conjunto <math>M(a,b) = \{ x \in \mathbb{Z}: a,b | x\}</math>
}}

Segundo o comentário que precede esta definição, tem-se:
:<math>mmc(a,b) = \frac{ab}{(a,b)}</math>
{{Justificativa}}

==== Exemplificando ====

Anteriormente foi visto que:
:<math>30 = 18\cdot \mathbf{1} + 12</math>
:<math>18 = 12\cdot \mathbf{1} + 6</math>
:<math>12 = 6\cdot \mathbf{2} + 0</math>
Utilizando esses valores, segue que:
:<math>\begin{bmatrix} 30 \\ 18 \end{bmatrix} = \overbrace{ \begin{bmatrix} \mathbf{1} & 1\\ 1 & 0 \end{bmatrix}\cdot \begin{bmatrix} \mathbf{1} & 1\\ 1 & 0 \end{bmatrix}\cdot \begin{bmatrix} \mathbf{2} & 1\\ 1 & 0 \end{bmatrix} } \cdot \begin{bmatrix} 6 \\ 0 \end{bmatrix} = \begin{bmatrix} 5 & 2\\ 3 & 1 \end{bmatrix} \cdot \begin{bmatrix} 6 \\ 0 \end{bmatrix}</math>.

Para este exemplo, a matriz inversa é
:<math>M^{-1} = (-1)^{3}\begin{bmatrix} 1 & -2\\ -3 & 5 \end{bmatrix} = \begin{bmatrix} -1 & 2\\ 3 & -5 \end{bmatrix}</math>

Logo, 
:<math>\begin{bmatrix} 6 \\ 0 \end{bmatrix} = \begin{bmatrix} -1 & 2\\ 3 & -5 \end{bmatrix} \cdot \begin{bmatrix} 30 \\ 18 \end{bmatrix} = \begin{bmatrix} -1\cdot 30 & 2\cdot 18\\ 3\cdot 30 & -5\cdot 18 \end{bmatrix}</math>, ou seja

* <math>(30,18) = 6 = 30\cdot(-1) + 18\cdot 2</math>
* <math>mmc(30,18) = 3\cdot 30 = -5\cdot 18 = 90</math>

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

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

Primeiramente, pelo algoritmo de Euclides tem-se:
:<math>7= 5.1 + 2</math>
:<math>5= 2.2 + 1</math>
:<math>2= 1.2 + 0</math>

Logo <math>mdc(7,5) = 1.</math>

Daí tem-se que <math>\textstyle mmc(7, 5)= \frac{7 \times 5}{1} = 35.</math>

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

Agora será apresentada uma prova não construtiva do [[#Teorema de Bézout|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 <math>a,b</math> números inteiros, considere <math>J=\{ ax+by: x,y \in \mathbb{Z}\}</math>.
Então, <math>J</math> é um subgrupo aditivo de <math>\mathbb{Z}</math> (um ideal), ou seja, <math>J</math> possui as seguintes propriedades:
# <math>0 \in J</math>;
# Dados <math>z, z' \in J</math>, tem-se <math>z+z'J</math>.

De fato, se <math>z, z' \in J</math> então:
* <math>z = ax + by</math>
* <math>z' = ax' + by'</math>
com <math>x,x',y,y' \in \mathbb{Z}</math>. Então:
:<math>z +z'= (ax + by) + (ax' + by') = a(x+x') + b(y+y') \in J</math>

Mas todo subgrupo (aditivo?) de <math>\mathbb{Z}</math> é escrito como <math>J = m\mathbb{Z} = \{ 0, \pm m,\pm 2m, \pm 3m,\ldots \}</math>, com <math>m\ge 0</math>, pois:

:Se <math>J</math> é subgrupo de <math>\mathbb{Z}</math>, então <math>J</math> possui elementos não-negativos. Em particular, <math>J</math> possui um ''menor elemento'' não-negativo <math>m</math>.
:Se <math>z \in J</math> então pelo [[Teoria de números/Divisibilidade#Algoritmo da divisão (de Euclides)|algoritmo de divisão]], <math>z = mq+r</math>, com <math>0\le r<m</math>.
:Donde <math>r = z- mq \in J</math>.
:Como <math>0\le r<m</math>, segue que <math>r = 0</math>, ou seja, <math>z = mq \in \mathbb{Z}</math>.

Para provar que se tem <math>m=(a,b)</math>, escreva <math>m=ax_0+by_0</math> (isso é possível, já que <math>m \in J</math>).

Observe que:
* <math>a=a\cdot1+b\cdot0</math>
* <math>b=a\cdot0+b\cdot1</math>
Então, tem-se <math>a,b \in J = m\mathbb{Z}</math>, ou seja, <math>m</math> é divisor de <math>a,b</math>.

Mas <math>m</math> é o maior divisor porque, dado qualquer outro divisor <math>\delta \in D(a,b)</math>, tem-se <math>\delta | ax_0 + by_0 = m</math>

Logo, <math>|\delta| \le |m|</math>, ou seja, <math>m = (a,b)</math>.
}}

== Exercícios ==
# O [[Teoria de números/Divisibilidade#Algoritmo da divisão (de Euclides)|algoritmo da divisão]] estabelece que dados os inteiros <math>a,b</math>, existem inteiros <math>q, r</math> tais que <math>a = bq + r</math>, com <math>0\le r<b</math>. Utilize uma calculadora comum (e apenas as quatro operações elementares) para obter os valores de <math>q, r</math> correspondentes a alguns pares de inteiros <math>a,b</math>.
# 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'':
## a = 299 e b = 161
## a = 435 e b = 232
## a = 101 e b = 33
## a = 145 e b = 48

== Ver também ==
=== Wikipedia ===
* [http://pt.wikipedia.org/wiki/M%C3%A1ximo_divisor_comum Máximo divisor comum]

{{AutoCat}}