Resolva cada sistema de congruências abaixo:
\begin{cases}x \equiv 3 & (\bmod 7) \\ x \equiv 4 & (\bmod 9) \\ x \equiv 5 & (\bmod 11)\end{cases}

Passo 1

O problema dá o seguinte sistema de congruências e pede encontrar todos os inteiros x\) que o satisfazem: \[\begin{cases} x \equiv 3 & (\bmod\\\ 7)\\[4pt] x \equiv 4 & (\bmod\\\ 9)\\[4pt] x \equiv 5 & (\bmod\\\ 11) \end{cases}
Informações relevantes fornecidas:
\;3,\;4,\;5\] são os restos desejados e \(\;7,\;9,\;11 são os módulos correspondentes.
O enunciado não pede uma única representação, então devemos dar a solução inteira (isto é, a classe de congruência) — normalmente expressa como x \equiv r \pmod{N}, onde N é o produto dos módulos, se a solução for única módulo esse produto.]

Passo 2

Plano de resolução (explicação didática do método que vamos usar):
Quando os módulos são dois a dois primos entre si (isto é, \gcd(7,9)=\gcd(7,11)=\gcd(9,11)=1), existe uma solução única módulo o produto N=7\cdot9\cdot11. A técnica construtiva consiste em:
  1. Calcular N = 7\cdot9\cdot11.
  2. Para cada congruência x\equiv a_i \pmod{n_i} calcular N_i = N/n_i.
  3. Encontrar o inverso multiplicativo de N_i módulo n_i, ou seja, um número m_i tal que N_i m_i\equiv 1\pmod{n_i}.
  4. A solução é dada por
x \equiv \sum_{i} a_i N_i m_i \pmod{N}.
Aqui vou explicar o conceito de inverso modular: dado b e um módulo n com \gcd(b,n)=1, o inverso de b modulo n é um inteiro y tal que b y\equiv 1\pmod{n}. Podemos achar y por tentativa se os números forem pequenos, ou pelo algoritmo de Euclides estendido em geral.

Passo 3

Calcular o produto dos módulos e os N_i:
N = 7\cdot 9\cdot 11 = 693.
Agora:
N_1 = \frac{N}{7} = 99,\qquad N_2 = \frac{N}{9} = 77,\qquad N_3 = \frac{N}{11} = 63.

Passo 4

Encontrar os inversos m_i tais que N_i m_i \equiv 1 \pmod{n_i}.
Para n_1=7 e N_1=99:
99 \equiv 99-7\cdot14 = 99-98 = 1 \pmod{7},
ou seja, 99\equiv 1\pmod{7}. Logo m_1=1 porque 99\cdot 1 \equiv 1\pmod{7}.
Para n_2=9 e N_2=77:
77 \equiv 77-9\cdot8 = 77-72 = 5 \pmod{9}.
Precisamos de m_2 tal que 5 m_2 \equiv 1\pmod{9}. Testando pequenos valores, 5\cdot 2 = 10 \equiv 1\pmod{9}. Então m_2 = 2.
Para n_3=11 e N_3=63:
63 \equiv 63-11\cdot5 = 63-55 = 8 \pmod{11}.
Queremos m_3 com 8 m_3 \equiv 1\pmod{11}. Observando, 8\cdot 7 = 56 \equiv 1\pmod{11} (pois 56-11\cdot5=1). Então m_3 = 7.
(Se preferir ver pelo Euclides estendido para 8 em módulo 11: 11=1\cdot8+3, 8=2\cdot3+2, 3=1\cdot2+1. Voltando: 1=3-1\cdot2=3-1\cdot(8-2\cdot3)=3\cdot3-1\cdot8=(11-1\cdot8)\cdot3-1\cdot8=3\cdot11-4\cdot8. Assim -4\cdot8\equiv1, e -4\equiv7\pmod{11}, confirmando m_3=7.)

Passo 5

Montar a soma da fórmula e calcular cada termo:
Usamos a_1=3,\;a_2=4,\;a_3=5. Então
x \equiv a_1 N_1 m_1 + a_2 N_2 m_2 + a_3 N_3 m_3 \pmod{693}.
Calculemos termo a termo:
a_1 N_1 m_1 = 3\cdot 99\cdot 1 = 297,
a_2 N_2 m_2 = 4\cdot 77\cdot 2 = 4\cdot 154 = 616,
a_3 N_3 m_3 = 5\cdot 63\cdot 7 = 5\cdot 441 = 2205.
Somando:
297 + 616 + 2205 = 3118.

Passo 6

Reduzir o resultado módulo N=693:
Dividindo 3118 por 693, temos 693\cdot 4 = 2772 e
3118 - 2772 = 346.
Portanto o resto ao dividir 3118 por 693 é 346. Podemos verificar rapidamente que esse resto satisfaz as três congruências:
346 \equiv 3 \pmod{7}\quad(\text{pois }346-7\cdot49=346-343=3),
346 \equiv 4 \pmod{9}\quad(\text{pois }346-9\cdot38=346-342=4),
346 \equiv 5 \pmod{11}\quad(\text{pois }346-11\cdot31=346-341=5).

Resposta

x \equiv 346 \pmod{693}

Exercícios relacionados