\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:
Calcular N = 7\cdot9\cdot11.
Para cada congruência x\equiv a_i \pmod{n_i} calcular N_i = N/n_i.
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}.
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.
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