20  Congruências com incôgnitas e o Teorema Chinês dos restos V2.0

20.1 Congruências com incôgnitas

Exemplo 20.1 Seja \(x\) uma incógnita e considere a congruência \[ x\equiv 4\pmod 6. \] As soluções desta congruência são números inteiros que são congruentes com \(4\) módulo \(6\). Claramente \(x=4\) é uma solução particular desta congruência e o conjunto das soluções é \[ \{6k+4\mid k\in\Z\}. \]

Exemplo 20.2 Considere agora o seguinte exemplo um pouco mais complicado: \[ 3x\equiv 4\pmod {10}. \] Note que \(3\) é invertível módulo \(10\) e o seu inverso é \(7\), pois \(3\cdot 7=21\equiv 1\pmod {10}\). Multiplicando os dois lados desta congruência por \(7\), obtemos que \[ x\equiv 21x=7\cdot 3x=7\cdot 4=28\equiv 8\pmod{10}. \] Logo, a congruência neste exemplo é equivalente à congruência \[ x\equiv 8\pmod{10}. \] As soluções desta última congruência, e também da congruência anterior, são números no conjunto \[ \{10k+8\mid k\in\Z\}. \]

Exemplo 20.3 Considere a congruência \[ 3x\equiv 5\pmod 6. \] Note que uma solução \(x\in\Z\) desta congruência satisfaz a equação diofantina \(3x-5=6k\) com algum \(k\in\Z\), ou seja \[ 3x-6k=5. \] Mas, como \(\mdc 36\nmid 5\), esta equação diofantina não possui solução e assim a conguência anterior também não possui solução

Exemplo 20.4 Considere a congruência \[ 6x\equiv 4\pmod {10}. \] Note que \(x\) é solução desta congruência se e somente se \(10\mid 6x-4\) que ocorre se e somente se \(5\mid 3x-2\). Ou seja, a congruência original deste exemplo é equivalente à congruência \[ 3x\equiv 2\pmod{5}. \] Multiplicando os dois lados desta congruência com \(2\) (que é o inverso modular de \(3\) módulo \(5\)), obtemos que \[ x\equiv 4\pmod 5 \] e as soluções são \[ \{5k+4\mid k \in\Z\}. \]

Teorema 20.1 Sejam \(a,b\in\Z\) e \(n\in\N\). Considere a congruência \[ ax\equiv b\pmod n. \] A congruência possui solução se e somente se \(\mdc an\mid b\). Neste caso, pondo \(d=\mdc an\), \(a_1=a/d\), \(b_1=b/d\) e \(n_1=n/d\) (e notando que estes são inteiros), a congruência é equivalente à congruência \[ a_1 x\equiv b_1\pmod{n_1} \] onde \(\mdc {a_1}{n_1}=1\). Seja \(c\in\Z\) inverso de \(a_1\) módulo \(n_1\). Então uma solução particular desta congruência é \(x_0=cb_1\) e a solução geral é \[ \{cb_1+kn_1\mid k\in\Z\}. \]

Comprovação. Seja \(d=\mdc an\). Então \(x\) é solução da congruência original se e somente se \(n\mid ax-b\). Se \(d\nmid b\), então esta divisibilide é impossível, pois \(d\mid n\) e \(d\mid ax\) e a congruência não possiu solução. Caso \(d\mid b\), a divisibilidade \(n\mid ax-b\) ocorre se e somente se \(n_1\mid a_1x-b_1\) e neste caso, a congruência original é equivalente à congruência \[ a_1 x\equiv b_1\pmod{n_1}. \] Agora \(\mdc{a_1}{n_1}=1\) e \(a_1\) é invertível módulo \(n_1\). A afirmção final do teorema pode ser verificada multiplicando os dois lados da última congruência por um inverso modular \(c\) de \(a_1\)

20.2 O Teorema Chinês dos Restos V2.0

Sejam \(m,n\in\N\) primos entre si, sejam \(a,b\in\Z\) e considere o sistema \[\begin{align*} x &\equiv a\pmod m\\ x &\equiv b\pmod n \end{align*}\] de congruências.

Uma solução \(x\in\Z\) deste sistema é um número inteiro tal que o resto de \(x\) é o mesmo que o resto de \(a\) quando divididos por \(m\) e o resto de \(x\) é o mesmo que o resto de \(b\) quando divididos por \(n\). Já vimos em uma aula anterior que tal \(x\) sempre existe. Seja \(x_0\) uma solução deste sistema (ou seja, uma solução particular do sistema). É fácil verificar que \(x_0+kmn\) com \(k\in\Z\) também é uma solução; de fato, \[\begin{align*} x_0+kmn&\equiv x_0\equiv a\pmod m\\ x_0+kmn&\equiv x_0\equiv b\pmod n. \end{align*}\] Além disso, se \(x\in\Z\) é uma outra solução, então \[\begin{align*} x&\equiv x_0\pmod m\\ x&\equiv x_0\pmod n. \end{align*}\] Aplicando a definição de ser congruente, obtemos que \(m\mid x-x_0\) e \(n\mid x-x_0\). Como \(\mdc mn=1\), tem-se que \(mn\mid x-x_0\); ou seja, \(x-x_0=kmn\) com algum \(k\in\Z\). Portanto \(x=x_0+kmn\).

Com este argumento verificamos o seguinte resultado, que pode ser visto como uma versão do Teorema Chinês dos Restos.

Teorema 20.2 Sejam \(m,n\in\N\) primos entre si, sejam \(a,b\in\Z\). Então o \[\begin{align*} x &\equiv a\pmod m\\ x &\equiv b\pmod n \end{align*}\] de congruências sempre possui uma solução. Além disso, se \(x_0\) é uma solução do sistema, então o conjunto das soluções (a solução geral) pode ser obtido como \[ \{x_0+kmn\mid k\in\Z\}. \]

Comprovação. Veja o argumento antes do teorema.

Note que uma solução particular para o sistema pode ser encontrada usando o Algoritmo Estendido de Euclides como fizemos no caso da primeira versão do Teorema Chinês. Note ainda que o teorema diz que o conjunto de soluções é uma classe residual módulo \(mn\) e este conjunto é o mesmo que o conjunto das soluções da congruência \[ x\equiv x_0\pmod{mn}. \]

Corolário 20.1 Com as condições no teorema anterior, o sistema \[\begin{align*} x &\equiv a\pmod m\\ x &\equiv b\pmod n \end{align*}\] de congruências é equivalente à congruência \[ x\equiv c\pmod{mn} \] com algum \(c\in\Z\).

O número \(c\) no corolário pode ser determinado usando o Algoritmo Estendido de Euclides.