Resolver os seguintes sistemas de congruências lineares:
Passo 1
O enunciado pede para resolver o sistema de congruências
ou seja, achar um inteiro
que satisfaça as duas condições simultaneamente. Como
, podemos aplicar o Teorema Chinês dos Restos e obter uma solução única módulo
.
Passo 2
Da primeira congruência temos
para algum
.
Passo 3
Substituindo em
dá
Passo 4
Para resolver
precisamos do inverso de
módulo
. Usamos o algoritmo de Euclides estendido:
Agora voltamos para expressar
como combinação linear de
e
:
Substituindo em cascata obtemos
logo
é o inverso de
módulo
.
Passo 5
Multiplicando
pelo inverso
temos
Passo 6
Substituindo
em
resulta
Como a solução é única módulo
, a família de soluções é