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
podemos dizer que ![D(a,b) \subset D(b,r_1) [;D(a,b) \subset D(b,r_1);]](http://thewe.net/tex/D%28a,b%29%20%5Csubset%20D%28b,r_1%29)
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
Exemplo: Vamos calcular o
(1)
,
(2)
, ![r_2=3 [;r_2=3;]](http://thewe.net/tex/r_2=3)
Agora, para calcular
e
de forma que
fazemos
(2) ![3=27-6.4 \rightarrow d=b-6.4 [;3=27-6.4 \rightarrow d=b-6.4;]](http://thewe.net/tex/3=27-6.4%20%5Crightarrow%20d=b-6.4)
(1) ![6=60-27.2 \rightarrow 6=a-b.2 [;6=60-27.2 \rightarrow 6=a-b.2;]](http://thewe.net/tex/6=60-27.2%20%5Crightarrow%206=a-b.2)
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