Congruências

Sejam $a, b, n \in {\mathbb{Z} }$. Dizemos que a é congruente a b módulo n, e escrevemos $a \equiv b \pmod n$, se n|b - a. Como a congruência módulo 0 é a igualdade e quaisquer inteiros são côngruos módulo 1, em geral estamos interessados em n > 1.

Proposição 1.7: Para quaisquer $a, a', b, b', c, n \in {\mathbb{Z} }$ temos:

(a)

$a \equiv a \pmod n$;

(b)

se $a \equiv b \pmod n$ então $b \equiv a \pmod n$;

(c)

se $a \equiv b \pmod n$ e $b \equiv c \pmod n$então $a \equiv c \pmod n$;

(d)

se $a \equiv a' \pmod n$ e $b \equiv b' \pmod n$então $a + b \equiv a' + b' \pmod n$;

(e)

se $a \equiv a' \pmod n$então $- a \equiv - a' \pmod n$;

(f)

se $a \equiv a' \pmod n$ e $b \equiv b' \pmod n$então $a \cdot b \equiv a' \cdot b' \pmod n$.

Dem: Para o item (a) basta observar que n | a - a = 0. Em (b), se n | b - a então n | a - b = -(b-a). Em (c), se n | b - a e n | c - b então n | c - a = (c - b) + (b - a). Em (d), se n | a' - a e n | b' - b então n | (a' + b') - (a + b) = (a' - a) + (b' - b). Em (e), se n | a' - a então n | (-a') - (-a) = -(a' - a). Em (f), se n | a' - a e n | b' - b então n | a'b' - ab = a'(b' - b) + b(a' - a).          $\blacksquare$

Os itens (a), (b) e (c) da proposição acima dizem, nesta ordem, que a relação $\equiv \pmod n$ (``ser côngruo módulo n'') é uma relação reflexiva, simétrica e transitiva. Relações satisfazendo estas três propriedades são chamadas relações de equivalência. Dada uma relação de equivalência $\sim$ sobre um conjunto Xe um elemento $x \in X$ definimos a classe de equivalência $\overline x$ de x como

$$\overline x = \{y \in X \vert y \sim x\};$$

observe que $x \sim y$ se e somente se $\overline x = \overline y$. As classes de equivalência formam uma partição de X, i.e., uma coleção de subconjuntos não vazios e disjuntos de X cuja união é X. O conjunto $\{ \overline x \vert x \in X \}$ das classes de equivalência é chamado o quociente de X pela relação de equivalência $\sim$e é denotado por $X/\sim$.

Aplicando esta construção geral ao nosso caso, definimos o quociente ${\mathbb{Z} }/(\equiv \pmod n)$, chamado por simplicidade de notação de ${\mathbb{Z} }/(n)$, ${\mathbb{Z} }/n{\mathbb{Z} }$ ou às vezes ${\mathbb{Z} }_n$. Dado $a \in {\mathbb{Z} }$, a definição de $\overline a$ como um subconjunto de ${\mathbb{Z} }$raramente será importante: o importante é sabermos que $\overline a = \overline{a'}$ se e somente se $a \equiv a' \pmod n$. Se n > 0, a divisão euclidiana diz que todo inteiro a é côngruo a um único inteiro a' com $0 \le a' < n$; podemos reescrever este fato na nosso nova linguagem como

$${\mathbb{Z} }/(n) = \{\overline 0, \overline 1, \ldots, \overline{n-1} \}.$$

Quando não houver possibilidade de confusão omitiremos as barras e chamaremos os elementos de ${\mathbb{Z} }/(n)$ simplesmente de $0, 1, \ldots, n-1$.

Os itens (d), (e) e (f) da proposição dizem que as operações de soma, diferença e produto são compatíveis com a relação de congruência. É esta propriedade que torna congruências tão úteis, nos possibilitando fazer contas módulo n. Podemos por exemplo escrever
$$\begin{align}196883 &= 1 \cdot 10^5 + 9 \cdot 10^4 + 6 \cdot 10^3 + 8 \cdot 10^2... ...9 + 6 + 8 + 8 + 3 \notag\\ &= 35 \notag\\ &\equiv 8 \pmod 9,\notag \end{align}$$
já que $10 \equiv 1 \pmod 9$(mostrando assim porque funciona o conhecido critério de divisibilidade por 9). Uma formulação mais abstrata da mesma idéia é dizer que as operações + e $\cdot$ passam ao quociente, i.e., que podemos definir

$$+: {\mathbb{Z} }/(n) \times {\mathbb{Z} }/(n) \to {\mathbb{Z}... ...\mathbb{Z} }/(n) \times {\mathbb{Z} }/(n) \to {\mathbb{Z} }/(n)$$

por $\overline a + \overline b = \overline{a+b}$ e $\overline a \cdot \overline b = \overline{a\cdot b}$. A dúvida à primeira vista seria se a escolha de a e b não afeta a resposta: afinal existem infinitos inteiros a' e b' com $\overline a = \overline{a'}$ e $\overline b = \overline{b'}$. Os itens (d) e (f) da proposição são exatamente o que precisamos: eles nos dizem que nestas condições $\overline{a+b} = \overline{a'+b'}$ e $\overline{a\cdot b} = \overline{a'\cdot b'}$.

Proposição 1.8: Sejam $a, n \in {\mathbb{Z} }$, n > 0. Então existe $b \in {\mathbb{Z} }$ com $ab \equiv 1 \pmod n$se e somente se (a,n) = 1.

Dem: Se $ab \equiv 1 \pmod n$ temos nk = 1 - ab para algum k, donde (a,n) | ab + nk = 1 e (a,n) = 1. Se (a,n) = 1 temos ax + ny = 1 para certos inteiros x e y, donde $ax \equiv 1 \pmod n$.          $\blacksquare$

Dizemos portanto que a é invertível ^1.1 módulo n quando (a,n) = 1e chamamos b com $ab \equiv 1 \pmod n$ de inverso de a módulo n. O inverso é sempre único módulo n: se $ab \equiv ab' \equiv 1 \pmod n$ temos $b \equiv ab^2 \equiv abb' \equiv b' \pmod n$.

Corolário 1.9: Se (a,n) = 1 e $ab \equiv ab' \pmod n$ então $b \equiv b' \pmod n$.

Dem: Basta escrever $b \equiv abc \equiv ab'c \equiv b' \pmod n$onde c é o inverso de a módulo n.          $\blacksquare$

Definimos $({\mathbb{Z} }/(n))^\ast \subset {\mathbb{Z} }/(n)$ por

$$({\mathbb{Z} }/(n))^\ast = \{ \overline a ; (a,n) = 1 \}.$$

Observe que o produto de elementos de $({\mathbb{Z} }/(n))^\ast$é sempre um elemento de $({\mathbb{Z} }/(n))^\ast$ (corolário 1.5).

Teorema 1.10: (Teorema Chinês dos restos) Se (m, n) = 1 então
$$\begin{align}f: {\mathbb{Z} }/(mn) &\to {\mathbb{Z} }/(m) \times {\mathbb{Z} }/(n) \notag\\ \overline a &\mapsto (\overline a, \overline a) \notag \end{align}$$
é uma bijeção. Além disso, a imagem por f de $({\mathbb{Z} }/(mn))^\ast$ é $({\mathbb{Z} }/(m))^\ast \times ({\mathbb{Z} }/(n))^\ast$.

Note que cada $\overline a$ na definição de fé tomado em relação a um módulo diferente. A função está bem definida pois $a \bmod mn$determina $a \bmod m$ e $a \bmod n$.

Dem: Como ${\mathbb{Z} }/(mn)$ e ${\mathbb{Z} }/(m) \times {\mathbb{Z} }/(n)$ têm mn elementos cada, para provar que f é bijetiva basta verificar que f é injetiva. E, de fato, se $a \equiv a' \pmod m$ e $a \equiv a' \pmod n$então m | (a - a') e n | (a - a'), donde mn | (a - a') e $a \equiv a' \pmod {mn}$. A imagem de $({\mathbb{Z} }/(mn))^\ast$ é $({\mathbb{Z} }/(m))^\ast \times ({\mathbb{Z} }/(n))^\ast$pois (a,mn) = 1 se e somente se (a,m) = (a,n) = 1.          $\blacksquare$

Dados inteiros $m_1, m_2, \ldots , m_r$, dizemos que estes inteiros são primos entre si se (m_i,m_j) = 1 para quaiquer $i \ne j$.

Corolário 1.11: Se $m_1, m_2, \ldots , m_r$ são inteiros primos entre si. Então
$$\begin{align}f: {\mathbb{Z} }/(m_1 m_2 \cdots m_r) &\to {\mathbb{Z} }/(m_1) \tim... ...ne a &\mapsto (\overline a, \overline a, \ldots, \overline a) \notag \end{align}$$
é uma bijeção.

Dem: Basta aplicar o teorema anterior r vezes.          $\blacksquare$

A aplicação mais comum deste teorema é para garantir que existe a com $a \equiv a_i \pmod {m_i}$ onde a_i são inteiros dados quaisquer.