Teoria de números/Máximo divisor comum


No capítulo anterior, foi demonstrado o 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

editar
Definição

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

Exemplos

editar

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

editar

O conjunto formado pelos divisores comuns de   e   será denotado por  .

No primeiro capítulo, mostrou-se que o número   é divisor de qualquer número inteiro. Em particular, se forem escolhidos números   e  , certamente   será um divisor comum de ambos.

Logo, o conjunto   é não vazio, pois  .

O maior dos divisores comuns

editar

Se   e   for um divisor comum de   e de  , então  . Logo o conjunto   é limitado superiormente e deve ter um elemento máximo, ou seja, existe um divisor comum de   e   maior que todos os demais. Analogamente, para  , o conjunto   também tem um elemento máximo. O único caso que   não é limitado superiormente é o conjunto  , já que zero é múltiplo de qualquer inteiro não-nulo.

Isso motiva a próxima definição.

Definição de MDC

editar
Definição

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

 
Wikipedia
A Wikipédia tem mais sobre este assunto:
Números primos entre si

Quando o conjunto   possui apenas um elemento positivo, ou seja, quando  , os números   e   são ditos primos entre si, relativamente primos ou simplesmente co-primos.


  Este módulo 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.

Exemplo

editar

Qual é o máximo divisor comum entre   e  ?

Considerando que os divisores de   são os elementos do conjunto   e que os divisores de   formam o conjunto  , tem-se que  , cujo maior elemento é  . Portanto,  .

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

editar
Teorema

Se  , então existem inteiros   e   tais que  .

 
Wikipedia
A Wikipédia tem mais sobre este assunto:
Identidade de Bézout

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

editar
Corolário

Se   e   então  .

Demonstração
Pelo teorema anterior, o máximo divisor comum entre   e   pode ser escrito como:
 , com   e   inteiros.

Multiplicando cada membro da equação anterior por  , obtem-se  .

Claramente,   divide cada parcela desta soma. Consequentemente deve dividir  .

 
Wikipedia
A Wikipédia tem mais sobre este assunto:
Euclides

Com essa propriedade, devida a Euclides de Alexandria, já é possível demonstrar o teorema que ficou pendente no capítulo anterior:

Propriedade fundamental dos primos

editar
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   e   um número primo que divide o produto  .

Será provado que se   não divide  , então deve necessariamente dividir  .

De fato, como   é primo, o conjunto de seus divisores é  . Além disso,  , logo   não pode ser um divisor comum de   e  .

Segue que  .

De acordo com o corolário acima, isso implica que   divide  .

Demonstração do teorema de Bézout

editar

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

De fato, para que tal propriedade se verifique, é suficiente que os conjuntos   e   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  , então   e  .

Donde,  .

Assim,  .

  • Reciprocamente, se  , então   e  . Logo, deve dividir a soma:
 ,

ou seja,  .

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

 

Por causa dela, pode ser suposto que  , e obter a demonstração:

Demonstração
A prova será feita por indução em  .

Obviamente, se  , tem-se  , e a propriedade é válida pois sempre que   tem-se:

 

Logo, pode ser suposto que   (e portanto,  ).

Será tomada como hipótese de indução que: os pares de números inteiros  , cuja soma seja menor que  , têm  .

Como  , e   somado com   é menor que  , a hipótese de indução garante que  . Então:

 
 
Wikipedia
A Wikipédia tem mais sobre este assunto:
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  :

Dados de entrada
  Os inteiros   e  .

Saída
   .

Procedimento
* Se  , então  ;
* Se  , então  ;
* Senão  

Exemplos numéricos

editar

Usando o procedimento sugerido, pode-se calcular   facilmente. Acompanhe:

 

No entanto, quando se tem   bem maior que  , a igualdade mais utilizada será  .

Por exemplo, se   e   as etapas serão:

   

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

 

Em geral, será buscado um valor   tal que  , pois assim a igualdade   (que é sempre verdadeira, para qualquer valor inteiro de  ) reduz o cálculo de   a um caso bem mais simples.

A existência de um número  , 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

editar
  Este módulo 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  , com  , verifique se  . Em caso afirmativo, o máximo divisor comum é o próprio  . Caso contrário, repita o processo usando   e o resto da divisão de   por  . Simbolicamente: Dados de entrada Os inteiros   e  . Saída  . Procedimento * Se  , então  ; * Se  , então  ; * Senão  , onde  

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

 
Wikipedia
A Wikipédia tem mais sobre este assunto:
Algoritmo de Euclides

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

Considere   e  , e a seguinte sequência de igualdades (obtidas pelo algoritmo da divisão):

     
     
 
     
     
 

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

 

No entanto, só existe uma quantidade finita de números positivos menores que  . Logo, depois de algum resto  , tem-se  , ou seja:

 

É nesse ponto que o algoritmo para: quando o resto  . Segundo o enunciado, o resultado fornecido será então  .

Será que este é realmente o valor de  ?

A resposta é sim, pois  .

Logo, obtem-se sucessivamente:

 

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

Exemplo numérico

editar

Quanto é  ?

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

 
 
 

Logo,  .

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

editar

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

 

O índice   indica que esta é a  -é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:

 , sempre que  

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

   
 
 

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

 

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

 , sendo que  .

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

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

 , com  

Disso se conclui que

 

Escrevendo  , tem-se

 , pois cada matriz   tem determinante igual a  .

Logo, a matriz   é invertível e  . Esta última igualdade se justifica pois  .

Dessas considerações, resulta que:

 

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

 

A primeira destas equações corresponde ao teorema de Bézout, com   e  . Já a segunda, implica em  . Esse valor coincide com o conhecido mínimo múltiplo comum entre   e  , definido a seguir:

Definição

O mínimo múltiplo comum dos inteiros   e  ,  , é o menor elemento positivo do conjunto  

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

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

Exemplificando

editar

Anteriormente foi visto que:

 
 
 

Utilizando esses valores, segue que:

 .

Para este exemplo, a matriz inversa é

 

Logo,

 , ou seja
  •  
  •  

Note que, quando   são positivos, a expressão   deve ter exatamente um dos valores   menor que zero, para que a combinação linear de   não seja maior que qualquer um deles.

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

Primeiramente, pelo algoritmo de Euclides tem-se:

 
 
 

Logo  

Daí tem-se que  

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

editar

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   números inteiros, considere  .

Então,   é um subgrupo aditivo de   (um ideal), ou seja,   possui as seguintes propriedades:

  1.  ;
  2. Dados  , tem-se  .

De fato, se   então:

  •  
  •  

com  . Então:

 

Mas todo subgrupo (aditivo?) de   é escrito como  , com  , pois:

Se   é subgrupo de  , então   possui elementos não-negativos. Em particular,   possui um menor elemento não-negativo  .
Se   então pelo algoritmo de divisão,  , com  .
Donde  .
Como  , segue que  , ou seja,  .

Para provar que se tem  , escreva   (isso é possível, já que  ).

Observe que:

  •  
  •  

Então, tem-se  , ou seja,   é divisor de  .

Mas   é o maior divisor porque, dado qualquer outro divisor  , tem-se  

Logo,  , ou seja,  .

Exercícios

editar
  1. O algoritmo da divisão estabelece que dados os inteiros  , existem inteiros   tais que  , com  . Utilize uma calculadora comum (e apenas as quatro operações elementares) para obter os valores de   correspondentes a alguns pares de inteiros  .
  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

editar

Wikipedia

editar