Encontre um Sistema Completo de Resíduos módulo 13 formado apenas por múltiplos de 5 .
Passo 1
O enunciado pede: encontrar um sistema completo de resíduos módulo
formado apenas por múltiplos de
.
Informações dadas:
- O módulo é
. - Precisa-se de um conjunto com exatamente
inteiros (ou classes) que representem todas as classes residuais mod distintas. - Todos os elementos desse conjunto devem ser múltiplos de
(isto é, números da forma , ).
Passo 2
Conceito importante (o que é um sistema completo de resíduos): um conjunto de
inteiros
é um sistema completo de resíduos módulo
se, ao reduzir cada
módulo
, obtém-se todas as classes
exatamente uma vez. Ou seja, os resíduos mod
dos elementos do conjunto são todos distintos e cobrem todas as classes mod
.
Vou explicar devagar e com exemplo: por exemplo,
é um sistema completo de resíduos módulo
porque seus resíduos são
. Já
não é, porque todos são congruentes a
mod
.
Passo 3
Estratégia geral que vamos usar (sem resolver ainda): considerar os múltiplos de
,
e mostrar que, ao reduzir módulo
, esses
números dão resíduos distintos — então formam um sistema completo de resíduos módulo
.
Para justificar isso é útil um fato geral: se
, então os números
formam um sistema completo de resíduos módulo
. Vou provar esse fato na próxima etapa.
Passo 4
Prova do fato geral (passo-a-passo e bem didático):
- Suponha
. Considere e com . - Se
, então . - Como
, o único múltiplo de que é congruente a módulo ocorre quando . Formalmente, existe tal que . Pelo teorema da divisibilidade, como é invertível módulo , isto implica . - Logo
. Mas estão entre e , então isso força . - Conclusão: os
valores são todos distintos módulo . Como há exatamente classes mod , esses valores representam todas as classes — portanto formam um sistema completo de resíduos módulo .
Comentário intuitivo: multiplicar por
com
“permuta” as classes mod
, não cria colisões.
Passo 5
Aplicando ao nosso caso: aqui
e
.
Calcular
. Como
é primo e
não é múltiplo de
, temos
Pelo resultado acima, os
números
formam um sistema completo de resíduos módulo
.
Passo 6
Agora vou listar esses múltiplos e reduzir cada um módulo
para ver explicitamente os resíduos (faço as contas passo a passo, para você conseguir reproduzir na prova sem calculadora):
-
. Redução: . -
. Redução: . -
. Redução: . -
. Redução: . -
. Redução: . -
. Redução: . -
. Redução: . -
. Redução: . -
. Redução: . -
. Redução: . -
. Redução: . -
. Redução: . -
. Redução: .
Lista dos resíduos obtidos (na ordem dos
de
a
):
Passo 7
Verificação final e conclusão didática:
- Os resíduos listados são
em alguma ordem? Sim — olhando a lista: aparecem exatamente uma vez cada (por exemplo, aparece como , como , etc.). - Portanto os
múltiplos de que coloquei representam todas as classes mod sem repetição, logo formam um sistema completo de resíduos módulo .
Dica prática para prova: sempre que precisar de um sistema completo de resíduos formado por múltiplos de
, verifique
. Se for
, os múltiplos
servem imediatamente.