Definición
Dados dos números \( a\) y \( b\), y un entero positivo \( n\), definimos \( a \equiv b \pmod n\) (léase: \( a\) congruente con \( b\) módulo \( n\)) si \( n\) divide a la diferencia \( a – b\). Por ejemplo: \( 7 \equiv 1 \pmod 6\) ya que \( 6\) divide a \( 7 – 1\); \( 0 \equiv 32 \pmod 4\) ya que \( 4\) divide a \( 0 – 32\); además, \( 21 \not\equiv 10 \pmod 5\) ya que \( 5\) no divide a \( 21 – 10\).
Propiedades de las Congruencias
- Si \( a \equiv 0 \pmod n\), entonces \( a\) es múltiplo de \( n\).
- Si \( a \equiv b \pmod n\), entonces \( a\) y \( b\) poseen el mismo residuo al dividir cada uno de ellos por \( n\).
- Si \( a \equiv b \pmod n\) y \( b \equiv c \pmod n\), entonces \( a \equiv c \pmod n\).
- Si \( a \equiv b \pmod n\), entonces \( (a + c) \equiv (b + c) \pmod n\) y \( ac \equiv bc \pmod n\).
- Si \( a \equiv b \pmod n\), entonces \( a/c \equiv b/c \pmod n\) si y sólo si el máximo común divisor entre \( c\) y \( n\) es \( 1\).
- Si \( a \equiv b \pmod n\), entonces \( ak \equiv bk \pmod n\) para \( k\) un entero positivo.
- Si \( p\) es un número primo y \( ab \equiv 0 \pmod p\), entonces \( a \equiv 0 \pmod p\) ó \( b \equiv 0 \pmod p\).