Congruencias

Definición

Dados dos números $a$ y $b$, y un entero positivo $n$, definimos $a\equiv b(\mathrm{mod}n)$ (léase: $a$ congruente con $b$ módulo $n$) si $n$ divide a la diferencia $a–b$. Por ejemplo: $7\equiv 1(\mathrm{mod}6)$ ya que $6$ divide a $7–1$; $0\equiv 32(\mathrm{mod}4)$ ya que $4$ divide a $0–32$; además, $21\not\equiv 10(\mathrm{mod}5)$ ya que $5$ no divide a $21–10$.

Propiedades de las Congruencias

• Si $a\equiv 0(\mathrm{mod}n)$, entonces $a$ es múltiplo de $n$.
• Si $a\equiv b(\mathrm{mod}n)$, entonces $a$ y $b$ poseen el mismo residuo al dividir cada uno de ellos por $n$.
• Si $a\equiv b(\mathrm{mod}n)$ y $b\equiv c(\mathrm{mod}n)$, entonces $a\equiv c(\mathrm{mod}n)$.
• Si $a\equiv b(\mathrm{mod}n)$, entonces $(a+c)\equiv (b+c)(\mathrm{mod}n)$ y $ac\equiv bc(\mathrm{mod}n)$.
• Si $a\equiv b(\mathrm{mod}n)$, entonces $a/c\equiv b/c(\mathrm{mod}n)$ si y sólo si el máximo común divisor entre $c$ y $n$ es $1$.
• Si $a\equiv b(\mathrm{mod}n)$, entonces $ak\equiv bk(\mathrm{mod}n)$ para $k$ un entero positivo.
• Si $p$ es un número primo y $ab\equiv 0(\mathrm{mod}p)$, entonces $a\equiv 0(\mathrm{mod}p)$ ó $b\equiv 0(\mathrm{mod}p)$.