quinta-feira, 16 de fevereiro de 2012

017-O Algoritmo de Euclides e a Representação Binomial do mdc(a,b)

Considere [;a \neq 0;], [;b \neq 0;], [; x;] e [;y;] todos [;\in;] [;\left{...+3,-2,-1,0,+1,+2,+3,...\right};]= [;Z;]. Foi provado no post A Combinação Linear ax+by que o resultado de [;ax+by;] é sempre um múltiplo inteiro de [;d=mdc(a,b)>0;]. Ou seja, se [;S;] representa o conjunto de todos os valores inteiros que [;ax+by;] pode assumir, então

[;S=\left{...-3d,-2d,-d,0,+d,+2d,+3d,...\right};]

Observem que o menor valor positivo do conjunto [;S;] é  [;d=mdc(a,b);]. Logo, devem existir [;s;] e [;t;] [;\in \mathbb{Z};], onde [;d=as+bt;]. Neste artigo, vamos aprender a encontrar os valores inteiros [;s;] e [;t;] que, combinados com os coeficientes inteiros [;a;] e [;b;] , representam o [;mdc(a,b);].

Inicialmente, é necessário termos um método para  calcular [;d;]. A utilização do algoritmo de Euclides, neste caso, é melhor que o método conhecido de fatoração porque, não só calcula [;mdc(a,b);] , como também nos permite achar [;s;] e [;t;].


 ( No livro [;VII;] de sua célebre obra "OS ELEMENTOS"Euclides de Alexandria [;360 a.C-295 a.C;] apresentou para a posteridade seu famoso algoritmo )

Seja calcular [;mdc(a,b);], com [;a>b;]. Se [;a;] for múltiplo de [;b;], [;mdc(a,b)=b;], caso contrário, o  algoritmo citado é utilizado tendo em vista o teorema a seguir. Dado [;k;]um inteiro não-negativo e supondo  [;r_i \neq 0;] para [;1\leq i \leq k;], procedemos

1) Divida [;a;] por [;b;] e temos um resto [;r_1;];
2) Divida [;b;] por [;r_1;] e temos um resto [;r_2;];
3) Divida [;r_1;] por [;r_2;] e temos um resto [;r_3;];
...............................................................
4)  Divida [;r_{k-1};] por [;r_k;] e temos um resto [;r_{k+1};].

Observem que, a cada passo do algoritmo, determinamos um [;r_i;] onde [;0 < r_k < r_{k-1}<...<r_1<b;]. Como não podemos continuar este processo infinitamente ( pois existe um número finito de números entre [;0;] e [;b;] ), fatalmente surgirá um resto [;r_{k+1}=0;].

TEOREMA

Se [;r_{k+1}=0;], então [;mdc(a,b)=r_k;].

Demonstração:Sejam [;q_1,q_2,...q_{k+1};] os quocientes das divisões consideradas. Sendo [;a=bq_1+r_1;] e [;a-bq_1=r_1;], conclui-se que todos os divisores comuns de [;a;] e [;b;] também dividem [;r_1;]. Designando

[;D(a,b)=;]  conjunto dos divisores comuns de [;a;] e [;b;] e
[;D(b,r_1)=;] conjunto dos divisores comuns de [;b;] e [;r_1;]

podemos dizer que [;D(a,b) \subset D(b,r_1);]

No entanto,  pela igualdade [;bq_1+r_1=a;], conclui-se também que todos os divisores comuns de [;b;]  e [;r_1;] dividem [;a;]. Analogamente [;D(b,r_1)\subset D(a,b);]. Mas sabemos que, se [;A;] e [;B;]  são conjuntos, para [;A \subset B;] e [;B\subset A;] faz-se necessário [;A=B;] , portanto [;D(a,b)=D(b,r);] e isto implica [;mdc(a,b)=mdc(b,r_1);]. Este resultado gera a cadeia de igualdade

[;mdc(a,b)=mdc(b,r_1)=mdc(r_1,r_2)=.mdc(r_2,r_3)=...=mdc(r_{k-1},r_k)=mdc(r_k,r_{k+1});]

Logo, se [;r_{k+1}=0;], temos [;mdc(a,b)=mdc(r_k,r_{k+1})=mdc(r_k,0)=r_k;]  e está provado.

Exemplo: Vamos calcular o [;mdc(60,27);].

(1)       [;60=27.2+6;],     [;r_1=6;] 
(2)        [;27=6.4+3;],      [;r_2=3;]
                            [;6=3.2+0;],     [;r_3=0;]           

[;\rightarrow d=mdc(60,27)=r_2=3;]

Agora, para calcular [;s;] e [;t;] de forma que [;mdc(60,27)=60s+27t;]  fazemos

[;d=3;], [;a=60;] e [;b=27;] ( 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) [;3=27-6.4 \rightarrow d=b-6.4;]
(1) [;6=60-27.2 \rightarrow 6=a-b.2;]

Assim, [;d=b-6.4 \Rightarrow d=b-(a-b.2).4 \Rightarrow d=a(-4)+b(9);] 

[;\rightarrow d=mdc(60,27)=3=60(-4)+27(9);] 

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.


Um comentário:

  1. Gosto muito dos artigos de ótima qualidade do seu Blog. Quando for possível dá uma passadinha para ver nosso Curso de Informática Online. Lucas

    ResponderExcluir