Sejam a, b inteiros e p um primo tais que \operatorname{mdc}(a, p)=1. Mostre que uma solução da congruência a x \equiv b(\bmod p) é x=a^{p-2} b.

Passo 1

O enunciado dá as seguintes informações:
  • a e b são inteiros.
  • p é um primo.
  • \operatorname{mdc}(a,p)=1 (ou seja, p não divide a).
    A pergunta que precisamos responder é: mostrar que uma solução da congruência
a x \equiv b \pmod{p}
é
x = a^{p-2} b.

Passo 2

Vamos primeiro entender o que significa “solução” da congruência e a ideia de inverso multiplicativo:
  • Dizer que x é solução de a x \equiv b \pmod{p} significa que, ao multiplicar a por x e subtrair b, o resultado é múltiplo de p.
  • Se existir um número y tal que
a y \equiv 1 \pmod{p},
então y é o inverso multiplicativo de a módulo p. Nesse caso, multiplica-se a congruência a x \equiv b por y e obtém-se x \equiv y b \pmod{p}. Assim, encontrar uma solução para a x \equiv b reduz-se a encontrar um inverso de a módulo p.

Passo 3

Apresento agora um resultado fundamental (que será usado): para p primo e \operatorname{mdc}(a,p)=1 vale
a^{p-1} \equiv 1 \pmod{p}.
Explicação curta e intuitiva (prova clássica): considere os resíduos 1,2,\dots,p-1 módulo p. Multiplicar cada um por a (com a invertível módulo p) apenas permuta esses resíduos sem produzir nenhum múltiplo de p. Portanto o produto dos elementos da sequência coincide módulo p com o produto dos mesmos elementos multiplicados por a, isto é,
1\cdot 2\cdots (p-1) \equiv a\cdot 2a\cdots (p-1)a \equiv a^{p-1}\bigl(1\cdot 2\cdots (p-1)\bigr) \pmod{p}.
Como 1\cdot 2\cdots (p-1) não é múltiplo de p, pode-se “cancelar” esse fator (porque é invertível módulo p) e obter a^{p-1}\equiv1\pmod p.

Passo 4

A partir de a^{p-1}\equiv1\pmod p obtemos diretamente que
a\cdot a^{p-2} = a^{p-1} \equiv 1 \pmod{p}.
Isto mostra que a^{p-2} é um inverso multiplicativo de a módulo p: ou seja,
a^{p-2} \equiv a^{-1} \pmod{p}.

Passo 5

Agora usamos esse inverso para resolver a congruência. Multiplique a congruência original a x \equiv b \pmod{p} por a^{p-2} em ambos os lados:
a^{p-2}\bigl(a x\bigr) \equiv a^{p-2} b \pmod{p}.
Pela associatividade,
\bigl(a^{p-2} a\bigr) x \equiv a^{p-2} b \pmod{p}.
Mas sabemos que a^{p-2} a \equiv 1 \pmod{p}, logo
1\cdot x \equiv a^{p-2} b \pmod{p},
ou seja
x \equiv a^{p-2} b \pmod{p}.
Portanto x=a^{p-2} b (mod p) é de fato uma solução.

Passo 6

Pequeno exemplo numérico para fixar a ideia: tome p=7, a=3, b=5. Então a^{p-2}=3^{5}=243. Calculando módulo 7 temos 243\equiv5\pmod7. Logo x\equiv 5\cdot 5=25\equiv4\pmod7. Conferindo: a x = 3\cdot 4 =12\equiv5\pmod7, que é exatamente b. Funciona!

Resposta

x \equiv a^{p-2} b \pmod{p}

Exercícios relacionados