- ( 2 pontos) Encontre todas as soluções inteiras (entre 0 e m) para as congruência
e determine a forma geral de uma solução.
Passo 1
O enunciado dá a congruência
. Pede duas coisas:
- Encontrar todas as soluções inteiras entre
e (aqui o módulo é , então quero as soluções em ). - Determinar a forma geral de todas as soluções inteiras (ou seja, uma expressão que gera todas as soluções).
Informações fornecidas: o coeficiente
, o termo à direita
e o módulo
.
Passo 2
Antes de tentar resolver, precisamos verificar se a congruência tem solução. Existe um resultado simples que vamos usar e entender bem: a congruência
tem solução se, e somente se,
divide
. Aqui
significa o maior divisor comum entre
e
. Vou aplicar isso ao nosso caso com
,
,
.
Passo 3
Calcular
usando o algoritmo de Euclides (passo a passo para você entender):
Como o resto chegou a
, o último resto não nulo é
. Logo
Explicação didática:
significa que
e
são coprimos (não têm divisor comum além de
). Como
divide qualquer inteiro, em particular divide
, a condição de existência de solução está satisfeita. Portanto há soluções.
Passo 4
Quando
, existe um inverso multiplicativo de
módulo
; isto é, existe um número
tal que
Se encontrarmos esse inverso, basta multiplicar ambos os lados da congruência por ele para isolar
.
No nosso caso
e
. Como os números são pequenos, podemos achar o inverso de
por tentativa rápida: calcule os restos de múltiplos de
módulo
:
Vimos que
. Portanto o inverso de
módulo
é
mesmo:
.
Passo 5
Multiplicamos a congruência original por esse inverso para resolver para
. Começamos com
Multiplicando ambos os lados por
(o inverso de
modulo
) obtemos
No lado esquerdo
, porque
. No lado direito
. Assim
Agora reduzimos
módulo
:
, então
Passo 6
Interpretando o resultado: a congruência
significa que todas as soluções inteiras são números que deixam resto
na divisão por
. A forma geral de todas as soluções é
Explicação do porquê: se
é solução, então
também é solução porque
e
. Portanto adicionar múltiplos de
não altera a congruência.
Passo 7
Agora a parte pedida das soluções entre
e
. O conjunto padrão de representantes de classes modulares é
. Desses, apenas
satisfaz a congruência
. Podemos verificar plugando
:
logo satisfaz
.