(1,5) Resolva as congruências lineares:
23 x \equiv 7(\bmod 19).

Passo 1

O enunciado pede para resolver a congruência linear
23x \equiv 7 \pmod{19}.
Informações relevantes fornecidas:
  • O coeficiente do lado esquerdo é 23.
  • O módulo é 19.
  • O termo à direita é 7.
  • A solução procurada é o conjunto de inteiros x que satisfazem essa congruência (isto é, a classe de equivalência de x módulo 19).

Passo 2

Estratégia e teoria necessária (passo-a-passo didático):
  • Para resolver uma congruência linear ax \equiv b \pmod{m} procede-se assim:
    1. Reduzir a módulo m (substituir por seu resto) para simplificar.
    2. Calcular d=\gcd(a,m). Se d\nmid b, não há solução. Se d\mid b, existem exatamente d soluções distintas módulo m.
    3. No caso d=1 (ou seja, \gcd(a,m)=1), existe um único inverso multiplicativo de a módulo m. Encontrando esse inverso a^{-1} tal que a a^{-1}\equiv1\pmod{m}, multiplica-se ambos os lados por a^{-1} e obtém-se x\equiv a^{-1}b\pmod{m}.
  • Para encontrar o inverso de a módulo m usa-se o algoritmo de Euclides estendido: ele fornece inteiros u,v tais que au + mv = \gcd(a,m). Quando \gcd(a,m)=1, então u é o inverso de a módulo m.

Passo 3

Aplicando a redução do coeficiente:
  • Como 23 \equiv 4 \pmod{19} (pegando esse resto de 23 dividido por 19), a congruência é equivalente a
4x \equiv 7 \pmod{19}.
Agora calculemos \gcd(4,19):
  • Usando o algoritmo de Euclides: 19 = 4\cdot4 + 3, 4 = 3\cdot1 + 1, 3 = 1\cdot3 + 0. Assim \gcd(4,19)=1.
  • Como \gcd(4,19)=1 e 1\mid 7, existe exatamente uma solução modulo 19.

Passo 4

Encontrar o inverso de 4 módulo 19 (Euclides estendido, com explicação):
  • Reescrevendo as divisões: 19 = 4\cdot4 + 3,
4 = 3\cdot1 + 1.
  • Agora fazemos substituições para escrever 1 como combinação linear de 4 e 19: 1 = 4 - 3\cdot1.Mas 3 = 19 - 4\cdot4, logo 1 = 4 - (19 - 4\cdot4) = 4 - 19 + 16 = 5\cdot4 - 1\cdot19.
  • Portanto existem inteiros u=5 e v=-1 tais que 5\cdot4 + (-1)\cdot19 = 1.
  • Isso mostra que 5 é o inverso multiplicativo de 4 módulo 19, pois 4\cdot5\equiv1\pmod{19}.

Passo 5

Obter a solução usando o inverso:
  • Multiplicando a congruência 4x\equiv7\pmod{19} pelo inverso 5, obtemos x \equiv 5\cdot 7 \pmod{19}.
  • Calcule 5\cdot7 = 35. Reduzindo módulo 19: 35 - 19 = 16. Assim x \equiv 16 \pmod{19}.
  • Verificação rápida (pra ficar seguro): 23\cdot16 = 368. Como 19\cdot19 = 361, tem-se 368-361=7, logo 23\cdot16\equiv7\pmod{19}. Correto!

Passo 6

Interpretação final e forma geral das soluções:
  • A solução única na classe dos restos módulo 19 é x\equiv16\pmod{19}.
  • Em termos de inteiros, todas as soluções são x = 16 + 19k,\quad k\in\mathbb{Z}.
  • Dica para prova: sempre reduza a módulo m primeiro; se \gcd(a,m)=1 procure o inverso (Euclides estendido é rápido e seguro).

Resposta

\,x\equiv16\pmod{19}
\,x=16+19k,\\ k\in\mathbb{Z}

Exercícios relacionados