Prove que se mdc(a, m)=1, então existe um inteiro x tal que a x equiv 1(bmod m). Além disso, prove que quaisquer dois x que satisfazem essa propriedade são iguais bmod m.

Passo 1

Resumo do enunciado: queremos mostrar duas coisas (em Teoria dos Números):
  1. Se a,x equiv 1 pmod m , então existe inteiro tal que
Isto significa que tem inverso multiplicativo módulo .
2) Sejam e duas soluções de . Provar que , ou seja, a inversa é única módulo .
Conteúdo necessário:
  • Definição de e coprimalidade.
  • Algoritmo de Euclides estendido e identidade de Bézout.
  • Noções de congruência modular.

Passo 2

(Existência do inverso)
Como a,s + m,t = 1 , pela identidade de Bézout existe uma combinação linear
a,s + m,t equiv 1 pmod m
para alguns inteiros a,s equiv 1 pmod m e . Essa identidade vem diretamente do algoritmo de Euclides estendido, que nos dá justamente esses coeficientes .
Agora, basta olhar essa igualdade módulo . Ele diz
Mas , então sobra
Logo, é um inverso de módulo . Isso prova a existência de algum com .

Passo 3

(Unicidade módulo a,x equiv 1 pmod m e a,x' equiv 1 pmod m )
Suponha que a,x - a,x' equiv 0 pmod m Longrightarrow a,(x - x') equiv 0 pmod m e m mid (x - x') Longrightarrow x equiv x' pmod m sejam dois inteiros tais que
Subtraindo as duas congruências, temos
Isto significa que divide . Mas como , um teorema básico diz que, se um número primo a divide um produto, ele já divide o outro fator. No caso geral de , concluímos que divide . Em símbolos:
Isso prova que qualquer outra solução só difere de por múltiplo de .

Resposta

  1. Pela identidade de Bézout (Euclides estendido) obtemos inteiros tais que . Assim satisfaz .
  2. Se e são duas inversas, então . Como , segue . Portanto o inverso é único módulo .

Exercícios relacionados