Exemplos

Determine o menor inteiro positivo que deixa resto 1 na divisão por 3 e resto 2 na divisão por 5

Questão simples, dá para fazer de cabeça, o número pedido é 7, porém que tal encontrarmos  todas as soluções para esse problema.

É pedido um número n que tem as formas:

n = 3q + 1

n = 5q’ + 2

ou podemos dizer que:

n = 1 (mod 3)

n = 2 (mod 5 )

como as congruencias tem módulos diferentes, não podemos fazer uma manipulação direta, então vamos substituir n = 5q’  + 2 na primeira congruência:

n = 1 (mod 3)

5q’ + 2 = 1 (mod 3)

como  5 = 2 (mod 3 ) podemos dizer que;

2q’ + 2 = 1 (mod 3 ) subtraindo 2

2q’ = – 1 (mod 3)

E, – 1 = 2 (mod 3 )

2q’ = 2 (mod 3)

Pelo teorema da inversão se a, não tem fator comum em n, então podemos utilizar a lei do cancelamento.

q’ = 1 (mod 3)

é o mesmo que dizer:

q’ = 3q” + 1

temos outra equação, podemos portante substituir q’ em n = 5q’ + 2

n = 5(3q” + 1) + 2

n = 15q” + 7

Observamos que esse valor, tem algo familiar.

n = 5(3q” + 1) + 2  ou seja,  na divisao por 5 deixa resto 2, e;

n = 3(5q” + 2) + 1 na divisão por 3 deixa resto 1.

Então a solução procurada é n = 15q” + 7


Observamos que, o menor valor inteiro positivo ocorre quando q” = 0, e será 7 como tinhamos encontrado no inicio.

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: