\[
n\mid (a-b),\quad a\equiv b\pmod n, \quad \cl a=\cl
b
\]
têm o mesmo significado.
Considere por exemplo o caso $n=10$ e seja $\cl a=\cl 3\in\Z_{10}$. Observando que $\cl 3\cdot \cl 7=\cl 1$, podemos concluir que o elemento $\cl a=\cl 3$ possui inverso multiplicativo em $\Z_{10}$. Neste caso escrevemos que $\cl 3^{-1}=\cl 7$ e $\cl 7^{-1}=\cl 3$. Será que todo elemento não nulo possui tal inverso multiplicativo? Considere por exemplo o elemento $\cl a=\cl 2\in\Z_{10}$. Se existisse $\cl b\in\Z_{10}$ tal que $\cl 2\cdot \cl b=\cl 1$, então isso significaria que
\[
10\mid (2b-1).
\]
No entanto é fácil observar que esta divisibilidade não pode ser possível para nenhum $b$, pois $2b$ é um número par, que diz que $2b-1$ é ímpar, e portanto não pode ser divisível por $10$.
\[
3\cdot x\equiv 8\pmod{10}.
\]
Esta congruência é equivalente à seguinte equação em $\Z_{10}$:
\[
\cl 3\cl x=\cl 8.
\]
Sabe-se que $\cl 3\cdot\cl 7=\cl 1$ em $\Z_{10}$ portanto esta equação pode ser resolvido por multiplicar os dois lados da equação por $\cl 7$:
\[
\cl x=\cl 7\cdot\cl 8=\cl 6.
\]
Obtemos então que as soluções da congruência original são números inteiros $x\in\Z$ tal que $\cl x=\cl 6$; ou seja $x\equiv 2\pmod {10}$.
\[
ua+vn=1.
\]
Traduzindo esta equação para a estrutura $\Z_n$, isto quer dizer que
\[
\cl 1 =\cl{ua+vb}=\cl u\cl a+\cl v\cl n=\cl u\cl a+\cl v\cl 0=\cl u\cdot \cl a.
\]
Ou seja, $\cl u$ é inverso de $\cl a$ em $\Z_n$.
Por outro lado, se existe $b\in\Z$ tal que $\cl b\cl a=\cl 1$, então $n\mid (ab- 1)$ que implica que existe $q\in \Z$ tal que
\[
ab-1=qn.
\]
Isto é equivalente a equação diofantina
\[
ab-qn=1
\]
nas variáveis $b$ e $q$. A existência do inverso $\cl b$ implica que esta equação possui soluções e segue pelo resultado na aula anterior,que $\mbox{mdc}(a,n)=1$.
Note que a demonstração acima é construtiva no sentido que mostra como achar o inverso de $\cl a\in \Z_n$ caso $\mbox{mdc}(a,n)=1$.
Denotemos por $U(n)$ o conjunto das classes residuais invertíveis em $\Z_n$. Pelo resultado anterior
\begin{eqnarray*}
U(n)&=&\{\cl a\mid a\in\{0,\ldots,n-1\},\ \mbox{$\cl a$ é invertível em $\Z_n$}\}\\&=&
\{\cl a\mid a\in\{0,\ldots,n-1\}\mbox{ com mdc}(a,b)=1\}.
\end{eqnarray*}
- $\cl 0\not\in U(n)$;
- $\cl 1\in U(n)$;
- $\cl{-1}=\cl{n-1}\in U(n)$;
- se $\cl a,\cl b\in U(n)$, então $\cl a\cdot\cl b\in U(n)$;
- se $\cl a\in U(n)$, então $(\cl a)^{-1}\in U(n)$;
- se $n$ é um primo, então todo elemento não nulo de $U(n)$ é invertível.
Um elemento $\cl a\in\Z_n$ chama-se quadrado (ou às vezes resíduo quadrático) se existe $\cl b\in\Z_n$ tal que $\cl b^2=\cl a$.
\[
3x^2\equiv 7\pmod {11}.
\]
Esta congruência pode ser escrita como a equação em $\Z_{11}$
\[
\cl 3\cl x^2=\cl 7.
\]
Temos que $\cl 3^{-1}=4$ e multiplicando os dois lados da equação por $\cl 4$ obtemos que
\[
\cl x^2=\cl 6.
\]
Como $\cl 6$ não é um quadrado em $\Z_{11}$, obtemos que esta equação não possui solução e a congruência original também não possui solução.