Dados a, m in Z, com m>0 e (a, m)=1. Mostre que existe solução de a x equiv b(bmod m). Além disso, se x0 é solução, então x0+m k, com k in Z, é também solução.

Passo 1

O enunciado pede para mostrar que, dado ,a,minZ com m>0 e gcd(a,m)=1, a congruência
a x equiv b pmodm
tem pelo menos uma solução inteira x. Além disso, devemos provar que, uma vez encontrada uma solução x0, todos os inteiros da forma x0 + m k (com kinZ) também são soluções.
Para isso vamos usar dois fatos básicos de teoria dos números:
  1. Identidade de Bézout (existe combinação linear de a e m que vale 1).
  2. Propriedade de estabilidade das congruências sob soma de múltiplos do módulo.

Passo 2

Como gcd(a,m)=1, pela identidade de Bézout existem inteiros u e v tais que
a,u + m,v = 1
Multiplicando essa igualdade por b obtemos
a,(u,b) + m,(v,b) = b
Isso quer dizer que
a,(u,b) equiv b pmodm
Logo x0 = u,b é uma solução da congruência a x equiv b pmodm.

Passo 3

Agora provamos que, se x0 é solução, então x0 + m k também é solução para qualquer kinZ. Como
a,(x0 + m k) = a,x0 + a,m,k
temos
a,(x0 + m k) equiv a,x0 + m,(a,k) equiv b + 0 equiv b pmodm,
pois a,x0equiv bpmodm e m,(a,k)equiv 0pmodm.

Resposta

Existe solução porque, pela identidade de Bézout, x0 = u,b satisfaz a x0equiv bpmodm. Além disso, todas as soluções são da forma
x = x0 + m,k, kinZ

Exercícios relacionados