Teorema do resto Chinês

Sejam m e n inteiros positivos primos entre si. Se a e b são inteiros quaisquer, então o sistema:

x = a (mod m)

x = b (mod n)

Sempre tem solução e qualquer uma de suas soluções pode ser escrita na forma

a + m.( m’.(b – a) + n.t)

onde t é um inteiro qualquer, e m’ é o inverso de m módulo n

Demonstrando o teorema:

Considerando o sistema;

x = a (mod m)

x = b ( mod n)

Como os módulos são diferentes, temos que fazer uma combinação através de suas formas por igualdade.

x = m.k + a

x = m.k’ + b

Agora substituimos na congruencia:

m.k + a = b (mod n)

m.k = (b – a) ( mod n)

Sendo m.m’ = 1 (mod n)  ou seja, m’ é o inverso de m então:

k = m'(b – a) ( mod n)

Chegamos a isolar o k, passando para sua forma de igualdade:

k = m'(b-a) + n . t

substituindo k na sua equação original:

x = m.(m'(b-a) + n.t) + a

[  ]c.q.d

Deixe uma resposta

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s

%d blogueiros gostam disto: