Sejam
inteiros positivos dois a dois primos entre si, isto é,
, se
e sejam
inteiros tais que
para
. Mostre então que o sistema
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
Multiplicando a
k -ésima congruência por
ak^-1 , obtemos
Logo o sistema original é equivalente ao sistema “puro”
Passo 3
Pelo Teorema Chinês dos Restos, como
gcd(ni,nj)=1 para
ineq j , existe solução única de
módulo
N=n1cdots nr . A construção explícita é: defina
e seja
Mk o inverso de
Nk em
Bbb Znk , ou seja
Então
é a solução comum, e qualquer outra difere desta por múltiplo de
N .
Passo 4
Aplicando ao sistema
primeiro encontramos os
ck :
-
, o inverso degcd(2,5)=1 em2 éZ5 pois3 . Logo2cdot3=6equiv1pmod5
-
, o inverso degcd(3,7)=1 em3 éZ7 pois5 . Logo3cdot5=15equiv1pmod7
-
, o inverso degcd(4,11)=1 em4 éZ11 pois3 . Logo4cdot3=12equiv1pmod11
Agora
N=5cdot7cdot11=385 . Calculamos
Achamos os inversos
Mk :
-
e77equiv2pmod5 , logo2^-1equiv3pmod5 .M1=3 -
e55equiv6pmod7 , logo6^-1equiv6pmod7 .M2=6 -
e35equiv2pmod11 , logo2^-1equiv6pmod11 .M3=6
Por fim
Resposta
A solução única é