Propiedades Basicas

Gauss introdujo en concepto de congruencias en su famoso libo de Disquisisiones Aritméticas.

Definición: Sea $n$ un entero positivo fijo. Los enteros $a,b$ son congruentes módulo $n$, cosa que denotaremos por

(1)
\begin{align} a \equiv b \pmod n \end{align}

si $n\mid a-b$.
Si $n\nmid (a-b)$ entonces decimos que $a$ es incongruente a $b$ módulo $n$ y lo denotamos por $a\not\equiv b \pmod n$.

Nota:

  • Cualesquiera dos enteros son congruentes módulo 1.
  • Dos enteros son congruentes módulo 2 si y sólo sí ambos números tienen la misma paridad.
  • Por el algoritmo de la división $a =nq+r$ y entonces $a \equiv r \pmod n$, es decir, todo entero es congruente a su residuo al ser dividido por $n$ (módulo $n$).

La última observación merece más atención. Al dividir módulo $n$ los residuos posibles son $0, 1, \ldots, (n-1)$ y entonces todo entero es congruente a uno y sólo uno de estos residuos posibles módulo $n$. En particular $a\equiv 0 \pmod n$ si y sólo si $n\mid a$.

Definición: El conjunto $0,1,2,\ldots, n-1$ es llamado un juego reducido de residuos módulo $n$. En general a un conjunto $a_1, a_2, \ldots, a_n$ de enteros tal que todo entero $a$ es congruente a uno y sólo uno de los $a_i$'s es llamado un juego completo de residuos módulo $n$.

Por ejemplo $-12, -4,11,13,22,82,91$ es un juego completo de residuos módulo 7.

Teorema: Dos enteros arbitrarios $a,b$ son congruentes módulo $n$, esto es $a \equiv b \pmod n$, si y sólo si $a$ y $b$ dejan el mismo residuo positivo al ser divididos por $n$.

Por ejemplo $-56 \equiv -11 \pmod 9$ pues al ser divididos entre 9 dejan el mimo residuo 7.

Teorema: Sea $n>0$ un entero fijo y sean $a,b,c,d$ enteros arbitrarios. Entonses las siguientes propiedades se cumplen:

  1. $a\equiv a \pmod n$.
  2. Si $a\equiv b \pmod n \Rightarrow b\equiv a \pmod n$.
  3. Si $a\equiv b \pmod n \land b\equiv c \pmod n \Rightarrow a \equiv c \pmod n$.
  4. Si $a \equiv b \pmod n \land c\equiv d \pmod n \Rightarrow a+c \equiv b+d \pmod n$ y $ac \equiv bd \pmod n$.
  5. Si $a\equiv b \pmod n \Rightarrow a+c \equiv b+c \pmod n \land ac\equiv bc \pmod n$.
  6. Si $a \equiv b \pmod n \Rightarrow a^k \equiv b^k \pmod n$ para todo entero positivo $n$.

Ejemplo: Demostremos que $41 \mid 2^{20}-1$. En efecto, notemos que $2^5\equiv =9 \pmod 41$—-

Ejercicio: Encuentra el residuo al dividir $\sum_{k=1}^{100} k!$ al ser dividido entre 12.

Notemos que el converso del resultado $a\equiv b \pmod n \Rightarrow ac \equiv bc \pmod n$ no es verdadero, en efecto $2(4) \equiv 2(1) \pmod 6$ sin embargo $4\not\equiv 1 \pmod 6$. Es decir las leyes de cancelación no son verdaderas (en general) en congruencias. Sin embargo tenemos el siguiente resultado:

Teorema: Si $ac\equiv bc \pmod n$ entonces $a\equiv b \pmod{n/d}$ con $d=(n,c)$.

Corolario: Si $ac\equiv bc \pmod n$ y $(n,c)=1$ entonces $a\equiv b \pmod n$.

Notar la versión de este corolario cuando $n=p$ es un número primo.

Ejemplo: Tenemos que $33 \equiv 15 \pmod 9$ que implica que $11\equiv 5 \pmod 3$. Así mismo $-35 \equiv 45 \pmod 8$ y por lo tanto $-7 \equiv 9 \pmod 8$.

Notemos que también tenemos que si $ab\equiv 0 \pmod n$ entonces NO podemos conluir que alguno de los enteros $a \lor b$ sea congruente a cero módulo $n$.

Pruebas de Divisibilidad

Una de las aplicaciones más interesantes de la teoría de congruencias es la de encontrar criterios para determinar cuándo un número divide a otro. Estas pruebas de divisibilidad dependen en el sistema numérico posicional que se usa, en concreto usamos que todo número lo escribimos en base 10,.

Dado un entero $b>1$ fijo, todo entero positivo $N$ puede ser escrito de forma única en términos de las potencias de $b$ como:

(2)
\begin{align} N =a_mb^m + a_{m-1}b^{m-1} + \cdots + a_1b_1 + a_0. \end{align}

con los $a_i$ enteros entre $0$ y $b-1$.

Por el algoritmo de la división sabemos que existen enteros $q_1, a_0$ tal que $N=q_1b+a_0$ con $0\le a_0<b$. Si $q_1 \ge b$ entonces podemos dividir una vez más para obtener

(3)
\begin{align} q_1=q_2b+a_1 \qquad 0\le a_1<b. \end{align}

Al substituir $q_1$ en la primera ecuación obtenemos:

(4)
\begin{equation} N=q_2b^2 +a_1b+a_0. \end{equation}

Nosotros podemos continuar con este proceso siempre que $q_2>b$ y obtener $N=q_3b^3+a_2b^2+a_1b+a_0$.

Como $N>q_1>q_2>\cdots \ge 0$ es una sucesión estrictamente decreciente de enteros, sabemos que este proceso tiene que terminar, digamos, en el paso $(m-1)$ con $q_{m-1}=q_mb+a_{m-1}$ y $0\le a_{m-1} <b$ y $0\le q_m <b$. Poniendo $a_m=q_m$ obtenemos la representación

(5)
\begin{align} N=a_mb^m a_{m-1}b^{m-1}+\cdots+a_1b+a_0 \end{align}

deseada.
Proposición: La representación anterior de $N$ (en base $b$) es única.

Demostración: Si suponemos que tenemos dos representaciones

(6)
\begin{align} N=a_mb^m + \cdots a_0 = c_mb^m +\cdots + c_1b_1 + c_0 \end{align}

entonces al substraer la segunda representación de la primera obtenemos una representación:
$0= d_b b^m + \cdots + d_1b + d_0$ con $d_i = a_i -c_i$. Si las dos representaciones son diferentes, entonces existe un $i$ tal que $d_i\ne 0$ y por el principio del buen orden existe uno de estos indices menor, sea $k$ el menor de los índices tal que $d_k\ne 0$. Entonces

(7)
\begin{align} 0= d_mb^m +\cdots + d_kb^k \end{align}

y si dividimos por $b^k$ obtenemos que:

(8)
\begin{align} d_k= -b(d_mb^{m-k-1} + \cdots + d_{k+1}). \end{align}

y entonces $b\mid d_k$ lo que implica que $d_k = 0$ generando una contradicción. Por lo tanto la representación de $N$ es única.

Tenemos entonces que $N$ está completamente determinado por la sucesión de enteros $a_m,a_{m-1}, \cdots, a_1,a_0$ que aparecen como coeficientes en la representación de $N$ como suma de potencias de $b$. Podemos entonces escribir a $N$ en sistema posicional base $b$ como:

(9)
\begin{align} N=(a_ma_{m-1}\cdots a_2a_1a_0)_b. \end{align}

Cuando $b=2$ obtenemos el sistema de números binarios en el que todo entero puede ser representado con puros 0's y 1's. Por ejemplo:

(10)
\begin{equation} 105 = (1101001)_2 \end{equation}

y por otro lado $(1001111)_2 = 79$.

Nosotros usualmente escribimos a los números en base 10 (el sistema decimal) en el que por ejemplo 2014 = 2(10^3) + 0(10^2)+1(10) + 4. Los enteros 2,0,1,4, son llamados los dígitos (de los millares, centenas, decenas e unidades).

Teorema: Sea $P(x) = \sum_{k=0}^m c_k x^k$ una función polinomial en la variable $x$ con coeficientes enteros $c_k$. Si $a\simeq b \pmod n \Rightarrow P(a)\simeq P(b) \pmod n$.

Decimos que un entero $a$ es una solución de la congruencia $P(x)\equiv 0 \pmod n$ si $P(a)\equiv 0 \pmod n$.

Corolario: Si $a$ es una solución de $P(x)\equiv 0 \pmod n$ y $a\equiv b$ entonces $b$ es también una solucion de la congruencia.

Aplicación 1 (Criterio de divisibilidad por 9): Un entero $N$ es divisible por $9$ si y sólo si la suma de sus dígitos (en base 10) es divisible por 9.

Aplicación 2 (Criterio de divisibilidad por 11): Un número $N$ es divisible por 11 si sólo si la suma alternada de sus digitos es divisible por 11.

Ejemplo : 1,571,724 es divisilbe por 9 y por 11 y por lo tanto divisible por 99.

Si no se indica lo contrario, el contenido de esta página se ofrece bajo Creative Commons Attribution-ShareAlike 3.0 License