(20 Pontos) Seja n>1 um número inteiro e seja \bar{x} \in \mathbb{Z}_{n}, 0 \leq x<n. Mostre que existe \bar{y} \in \mathbb{Z}_{n} de modo que \bar{x} \cdot \bar{y}=\bar{y} \cdot \bar{x}=\overline{1} se, e somente se, \operatorname{MDC}\{x, n\}=1.

Passo 1

O enunciado pede para mostrar que, dado um inteiro n>1 e um elemento \bar x\in\mathbb{Z}_n com 0\le x<n, existe \bar y\in\mathbb{Z}_n tal que
\bar x\cdot\bar y=\bar y\cdot\bar x=\overline{1}
se, e somente se, \gcd(x,n)=1.
O conteúdo usado será teoria de números: divisibilidade, máximo divisor comum e o lema de Bezout (identidade de Bezout).

Passo 2

Prova da direção “ \Rightarrow”: suponha que \bar x tenha inverso \bar y. Então
\bar x\cdot\bar y = \overline{1} \quad\Longrightarrow\quad xy \equiv 1 \pmod{n}.
Isso significa que existe inteiro k tal que
xy - 1 = kn \quad\Longrightarrow\quad xy +(-k)n = 1.
Mas qualquer divisor comum de x e n divide ambos xy e kn, logo divide o seu combinado xy - kn = 1. Assim \gcd(x,n) divide 1, o que implica
\gcd(x,n)=1.

Passo 3

Prova da direção “ \Leftarrow”: suponha \gcd(x,n)=1. Pelo lema de Bezout, existem inteiros a,b tais que
ax + bn = 1.
Reduzindo essa igualdade módulo n, o termo bn some, ficando
ax \equiv 1 \pmod{n}.
Então \bar a\in\mathbb{Z}_n satisfaz \bar a\cdot\bar x=\overline{1}. Logo \bar x é invertível em \mathbb{Z}_n, com inverso \bar y=\bar a.

Resposta

Mostramos que \bar x tem inverso em \mathbb{Z}_n se, e somente se, \gcd(x,n)=1.

Exercícios relacionados