Saltar para o conteúdo

Teoria de números/Máximo divisor comum

Origem: Wikilivros, livros abertos por um mundo aberto.


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 | editar código-fonte]
Definição

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

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

[editar | editar código-fonte]

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 | editar código-fonte]

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 | editar código-fonte]
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
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.

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 | editar código-fonte]
Teorema

Se , então existem inteiros e tais que .

Wikipedia
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

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
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 | editar código-fonte]
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 | editar código-fonte]

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
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 | editar código-fonte]

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 | editar código-fonte]
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
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 | editar código-fonte]

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 | editar código-fonte]

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 | editar código-fonte]

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 | editar código-fonte]

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

  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