Sejam n1, n2, cdots, nr inteiros positivos dois a dois primos entre si, isto é, mdc(ni, nj)=1, se i neq j e sejam a1, a2, cdots, ar inteiros tais que m d c(ak, nk)=1 para k in1,2, cdots, r. Mostre então que o sistema
c a1 x equiv b1(bmod n1) a2 x equiv b2(bmod n2) vdots vdots vdots ar x equiv br(bmod nr)
tem solução única módulo n=n1, n2 ldots nr. Com base neste resultado, resolva o seguinte sistema de congruências
c 2 x equiv 1(bmod 5) 3 x equiv 2(bmod 7) 4 x equiv 3(bmod 11)

Passo 1

O enunciado pede para mostrar que, se
tem solução única módulo em e depois combinando as soluções. A seguir fazemos a prova geral e depois resolvemos

Passo 2

Como gcd(ak,nk)=1, existe inverso de ak em Bbb Znk, digamos ak^-1 tal que
ak,ak^-1equiv1pmodnk
Multiplicando a k-ésima congruência por ak^-1, obtemos
xequiv ckpmodnk,onde ck=ak^-1bkbmod nk
Logo o sistema original é equivalente ao sistema “puro”
xequiv c1pmodn1,; xequiv c2pmodn2,;dots,; xequiv crpmodnr

Passo 3

Pelo Teorema Chinês dos Restos, como gcd(ni,nj)=1 para ineq j, existe solução única de
xequiv ckpmodnk(k=1,dots,r)
módulo N=n1cdots nr. A construção explícita é: defina
N = n1n2cdots nr, Nk=Nnk,
e seja Mk o inverso de Nk em Bbb Znk, ou seja
NkMkequiv1pmodnk
Então
x ;=;sumk=1^r ck,Nk,Mk ;bmod N
é a solução comum, e qualquer outra difere desta por múltiplo de N.

Passo 4

Aplicando ao sistema
2xequiv1pmod5, 3xequiv2pmod7, 4xequiv3pmod11,
primeiro encontramos os ck:
  • gcd(2,5)=1, o inverso de 2 em Z5 é 3 pois 2cdot3=6equiv1pmod5. Logo
xequiv3cdot1=3pmod5, c1=3
  • gcd(3,7)=1, o inverso de 3 em Z7 é 5 pois 3cdot5=15equiv1pmod7. Logo
xequiv5cdot2=10equiv3pmod7, c2=3
  • gcd(4,11)=1, o inverso de 4 em Z11 é 3 pois 4cdot3=12equiv1pmod11. Logo
xequiv3cdot3=9pmod11, c3=9
Agora N=5cdot7cdot11=385. Calculamos
N1=3855=77, N2=3857=55, N3=38511=35
Achamos os inversos Mk:
  • 77equiv2pmod5 e 2^-1equiv3pmod5, logo M1=3.
  • 55equiv6pmod7 e 6^-1equiv6pmod7, logo M2=6.
  • 35equiv2pmod11 e 2^-1equiv6pmod11, logo M3=6.
    Por fim
x ;=;3cdot77cdot3;+;3cdot55cdot6;+;9cdot35cdot6 ;=;693+990+1890 ;=;3573 ;equiv;108pmod385

Resposta

A solução única é
xequiv108pmod385

Exercícios relacionados