Aplicando o teorema chinês do resto (TCR) resolva os seguintes sistemas de conguências lineares com duas ECL, caso exista solução. Se não for possível aplicar o TCR resolva de forma direta.

Passo 1

Opa! Então o problema é o seguinte: a gente quer encontrar todos os inteiros x equiv 3 pmod26, x equiv 11 pmod33 que satisfazem simultaneamente
Isso faz parte da matéria de “congruências” e, mais especificamente, do Teorema Chinês do Resto (TCR). Para usar o TCR a gente precisa que os módulos (aqui 26 e 33) sejam coprimos, e depois aplicar fórmula com o algoritmo de Euclides estendido para achar inversos.

Passo 2

Primeiro, verifica se 26 e 33 são coprimos, isto é, se .
– Fatorando: , .
– Não têm fatores comuns, logo .
Como deu 1, podemos usar o TCR.

Passo 3

No TCR, calculamos:
N = 26 times 33 = 858
Depois definimos
M1 = N26 = 33, M2 = N33 = 26
A ideia é escrever a solução como
x ;=; a1,M1,y1 ;+; a2,M2,y2 ;bmod N,
em que , , e cada é o inverso de módulo do outro módulo.

Passo 4

Agora precisamos achar M1,y1 equiv 1 pmod26, tal que
33,y1 equiv 1 pmod26
ou seja
7,y1 equiv 1 pmod26
Note que 7 times 15 = 105 equiv 1 pmod26, , então buscamos
Usando o algoritmo de Euclides estendido (ou tentativa rápida), encontramos que
logo .

Passo 5

Em seguida, achamos M2,y2 equiv 1 pmod33, tal que
26,y2 equiv 1 pmod33
ou seja
26 times 14 equiv 1 pmod33,
Aplicando o Euclides estendido (detalhe: 33=26·1+7, 26=7·3+5, 7=5·1+2, 5=2·2+1 e voltando), ficamos com
portanto .

Passo 6

Agora montamos a solução via TCR:
x ;=; 3cdot M1cdot y1 ;+; 11cdot M2cdot y2 =; 3cdot33cdot15 ;+; 11cdot26cdot14
Calculando:
3cdot33cdot15 = 1485, 11cdot26cdot14 = 4004, 1485+4004 = 5489
Mas isso é uma representação “grande” — a gente sempre reduz módulo 5489 mod 858 = 5489 - 6cdot858 = 5489 - 5148 = 341 :

Resposta

A solução geral é
boxedx equiv 341 pmod858

Exercícios relacionados