Teorema Chinês dos Restos

{x51x73x95\left\{ \begin{aligned} x \equiv_5 \quad 1\\ x \equiv_7 \quad 3\\ x \equiv_9 \quad 5 \end{aligned} \right.

Inverso

a~Zã \in \Z é o inverso de aZa \in \Z, para o módulo nN1n \in \N_1, se

a~×a=a×a~n1ã\times a = a\times ã \equiv_n 1

NOTA

  • Só há inverso se an=1a \frown n = 1 (aa primo com nn)
  • 11 e 1-1 são os seus próprios inversos, para qualquer módulo.
  • Não existe apenas só um inverso, mas vários. A expressão que dá todos os inversos a~ã de um número aa módulo nn, é dada por:
a~=a~0+nt,tZa~0um inverso de a moˊdulo n qualquerã = ã_0 + nt, t \in \Z\\ ã_0 \rightarrow \text{um inverso de }a \text{ módulo } n\text{ qualquer}

Como Calcular o Inverso

Queremos saber (a×a~)n1(a\times ã) \equiv_n 1, e sabe-se aa e nn.

  1. Verificar se dá para fazer mentalmente

Para fazer mentalmente, tenta-se encontrar k0k_0 e k1k_1, tal que

(a×k0)(n×k1)=1 ou (1)(a\times k_0) - (n \times k_1) = 1 \text{ ou } (-1)

No primeiro caso, (=1)(=1), k0=a~k_0=ã, k0k_0 é um inverso.

No segundo caso, a~=k0(1)=k0ã= k_0 (-1)=-k_0

Se quisermos uma solução positiva, podemos recorrer à Solução Geral.

  1. Não dá para fazer mentalmente

Resolve-se a equação diofantina

(a×k0)+(n×k1)=1(a\times k_0) + (n \times k_1) = 1

E k0k_0 será o inverso

Exemplo

Calcular 22k025122k_0 \equiv_{25} 1, inverso de 2222 módulo 2525.
Usando o método manual,

(7×k0)+(8×k1)=1,k0?(7\times k_0) + (8 \times k_1) = 1,\quad k_0?

Pelo Algoritmo de Euclides (estendido)

iaiqidimi025101221012371131784025(7)+22(8)=1\begin{array}{c|c|c|c|} i & a_i & q_i & d_i & m_i\\ \hline 0 & 25 & & 1 & 0\\ 1 & 22 & 1 & 0 & 1\\ 2 & 3 & 7 & 1 & -1\\ 3 & 1 & & -7 & 8\\ 4 & 0 & & & \end{array}\\ 25(-7) + 22(8) = 1\\

Ou seja,

k0=8k_0 = 8 \quad \checkmark

A solução geral é dada por:

λ=8+25t,tZ\lambda = 8 + 25t, \quad t \in \Z

Teoremas

Teorema 1

a1,,akZa_1, \dots, a_k \in \Z e m1,,mkN1m_1,\dots,m_k \in \N_1, com estes últimos primos entre si 2 a 2.
O problema:

{xm1a1xm2a2xmkak\left\{ \begin{aligned} x & \equiv_{m_1} \quad a_1\\ x & \equiv_{m_2} \quad a_2\\ & \vdots\\ x & \equiv_{m_k} \quad a_k \end{aligned} \right.

Tem solução única Módulo MM

M=i=1kmiM = \prod_{i=1}^k m_i

Teorema 2

a1,,akZa_1, \dots, a_k \in \Z e m1,,mkN1m_1,\dots,m_k \in \N_1, com estes últimos não necessariamente primos entre si.
O problema,

{xm1a1xm2a2xmkak\left\{ \begin{aligned} x & \equiv_{m_1} \quad a_1\\ x & \equiv_{m_2} \quad a_2\\ & \vdots\\ x & \equiv_{m_k} \quad a_k \end{aligned} \right.

Tem solução única módulo MM

M=m1m2mKab=mmc(a,b)M = m_1 \smile m_2 \smile \dots \smile m_K\\ a \smile b = mmc(a,b)

SE E SÓ SE, i,j=1,,k\forall i,j = 1,\dots, k, tais que 1i<jk1 \leq i < j \leq k,

(mimj)(aiaj)(m_i \frown m_j)|(a_i-a_j)

Teorema Chinês dos Restos

Módulos primos

{xm1a1xmkak\left\{ \begin{aligned} x & \equiv_{m_1} \quad a_1\\ & \vdots\\ x & \equiv_{m_k} \quad a_k \end{aligned} \right.

m1,,mkm_1,\dots,m_k, primos entre si 2 a 2

Pelo Teorema 1, há sempre solução

A Solução Geral é dada por

x=x0+Mt,tZx0=a1n1n~1++aknkn~kx = x_0 + Mt, \quad t \in \Z\\ x_0 = a_1n_1ñ_1 + \dots + a_kn_kñ_k

Onde,

  • M=i=1kmiM = \prod_{i=1}^k m_i
  • ni=m1××mi1×mi+1××mk=Mmin_i = m_1\times\dots\times m_{i-1} \times m_{i+1}\times \dots \times m_k = \frac M {m_i}
  • n~iñ_i é o inverso de nin_i, módulo mim_i
Exemplo
{3x+176x92x241\left\{ \begin{aligned} 3x+1 & \equiv_7 \quad 6\\ x & \equiv_9 \quad 2\\ x-2 & \equiv_4 \quad 1 \end{aligned} \right.

44,77 e 99 são primos entre si, 2 a 2.

  1. Colocar tudo na forma xnax \equiv_n a
3x+1763x753x +1 \equiv_7 6\\ 3x \equiv_7 5

Agora queremos encontrar o inverso de 33 módulo 77 (37=13 \frown 7 = 1), pois, sendo k7k_7 esse inverso,

(3k7)x75k7x75k7(3k_7)x \equiv_7 5k_7\\ x \equiv_7 5k_7

De cabeça, verifica-se que (3×5)(7×2)=1(3\times 5) -(7 \times 2) = 1, logo k7=5k_7 = 5.

(3×5)x7(5×5)x725x74(3\times5)x \equiv_7 (5\times5)\\ x \equiv_7 25 \\ x \equiv_7 4 \quad \checkmark
x92x\equiv_9 2 \quad \checkmark
x241x43x-2 \equiv_4 1\\ x \equiv_4 3 \quad \checkmark

Para aprender a calcular inversos mais difíceis, consultar Cálculo de Inversos

{x74x92x43\left\{ \begin{aligned} x & \equiv_7 \quad 4\\ x & \equiv_9 \quad 2\\ x & \equiv_4 \quad 3 \end{aligned} \right.\\

Temos,

a1=4,a2=2,a3=3m1=7,m2=9,m3=4a_1=4, a_2 = 2, a_3 = 3\\ m_1 = 7, m_2 = 9, m_3 = 4
  1. Calcular módulo da Solução (MM)
M=m1×m2×m3=7×9×4=252M = m_1\times m_2 \times m_3\\ = 7 \times 9 \times 4 = 252
  1. Calcular os nin_i (ni=Mmin_i = \frac M {m_i})
{n1=m2×m3=9×4=36n2=m1×m3=7×4=28n3=m1×m2=7×9=63\left\{ \begin{aligned} n_1 = m_2 \times m_3 = 9 \times 4 = 36\\ n_2 = m_1 \times m_3 = 7 \times 4 = 28\\ n_3 = m_1 \times m_2 = 7 \times 9 = 63 \end{aligned} \right.\\
  1. Calcular os inversos de nin_i módulo mim_i (n~iñ_i)
36n~171,367=136ñ_1 \equiv_7 1, \quad 36 \frown 7 = 1

Como (36×1)(7×5)=1,n~1=1(36\times1) - (7 \times 5) = 1, ñ_1 = 1

28n~291,289=128ñ_2 \equiv_9 1, \quad 28 \frown 9 = 1

Como (28×1)(9×3)=1,n~2=1(28\times1) - (9 \times 3) = 1, ñ_2 = 1

63n~341,,634=163ñ_3 \equiv_4 1, , \quad 63 \frown 4 = 1

Como (63×3)(4×47)=1,n~3=3(63 \times 3) - (4 \times 47)=1, ñ_3 = 3

  1. Solução Particular e Geral

Solução Geral é dada por,

x=x0+252t,tZx = x_0 +252t, \quad t \in \Z
x0=a1n1n~1+a2n2n~2+a3n3n~3=(4×36×1)+(2×28×1)+(3×63×3)=144+56+567=767x_0 = a_1n_1ñ_1+a_2n_2ñ_2+a_3n_3ñ_3\\ = (4\times36\times1)+(2\times28\times1)+(3\times63\times3)\\ = 144 + 56 + 567\\ = 767
x=767+252tx=11+252t,tZx=767+252t\\ x=11 + 252t, \quad t \in \Z

Módulos não primos

{xm1a1xmkak\left\{ \begin{aligned} x & \equiv_{m_1} \quad a_1\\ & \vdots\\ x & \equiv_{m_k} \quad a_k \end{aligned} \right.

m1,,mkm_1,\dots,m_k, não necessariamente primos entre si.

Pelo Teorema 2, há solução, se i,j=1,,k\forall i,j = 1,\dots, k, tais que 1i<jk1 \leq i < j \leq k,

(mimj)(aiaj)(m_i \frown m_j)|(a_i-a_j)

Se a condição se verificar, a Solução Geral é dada por

x=x0+Mt,tZx0=a1n1n~1++aknkn~kx = x_0 + Mt, \quad t \in \Z\\ x_0 = a_1n_1ñ_1 + \dots + a_kn_kñ_k

Onde,

  • M=i=1kciM = \prod_{i=1}^k c_i
  • cic_i é tal que: cimic_i|m_i e c1××ck=m1mk=Mc_1 \times \dots \times c_k = m_1 \smile \dots \smile m_k = M
    (com o exemplo fica claro)
  • c1,,ckc_1,\dots,c_k são primos 2 a 2.
  • ni=c1××ci1×ci+1××ck=Mcin_i = c_1\times\dots\times c_{i-1} \times c_{i+1}\times \dots \times c_k = \frac M {c_i}
  • n~iñ_i é o inverso de nin_i, módulo cic_i
Exemplo
{x1210x82x52{x1210x82x52\left\{ \begin{aligned} x &\equiv_{12} \quad &10\\ x &\equiv_8 \quad &2\\ x &\equiv_5 \quad &2 \end{aligned} \right. \quad \Leftrightarrow \quad \left\{ \begin{aligned} x &\equiv_{12} \quad &10\\ x &\equiv_8 \quad &2\\ x &\equiv_5 \quad &2 \end{aligned} \right.

Já está tudo na forma xnax \equiv_n a \quad \checkmark

Repare-se que 1212 e 88 não são primos entre si.

  1. Verificar se existe solução
m1m2=128=4,a1a2=102=84 divide 8m1m3=125=1,a1a3=102=81 divide 8m2m3=85=1,a2a3=22=01 divide 0m_1 \frown m_2 = 12 \frown 8 = 4, \qquad a_1-a_2=10-2=8\\ 4 \textnormal{ divide } 8 \quad \checkmark \\ m_1 \frown m_3 = 12 \frown 5 = 1, \qquad a_1-a_3=10-2=8\\ 1 \textnormal{ divide } 8 \quad \checkmark \\ m_2 \frown m_3 = 8 \frown 5 = 1, \qquad a_2-a_3=2-2=0\\ 1 \textnormal{ divide } 0 \quad \checkmark \\
  1. Calcular os cic_i e MM
m1=22×3,m2=23,m3=5m1m2m3=23×3×5=i=13cim_1 = 2^2 \times 3, \quad m_2 = 2^3, \quad m_3=5\\ m_1 \smile m_2 \smile m_3 = 2^3 \times 3 \times 5 = \prod_{i=1}^3c_i

Relembrar: No cálculo do mmcmmc, escolhemos todos os fatores primos, mas, se houver repetições, escolhemos o de maior expoente.

Como cimic_i|m_i,

c1=3,c2=23,c3=5c_1 = 3, \quad c_2 = 2^3, \quad c_3 = 5
M=23×3×5=120M = 2^3 \times 3 \times 5 = 120
  1. Calcular os nin_i
{n1=c2×c3=8×5=40n2=c1×c3=3×5=15n3=c1×c2=3×8=24\left\{ \begin{aligned} n_1 = c_2 \times c_3 = 8 \times 5 = 40\\ n_2 = c_1 \times c_3 = 3 \times 5 = 15\\ n_3 = c_1 \times c_2 = 3 \times 8 = 24 \end{aligned} \right.\\
  1. Calcular os n~iñ_i
40n~13140ñ_1 \equiv_3 1

Como (40×1)(3×13)=1,n~1=1(40\times1) - (3 \times 13) = 1, ñ_1 = 1

15n~28115ñ_2 \equiv_8 1

Como (15×1)(8×2)=1,n~2=1(1)=1(15\times1) - (8 \times 2) = -1,\quad ñ_2 = -1(1) = -1

Atenção: Podemos igualar a 1-1, em vez de 11. Nestes casos, o inverso do número nn é (1×k)(-1 \times k), onde nkn1nk \equiv_n -1. Para mais esclarecimentos, consultar Cálculo de Inversos

24n~35124ñ_3 \equiv_5 1

Como (24×1)(5×5)=1,n~3=1(1)=1(24 \times 1) - (5 \times 5)=-1,\quad ñ_3 = -1(1) = -1

  1. Solução Geral e Particular
x=x0+120t,tZx = x_0 +120t, \quad t \in \Z
x0=a1n1n~1+a2n2n~2+a3n3n~3=(1×40×1)+(2×15×1)+(2×24×1)=403048=38x_0 = a_1n_1ñ_1+a_2n_2ñ_2+a_3n_3ñ_3\\ = (1\times40\times1)+(2\times15\times-1)+(2\times24\times-1)\\ = 40 - 30 - 48\\ = -38
x=38+120tx=82+120t,tZx=-38+120t\\ x=82 + 120t, \quad t \in \Z