Congruências

Referência : Tavares, J., Geraldo, A., (2017) Congruências, Rev. Ciência Elem., V5(1):070
Autor: João Nuno Tavares e Ângela Geraldo
Editor: José Ferreira Gomes
DOI: [https://doi.org/10.24927/rce2017.070]

Definição

Seja $m$ um inteiro positivo. Dois inteiros $a,b\in\mathbb{Z}$ dizem-se congruentes módulo $m$ se a diferença $a-b$ é um múltiplo inteiro de $m$:

Nesse caso escreve-se

Por exemplo

$19\equiv 5 \ \ (\mbox{mod}\ 7)$, porque $19-5=14$ é múltiplo inteiro de $7$.

$31\equiv -2 \ \ (\mbox{mod}\ 3)$, porque $31-(-2)=33$ é múltiplo inteiro de $11$.

$12\equiv 39 \ \ (\mbox{mod}\ 9)$, porque $12-39=-27$ é múltiplo inteiro de $9$.

$16\equiv -9 \ \ (\mbox{mod}\ 5)$, porque $16-(-9)=25$ é múltiplo inteiro de $5$.

Mas, por exemplo, $3$ não é congruente com $11$ $(\mbox{mod}\ 7)$, porque $3-11=-8$ não é múltiplo inteiro de $7$.

Propriedades

A propriedade seguinte será usada na dedução dos chamados critérios de divisibilidade.

Teorema

Dois inteiros $a,b\in\mathbb{Z}$ são congruentes módulo $m$ se e só se produzem o mesmo resto quando divididos por $m$.

Demonstração

Suponhamos que $a\equiv b \ \ (\mbox{mod}\ m)$, e que $a=qm+r$, com $q,r\in \mathbb{Z}$ e $0\leq r < m$. Então $a-b=km,\, k\in \mathbb{Z}$. Substituindo $a=qm+r$, vem que $b=a-km=qm+r-km=(q-k)m+r$, com $q-k\in \mathbb{Z}$ e $0\leq r <m$, o que significa que o resto da divisão de $b$ por $m$ também é $r$.

Reciprocamente, se $a=qm+r$ e $b=q'm+r$ com $q,q',r\in \mathbb{Z},\ 0\leq r < m$, então $b-a=q'm+r-qm-r=(q´-q)m$, o que significa que $a\equiv b \ \ (\mbox{mod}\ m)$, CQD.

Mais propriedades

• Sejam $d$, $n \in \mathbb{N}$ e $a$, $b \in \mathbb{Z}$. Temos que:

(i) $a \equiv a \quad (\mbox{mod} \ n)$;

(ii) se $a \equiv b \quad (\mbox{mod} \ n)$, então $b \equiv a \quad (\mbox{mod} \ n)$;

(iii) se $a \equiv b \quad (\mbox{mod} \ n)$ e $b \equiv c \quad (\mbox{mod} \ n)$, então $a \equiv c \quad (\mbox{mod} \ n)$;

(iv) se $a \equiv b \quad (\mbox{mod} \ n)$ e $d|n$ então $a \equiv b \quad (\mbox{mod} \ d)$.

Demonstração

(ii) Se $a \equiv b \quad (\mbox{mod} \ n)$ então $a-b=kn \, \Leftrightarrow \, a=b+kn$ com $k \in \mathbb{Z}$. Ora então $b-a=b-(b+kn)=-kn$, ou seja, $b-a$ é um mútiplo inteiro de $n$ e portanto $b \equiv a \quad (\mbox{mod} \ n)$.

(iii) Se $a \equiv b \quad (\mbox{mod} \ n)$ então $a-b=kn \, \Leftrightarrow \, a=b+kn$ com $k \in \mathbb{Z}$. Se $b \equiv c \quad (\mbox{mod} \ n)$ então $b-c=tn \, \Leftrightarrow \, c=b-tn$ com $t \in \mathbb{Z}$. Ora, $a-c=(b+kn)-(b-tn)=kn+tn=(k+t)n$, ou seja, $a-c$ é um múltiplo inteiro de $n$, isto é, $a \equiv c \quad (\mbox{mod} \ n)$.

(iv) Se $a \equiv b \quad (\mbox{mod} \ n)$ então $a-b=kn$ com $k \in \mathbb{Z}$. Ora, se $d|n$ podemos escrever $n=td$ com $t \in \mathbb{Z}$. Temos então que $a-b=kn=k(td)=(kt)d$, como $kt$ é um número inteiro, concluímos que $a-b$ é um múltiplo inteiro de $d$, ou seja, $a \equiv b \quad (\mbox{mod} \ d)$.

• Seja $n \in \mathbb{N}$ e sejam $a$, $b$, $c$ e $d \in \mathbb{Z}$. Temos que:

(v) se $a \equiv b \quad (\mbox{mod} \ n)$ e $c \equiv d \quad (\mbox{mod} \ n)$, então $a+c \equiv b+d \quad (\mbox{mod} \ n)$;

(vi) se $a \equiv b \quad (\mbox{mod} \ n)$ e $c \equiv d \quad (\mbox{mod} \ n)$, então $ac \equiv bd \quad (\mbox{mod} \ n)$.

Demonstração

(v) Sejam $r$ e $s$ inteiros tais que, $a-b=rn$ e $c-d=sn$. Então, $(a+c)-(b+d)=(a-b)+(c-d)=rn+sn=(r+s)n$, isto é, $(a+c)-(b+d)$ é um múltiplo inteiro de $n$ e portanto $a+c \equiv b+d \quad (\mbox{mod} \ n)$.

(vi) Observemos que $ac-bd=ac-bc+bc-bd=(a-b)c+(c-d)b=rnc+snb=(rc+sb)n$, ou seja, $ac-bd$ é um múltiplo inteiro de $n$ e então $ac \equiv bd \quad (\mbox{mod} \ n)$.