Considere , , e todos = . Foi provado no post A Combinação Linear ax+by que o resultado de é sempre um múltiplo inteiro de . Ou seja, se representa o conjunto de todos os valores inteiros que pode assumir, então
Observem que o menor valor positivo do conjunto é . Logo, devem existir e , onde . Neste artigo, vamos aprender a encontrar os valores inteiros e que, combinados com os coeficientes inteiros e , representam o .
Inicialmente, é necessário termos um método para calcular . A utilização do algoritmo de Euclides, neste caso, é melhor que o método conhecido de fatoração porque, não só calcula , como também nos permite achar e .
( No livro de sua célebre obra "OS ELEMENTOS", Euclides de Alexandria apresentou para a posteridade seu famoso algoritmo )
Seja calcular , com . Se for múltiplo de , , caso contrário, o algoritmo citado é utilizado tendo em vista o teorema a seguir. Dado um inteiro não-negativo e supondo para , procedemos
1) Divida por e temos um resto ;
2) Divida por e temos um resto ;
3) Divida por e temos um resto ;
...............................................................
4) Divida por e temos um resto .
Observem que, a cada passo do algoritmo, determinamos um onde . Como não podemos continuar este processo infinitamente ( pois existe um número finito de números entre e ), fatalmente surgirá um resto .
TEOREMA
Se , então .
Demonstração:Sejam os quocientes das divisões consideradas. Sendo e , conclui-se que todos os divisores comuns de e também dividem . Designando
conjunto dos divisores comuns de e e
conjunto dos divisores comuns de e
podemos dizer que
No entanto, pela igualdade , conclui-se também que todos os divisores comuns de e dividem . Analogamente . Mas sabemos que, se e são conjuntos, para e faz-se necessário , portanto e isto implica . Este resultado gera a cadeia de igualdade
Logo, se , temos e está provado.
Exemplo: Vamos calcular o .
(1) ,
(2) ,
,
Agora, para calcular e de forma que fazemos
, e ( de forma a não perder de vista os números que interessam ) e começamos a reescrever as equações acima, isolando o resto no primeiro membro, começando pela penúltima:
(2)
(1)
Assim,
Este tipo de representação é útil para resolver equações diofantinas lineares, assunto para um futuro post.
********************NOTA *********************
Em homenagem aos seguidores de ELEMENTOS DE TEIXEIRA apresentarei no próximo post a resolução do CÍRCULO REDUTOR!
Fonte do presente post: Teoria dos Números, de
Salahoddin Shokranian,
Marcus Soares,
Hemar Godinho;
Editora UNB, 1998.
Salahoddin Shokranian,
Marcus Soares,
Hemar Godinho;
Editora UNB, 1998.
Nenhum comentário:
Postar um comentário