FANDOM


Sistemas Completos de Resíduos Editar

Os números $ a_1,a_2,\dots,a_n $ formam um sistema completo de resíduos (s.c.r) módulo $ n $ se os seus restos da divisão por $ n $ forem, em alguma ordem, $ 0,1,2,\dots,n-1 $.

Exemplo (Cone Sul 1999) Editar

Seja $ A $ um número de seis algarismos, três dos quais estão coloridos e são iguais a $ 1,2 $ e $ 4 $. Demonstrar que é sempre possível obter um número que é múltiplo de $ 7 $, efetuando uma só das seguintes operações: ou suprimir os três algarismos coloridos, ou escrever todos os algarismos em alguma ordem.

Solução: Considere $ C $ o número que queremos obter a partir de $ A $. Para nos ajudar, consideraremos $ B $ o número de três algarismos obtido a partir de $ A $ apagando os algarismos coloridos $ 1,2 $ e $ 4 $.

Se $ B $ for múltiplo de $ 7 $, então basta apagarmos os algarismos $ 1,2 $ e $ 4 $ de $ A $ para obtermos um múltiplo de $ 7 $.

E se $ B $ não for um múltiplo de $ 7 $? Mostremos que podemos colocar os algarismos $ 1,2 $ e $ 4 $ em alguma outra ordem para obtermos um múltiplo de $ 7 $. Este será o nosso $ C $.

A vantagem aqui é que $ 0,124,142,214,241,412,421 $ é um sistema completo de resíduos módulo $ 7 $. Por isso, poderemos colocar algum destes números na frente de $ B $ para que ele seja múltiplo de $ 7 $. Como?

Qual permutação, que chamaremos de $ D $, devemos colocar à direita de $ B $? Observe que colocarmos um número $ D $ de três algarismos à direita de $ B $ é o equivalente ao tomarmos o número $ 100B+D $. Assim, se $ 100B $ tiver resto $ r $ na divisão por $ 7 $, basta tomarmos $ D $ com resto $ 7-r $.