Aritmética modular

$\newcommand{\Z}{\mathbb Z}\newcommand{\cl}[1]{\overline{#1}}$Sejam $a$ e $b$ números inteiros e seja $n$ um natural com $n\geq 2$. Dizemos que $a$ é congruente com $b$ módulo $n$ se $n\mid (a-b)$. Neste caso escrevemos que
\[
a\equiv b\pmod n.
\]
Por exemplo, $-2\equiv 3\pmod 5$, mas $2\not\equiv 3\pmod 5$.

Note que $a\equiv b\pmod n$ se e somente se os restos de $a$ e $b$ quando divididos por $n$ são iguais.

Seja $n\geq 2$ fixo. Dado $a\in\Z$, denote por $\cl a$ o conjunto de números inteiros que são congruentes com $a$. Em símbolos,
\[
\cl a=\{b\in \Z\mid b\equiv a\bmod n\}.
\]
O conjunto $\cl a$ é chamado de classe residual módulo $n$.
Por exemplo, se $n=5$, temos que
\begin{eqnarray*}
\cl 0&=&\{0,\pm 5, \pm 10,\ldots\}=\{5k\mid k\in\Z\}\\
\cl 1&=&\{1,-4,6,-9,11,,\ldots\}=\{5k+1\mid k\in\Z\}\\
\cl 2&=&\{2,-3,7,-8,12,\ldots\}=\{5k+2\mid k\in\Z\}\\
\cl 3&=&\{3,-2,8,-7,13,\ldots\}=\{5k+3\mid k\in\Z\}\\
\cl 4&=&\{4,-1,9,-6,14,\ldots\}=\{5k+4\mid k\in\Z\}\\
\end{eqnarray*}
Observe que temos 5 classes residuais módulo 5; nomeadamente, $\cl 0$, $\cl 1$, $\cl 2$, $\cl 3$, $\cl 4$. Mais geralmente, módulo $n$ temos $n$ classes residuais: $\cl 0,\cl 1, \ldots,\cl{n-1}$. Se $a\in\Z$, então escrevemos $a=qn+r$ onde $0\leq r< n$ e a classe residual $\cl a$, pode ser escrita como
\[
\cl a=\{kn+r\mid k\in\Z\}.
\]

O conjunto de classes residuais módulo $n$ são denotados por $\Z_n$. Temos então que
\[
\Z_n=\{\cl 0,\cl 1,\ldots,\cl{n-1}\}.
\]
Em particular $|\Z_n|=n$.

Temos que $\cl a=\cl b$ se e somente se $a\equiv b\pmod n$ (ou seja, $n\mid (a-b)$) que equivale à condição que os restos de $a$ e $b$ quando divididos por $n$ são iguais.

Seja $n\geq 2$ fixo e escolha $\cl a,\cl b\in \Z_n$. Vamos definir as operações de adição é multiplicação entre estas classes:
\begin{eqnarray*}
\cl a+\cl b&=&\cl{a+b}\\
\cl a\cdot \cl b&=&\cl{ab}.
\end{eqnarray*}

Como as operações estão definidas usando representantes das classes, precisa-se provar que estas operações são bem definidas. Isso significa que tomemos $a_1,a_2,b_1,b_2\in\Z$ tais que $\cl{a_1}=\cl{a_2}$ e $\cl{b_1}=\cl{b_2}$ e precisa-se verificar que
\begin{eqnarray*}
\cl{a_1}+\cl{b_1}&=&\cl{a_2}+\cl{b_2}\\
\cl{a_1}\cdot\cl{b_1}&=&\cl{a_2}\cdot\cl{b_2}
\end{eqnarray*}
Verificaremos apenas o produto. Como $\cl{a_1}=\cl{a_2}$, temos que $n\mid (a_1-a_2)$ que implica que $a_2=a_1+k_an$, e similarmente, $b_2=b_1+k_bn$ onde $k_a,k_b\in\Z$. Então
\begin{eqnarray*}
\cl{a_2}\cdot\cl{b_2}&=&\cl{a_2b_2}=\cl{(a_1+k_an)(b_1+k_bn)}\\&=&\cl{a_1b_1+k_anb_1+k_bna_1+k_ak_bn^2}
\\&=&\cl{a_1b_1+n(k_ab_1+k_ba_1+k_ak_bn)}
\\&=&\cl{a_1b_1}=\cl{a_1}\cdot\cl{b_1}.
\end{eqnarray*}

Estas duas operações têm as seguintes propriedades para todo $\cl a,\cl b,\cl c\in\Z_n$ (a verificação é exercício):

1. A soma é associativa: $(\cl a+\cl b)+\cl c=\cl a+(\cl b+\cl c)$.
2. A soma é comutativa: $\cl a+\cl b=\cl b+\cl a$.
3. Existe um elemento neutro para a soma; nomeadamente, a classe $\cl 0$. De fato $\cl a+\cl 0=\cl 0+\cl a=\cl a$.
4. Toda classe $\cl a$ possui um simétrico (ou negativo); nomeadamente $\cl{-a}=\cl{n-a}$. De fato $\cl a+\cl{n-a}=\cl n=\cl 0$.
5. A produto é associativo: $(\cl a\cdot\cl b)\cdot\cl c=\cl a\cdot(\cl b\cdot\cl c)$.
6. A produto é comutativo: $\cl a\cdot\cl b=\cl b\cdot\cl a$.
7. Existe um elemento neutro para o produto; nomeadamente $\cl 1$. De fato $\cl a\cdot\cl 1=\cl 1\cdot\cl a=\cl a$.
8. Temos a propriedade distributiva $\cl a\cdot(\cl b+\cl c)=\cl a\cdot\cl b+\cl a\cdot \cl c$.

Isso quer dizer que aritmética em $\Z_n$ funciona mais ou menos na mesma maneira que em $\Z$.