sexta-feira, 13 de janeiro de 2012

005-A combinação linear ax + by


 
Considere [;a \neq 0;], [;b \neq 0;], [; x;] e [;y;] todos [;\in;] [;\left{...+3,-2,-1,0,+1,+2,+3,...\right};]= [;Z;], com [;|a|<|b|;].
 
Recordem que o máximo divisor comum ( MDC ) de [;a;] e [;b;], simbolizado por [;mdc(a,b)=d>0;], é o maior dos divisores comuns de [;a;] e [;b;].

Ex[;d(16)=\left{1,2,4,8,16\right};] e [;d(24)=\left{1,2,3,4,6,8,12,24\right};]

Os divisores comuns de [;16;] e [;24;] são [;\left{1,2,4,8\right};] e o maior deles é [;8;]. Logo,
[;mdc(16,24)=8;]

O que proponho é o seguinte.

DEMONSTRAR que a combinação  [;ax+by;]  é sempre múltiplo inteiro de [;mdc(a,b);].

Ou, em outras palavras, se [;mdc(a,b)=d;] , mostrar que [;ax+by=\pm nd;], para [;n \in N;].

Demonstração:  Seja [;S+;] o conjunto que contêm todos os valores não-negativos de [;F=ax+by;], ou seja, [; F \in S+;]  onde [;F \geq 0;].

[;S+ = \left{0,f,...,|a|,...|b|,...F,...\right};] 

[;0 \in S+;] para [; x=0;] e [;y=0;];  

[;|a| \in S+;]para [;|x|=1;] e [;y=0;]

 [;|b| \in S+;] para [;x=0;] e [;|y|=1;].

[;f;] é o primeiro elemento positivo de [;S+;], portanto, existem [;s;] e [;t;] [;\in Z;], tal que

[;f=as+bt>0;] 

E [;F>f;] representa qualquer outro elemento de [;S+;]:

[;F=ax+by>0;]

Se dividirmos [;F;] por [;f;] podemos ter um quociente [;q>0;] e um resto [;0 \leq r < f;].

Assim, [;F=fq + r;]

O próximo passo agora é mostrar que o resto [;r;] também [;\in S+;].  Vejamos,

[;r = F - fq;], mas [;F=ax+by;] e [;f = as + bt;] e substituindo estes valores no primeiro,

[;r=(ax+by)-(as+bt)q = ax + by -asq - btq ;] 

[;\Rightarrow r=a(x-sq) + b(y-tq);]

Desta forma, existem [;x^';] e [;y^';] [;\in Z;] onde [;r=ax^'+by^';] e conclui-se que [;r \in S+;] .

No entanto  [;0 \leq r < f;] e, por hipótese, [;f;] é o primeiro elemento positivo de [;+S;]. Logo, [;r=0;].

O fato de [;r=0;] nos traz três importantes consequências:

-  Qualquer elemento [;F;] de [;+S;] é múltiplo do primeiro elemento positivo [;f;] porque [;F=fq + r = fq + 0 = fq;];

- Como [;|a|;] e [;|b|;] [;\in;] [;S+;], eles também são múltiplos de [;f;] o que é a mesma coisa em dizer que [;f;] é um divisor comum de de [;a;] e [;b;];

- Seja [;d^'>0;] qualquer outro divisor comum de de [;a;] e [;b;]. Por

[;\frac{f}{d^'} = \frac{as+bt}{d^'} = \frac{a}{d^'}.s + \frac{b}{d^'}.t > 0;] 

concuimos que [;d^';]  divide [;f;] e  assim, [;0<d^' \leq f;], ou seja, [;f;] é maior que todos os outros divisores comuns.

Portanto, [;f=d=mdc(a,b);]

 [;F=ax+by=fq=dq \geq 0;]

Para os valores de [;F=ax+by \leq0;] a prova é trivial. Basta considerar o módulo de [;F;] .

Logo, [;ax+by=\pm nd;], para [;n \in N;].




Fonte: Teoria dos Números, de
           Salahoddin Shokranian,
           Marcus Soares,
           Hemar Godinho;
           Editora UNB, 1998.

Nenhum comentário:

Postar um comentário