1.4 Congruencias

\( \newcommand{\Implies}{\Rightarrow} \newcommand{\Iff}{\Leftrightarrow} \renewcommand{\emptyset}{\varnothing} \newcommand{\powersetsym}{\mathcal{P}} \newcommand{\fto}{\rightarrow} \newcommand{\mto}{\mapsto} \newcommand{\Cx}{\mathbb{C}} \newcommand{\R}{\mathbb{R}} \newcommand{\N}{\mathbb{N}} \newcommand{\Ns}{\mathbb{N}^*} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\K}{\mathbb{K}} \newcommand{\vv}[1]{\boldsymbol{#1}} \newcommand{\Abs}[1]{\left\lvert#1\right\rvert} \newcommand{\norm}[1]{ \left\|#1\right\| } \newcommand{\pnorm}[1]{\left\|#1\right\|_p} \newcommand{\supnorm}[1]{\left\|#1\right\|_\infty} \newcommand{\innerprod}[1]{\left\langle #1\right\rangle} \newcommand{\Ceil}[1]{\left\lceil #1\right\rceil} \newcommand{\Floor}[1]{\left\lfloor #1\right\rfloor} \newcommand{\Conj}[1]{\overline{#1}} \newcommand{\arccot}{\mathop{\text{arc\,cot}}\nolimits} \newcommand{\arcsec}{\mathop{\text{arc\,sec}}\nolimits} \newcommand{\arccsc}{\mathop{\text{arc\,csc}}\nolimits} \renewcommand{\arg}{\mathop{\text{arg}}\nolimits} \newcommand{\mcd}[1]{\mathop{\text{mcd}}\left(#1\right)} \newcommand{\mcm}[1]{\mathop{\text{mcm}}\left(#1\right)} \renewcommand{\ker}{\mathop{\text{ker}}\nolimits} \newcommand{\grad}{\mathop{\text{grad}}\nolimits} \newcommand{\dom}{\mathop{\text{dom}}\nolimits} \newcommand{\rng}{\mathop{\text{ran}}\nolimits} \newcommand{\diam}{\mathop{\text{diam}}\nolimits} \newcommand{\Obj}{\mathop{\text{obj}}\nolimits} \newcommand{\Hom}{\mathop{\text{hom}}\nolimits} \newcommand{\End}{\mathop{\text{end}}\nolimits} \newcommand{\Aut}[1]{\mathop{\mathrm{aut}}\nolimits(#1)} \newcommand{\Inn}[1]{\mathop{\mathrm{int}}\nolimits(#1)} \newcommand{\Deg}{\mathop{\mathrm{grad}}\nolimits} \newcommand{\Img}{\mathop{\text{im}}\nolimits} \newcommand{\Id}{\mathop{\mathrm{id}}\nolimits} \newcommand{\sgn}{\mathop{\mathrm{sgn}}\nolimits} \renewcommand{\Re}{\mathop{\mathrm{Re}}\nolimits} \renewcommand{\Im}{\mathop{\mathrm{Im}}\nolimits} \newcommand{\Char}{\mathop{\mathrm{car}}\nolimits} \renewcommand{\mod}[1]{\mathop{(\mathop{\text{mód}}\nolimits #1)}} \newcommand{\res}{\mathop{\text{mód}}} \newcommand{\categof}[1]{\mathsf{#1}} \newcommand{\CC}{\categof{C}} \newcommand{\CONJ}{\categof{Conj}} \newcommand{\SET}{\categof{Set}} \newcommand{\GRP}{\categof{Grp}} \newcommand{\AGRP}{\categof{Ab}} \newcommand{\morph}[1]{\mathrel{\mathop{\longrightarrow}\limits^{#1}}} \newcommand{\subgr}{\leq} \newcommand{\nsubgr}{\mathrel{\unlhd}} \newcommand{\iso}{\cong} \newcommand{\genby}[1]{\left\langle #1\right\rangle} \newcommand{\symgr}[1][n]{S_{#1}} \newcommand{\GenOf}[1]{\mathop{\text{gen}}\left(#1\right)} \newcommand{\normalizer}[2][G]{{\mathbf N}_{#1}(#2)} \newcommand{\centralizer}[2][G]{{\mathbf C}_{#1}(#2)} \newcommand{\orbit}[2][G]{\mathcal{O}_{#1}(#2)} \newcommand{\stab}[2][G]{#1(#2)} \newcommand{\GL}[2][n]{\mathrm{GL}(#1,#2)} \newcommand{\SL}[2][n]{\mathrm{SL}(#1,#2)} \newcommand{\Ort}[2][n]{\mathrm{O}(#1,#2)} \newcommand{\SO}[2][n]{\mathrm{SO}(#1,#2)} \newcommand{\KleinV}{\mathbf{V}}\)

1.4 Congruencias

Definición 1.36. Sea \(n\) un entero positivo. Decimos que dos enteros \(x\) y \(y\) son congruentes módulo \(n\) si \(x\) y \(y\) dejan el mismo residuo al ser divididos por \(n\). Para indicar esto, escribimos \[ x\equiv y\mod n. \]

La definición anterior motiva el uso de la notación \(x\res n\) para referirnos al residuo que deja \(x\) al ser divido por \(n\). Así, tenemos que \[ x\equiv y\mod n\qquad \text {si y sólo si}\qquad x\res n = y\res n. \]

La proposición siguiente nos da una caracterización alternativa de la relación de congruencia.

Demostración: Sean \(x\equiv y\mod n\). Entonces \(x = qn + r\) y \(y = q'n + r\), así que \(x - y = (q - q')n\) y por lo tanto \(n\mid (x - y)\). Recíprocamente, sea \(x - y\) divisible entre \(n\). Sean \(q,q',r,r'\) los enteros tales que \(x = qn + r\) y \(y = q'\) con \(0\leq r,r' < n\). Supongamos, sin pérdida de generalidad, que \(r\leq r'\). Puesto que \[ x - y = (q - q')n + (r - r'),\qquad 0\leq r - r' < r < n, \] las diferencias \(q - q'\) y \(r - r'\) han de ser el cociente y el residuo de dividir \(x - y\) entre \(n\), respectivamente. Pero como \(n\mid (x - y)\), tenemos \(r - r' = 0\), luego \(r = r'\) y por lo tanto \(x\equiv y\mod n\).

Demostración: Sean \(x \equiv x'\mod n\) y \(y\equiv y'\mod n\), o sea que \(x - x'\) y \(y - y'\) son divisibles entre \(n\). (1) Puesto que \[ (x + y) - (x' + y') = (x - x') + (y - y'), \] la diferencia del miembro izquierdo es divisible entre \(n\) y por lo tanto \(x + y\equiv x' + y'\mod n\).

(2) Tenemos \[ xy - x'y' = xy - xy' + xy' - x'y' = x(y - y') + y'(x - x'), \] lo que muestra que \(xy - x'y'\) ha de ser divisible entre \(n\), y así \(xy\equiv x'y'\mod n\).

(3) Se deduce de (2) y el principio de inducción matemática.

Como caso particular de la proposición anterior, tenemos que si \(x\equiv y\mod n\), entonces \(a + x\equiv y + a\mod n\) y \(ax\equiv ay\mod n\) para cualquier entero \(a\in \Z \).

Solución: donde \(d\) es el último dígito de \(x^n\) (leyendo de izquierda a derecha), es decir, el dígito de las unidades de \(x\). Por lo tanto, nosotros tenemos que \[ r\equiv 7^{26357296}\mod {10}. \] Observemos que \(7^4 = 2401\equiv 1\mod {10}\) y que \(26357296 = 4(6589324)\), de manera que, por la teorema 1.40,

\begin {align*} d & = 7^{26357296}\res 10 \\ & = 7^{4(6589324)}\res 10 \\ & = 1^{6589324}\res 10 \\ & = 1\res 10 \\ & = 1. \end {align*}

Así pues, el último dígito de \(8569451217^{26357296}\) es 1.

La proposición siguiente es una formulación del teorema 1.20 en términos de congruencias:

Demostración: \(ax \equiv 1\mod n\) si y sólo si existe un entero \(k\) tal que \(ax - 1 = kn\), o sea, tal que \(ax + (-kn) = 1\), así que la proposición se sigue del teorema 1.20.

Si \(x\) es tal que \(ax\equiv 1\mod n\), decimos que \(x\) es el “recíproco”, o “inverso”, de \(a\) módulo \(n\), y podemos expresar la afirmación de la proposición anterior diciendo que un entero \(a\) tiene “recíprocos” módulo \(n\), o que es “invertible” módulo \(n\), si y sólo si \(a\) es primo relativo de \(n\).

Pasemos ahora a un resultado de suma importancia en la teoría de números y sus aplicaciones.

Teorema 1.43 (Teorema Chino del Residuo). Si \(n_1,\ldots ,n_k\) son números enteros primos relativos dos a dos y \(a_1,\ldots ,a_k\) son enteros cualesquiera, entones existe un solución \(x\) al sistema de congruencias

\begin {eqnarray*} x &\equiv & a_1\mod {n_1},\\ &\vdots &\\ x &\equiv & a_k\mod {n_k}. \end {eqnarray*}

Más aún, \(x'\) es otra solución al sistema si y sólo si \(x'\equiv x\mod N\), donde \(N = \prod _{i=1}^n n_i\).

Pasemos ahora a estudiar congruencias de potencias primas de enteros. Necesitaremos los hechos siguientes.

Proposición 1.44. Si \(p\) es un número primo, entonces \(p\mid \binom {p}{k}\) para \(0 < k < p\).

Demostración: Tenemos que \(\binom {p}{k} = \frac {p!}{k!(p-k)!}\), o sea, \[ p! = k!(p-k)!\binom {p}{k}. \] Vemos entonces que \(p\) divide al miembro derecho, pero como los factores de \(k!(p-k)!\) son todos menores que \(p\), debemos concluir que \(p\) divide a \(\binom {p}{k}\).

Demostración: Sea \(N = \prod _{i=1}^n n_i\) y definamos \(N_i = N/n_i\). Que los enteros \(n_i\) son todos primos relativos dos a dos significa que \(\mcd {n_i,n_j} = 1\) cuando \(i\neq j\), lo que implica \(\mcd {n_i,N_i} = 1\), luego existe un \(s_i\) tal que \(s_iN_i \equiv 1\mod {n_i}\). Por otra parte, \(n_i\mid N_j\) cuando \(i\neq j\), o sea que \(s_iN_j\equiv 0 \mod {n_i}\). Con esto tenemos que, para todo \(j = 1,\ldots ,k\), \[ x = \left ( \sum _{i=1}^k (s_iN_i)a_i \right )\res n_j = \sum _{i=1}^k ((s_iN_i)a_i\res n_j) = a_j\res n_j. \] Así, \(x\) es una solución al sistema de congruencias planteado.

Puesto que los enteros \(n_i\) son primos relativos dos a dos, la generalización de la teorema 1.35 a \(k\) factores nos dice que \(n_i\mid (x - a_i)\) si y sólo si \(N\mid (x - a_i)\) para todo \(i=1,\ldots ,k\). En otras palabras, \(x\equiv a_i\mod {n_i}\) si y sólo si \(x\equiv a\mod N\), así que \(x'\) es una solución al sistema de congruencias si y sólo si \(x'\equiv x\equiv a_i\mod N\).

Demostración: Observemos primero lo siguiente: si \(p^n\mid ab\) pero \(p^n\nmid a\), entonces \(p\mid b\), pues en ese caso \(a\) es de la forma \(a = p^m x\) con \(0 \leq m < n\) y por tanto \(p^{n - m}\mid (a/p^m)b\), y como \(p\) divide a \(p^{n-m}\) pero no divide a \(a\), debe ser \(p\mid a\). De esta manera, como \[ p^n! = \binom {p^n}{k}k!(p^n - k)!, \] tenemos que \(p^n\) divide al miembro derecho pero no a \(k!(p^n - k)!\) porque consiste de factores menores que \(p^n\) al ser \(0 < k < p^n\), así que \(p\) debe dividir a\(\binom {p^n}{k}\).

Teorema 1.46. Si \(p\) es primo y \(x,y\) enteros cualesquiera, entonces \[ (x + y)^{p^n} \equiv x^{p^n} + y^{p^n} \mod p \] para cualquier entero \(n \geq 0\). En particular, \[ (x + y)^{p} \equiv x^{p} + y^{p} \mod p. \]

Demostración: Por el teorema binomial, \[ (x + y)^{p^n} = x^{p^n} + \binom {p^n}{1}x^{p^n-1}y + \binom {p^n}{2}x^{p^n-2}y^2 + \cdots + y^{p^n}, \] y por la proposición anterior \(p\) divide a cada término entre \(x^{p^n}\) y \(y^{p^n}\), o sea que el residuo de dividir \((x + y)^{p^n}\) entre \(p\) es \(x^{p^n} + y^{p^n}\).

Demostración: Por la teorema 1.40, basta probarlo por inducción sobre \(x\geq 0\), el caso base \(x = 0\) siendo obvio. Supongamos la congruencia cierta para un entero \(x\geq 0\). Entonces \(x^{p^n} + 1\equiv x + 1\mod p\), pero \(x^{p^n} + 1\equiv (x + 1)^{p^n}\) por la proposición anterior.