Teorema chino de los restos

ARITMÉTICA MODULAR

TEOREMA CHINO DE LOS RESTOS

ARITMÉTICA MODULAR

Empezamos recordando la relación de equivalencia

a ≡ b (mod n) ↔ a − b es múltiplo de n, siendo n, un número entero positivo.

Es fácil ver que esta relación de equivalencia puede reescribirse en la forma a ≡ b (mod n) ↔ el resto de la división euclídea de a y de b por n es el mismo.

De esta forma, es claroque se tienen n clases de equivalencia en el conjunto cociente que suele escribirse en la forma Zn, cada una de ellas correspondiente a uno de los posibles restos, es decir, 0, 1,. . ., n − 1. Es, de hecho, habitual identificar las clases de equivalencia con los citados números.

En el conjunto Zn se pueden definir dos operaciones, suma y producto, de la manera siguiente:

Si [pic] y [pic] sondos clases de equivalencia, se define [pic] + [pic] = [pic].
Si [pic] y [pic] son dos clases de equivalencia, se define [pic] · [pic] = [pic].

Tal y como hemos definido suma y producto, parece que dependen del representante elegido en cada clase. Sin embargo, esto no es cierto:

Proposición 1

Las operaciones suma y producto en Zn están bien definidas y dotan a Zn de estructura de anilloconmutativo con elemento identidad.

Observación 2
Una aplicación sencilla de las congruencias es la obtención de criterios de divisibilidad. Así, por ejemplo, podemos obtener un criterio para saber si un entero n es divisible por 11, sin realizar la división. Sea x = xnxn−1 . . . x2x1x0 un numero natural escrito en base diez, es decir,

x = xn · 10n + xn−1 · 10n−1 + · · · + x1 · 10 + x0 y0 ≤ xj ≤ 9, ( j E {0, . . . , n}

Como 10 ≡ −1 (mod 11), se tendrá que xi · 10i ≡ (−1)ixi (mod 11) y, por lo tanto,

[pic]

En consecuencia, x es divisible por 11 si, y solo si, [pic]
Es decir, si la suma de los dígitos que ocupan un lugar par menos la suma de los que ocupan un lugar impar es múltiplo de 11.
TEOREMA CHINO DE LOS RESTOS

Usando el algoritmo extendido deEuclides es fácil resolver congruencias del tipo
ax ≡ b (mod n),

Ya que dicha congruencia tiene solución si, y solo si, la ecuación Diofantica

ax + ny = b

Tiene solución. De hecho, se tiene:

Proposición 3

La congruencia ax ≡ b (mod n) tiene solución si, y solo si, d = mcd(a, n) divide a b. Además, si existe solución, esta es única módulo n/d.

Demostración.

Loúnico que debemos probar es que la solución es única moduló n/d.

Esto se deduce del hecho de que las soluciones de la ecuación Diofantica ax+ny = b son de la forma:

[pic]
Con t cualquier número entero y (x0, y0) una solución cualquiera de ax + ny =b.

¿Qué ocurre si no tengo una única congruencia, sino varias? La respuesta a esta pregunta viene dada por el conocido comoTeorema Chino de los Restos y su posterior extensión. El nombre del Teorema deriva del texto Suan–ching (“Aritmetica”)escrito por el matemático chino Sun–Tsu. Dentro de ese texto aparece la resolución del ejercicio siguiente:

¿Cuál es el numeró entero positivo mas pequeño tal que el resto de dividirlo por 11 es 2, el resto de dividirlo por 5 es 3 y el resto de dividirlo por 7 es 2?

Elproblema, trasladado al lenguaje de congruencias, es el de encontrar el menor entero positivo a tal que:

a ≡ 2 (mod 11), a ≡ 3 (mod 5), a ≡ 2 (mod 7).

Resolvamos el problema de Sun–Tsu. Si a ≡ 2 (mod 11), entonces a tiene la forma
a = 2 + 11t1 para algún entero t1.

Si exigimos que a ≡ 3 (mod 5), tendremos que 2 + 11t1 ≡ 3 (mod 5), es decir, t1 ≡ 1 (mod 5). Dicho de otramanera, t1 = 1 + 5t2 para algún entero t2, por lo que a tiene la forma
a = 13 + 55t2 para algún entero t2.
Finalmente, a debe verificar a ≡ 2 (mod 7), es decir, 13 + 55t2 ≡ 2 (mod 7). Por lo tanto, 6t2 ≡ 3 (mod 7) y, resolviendo esta congruencia, se tiene que t2 = 4 + 7t3 para algún entero t3. En definitiva, a debe tener la forma

a = 233 + 385t3 para algún entero t3....