1.20: Más propiedades de congruencias

En este capítulo introducimos una idea importante en el trabajo con congruencias. Tendrá consecuencias útiles e ilustrará otra razón por la que el Lema de Bezout es importante. Lo introducimos con un teorema.

Teorema \(\PageIndex{1}\)

Vamos\(m \ge 2\). Si\(a\) y\(m\) son relativamente primos, entonces existe un entero único\(a^\ast\) tal que\(aa^\ast\equiv1\pmod m\) y\(0 < a^\ast < m\).

Ejemplo\(\PageIndex{1}\)

Cuando\(m=9\), los valores relativamente primos para\(a\) son\(1,2,4,5,7,8\). En efecto, observe que

\(1 \cdot 1 \equiv 1 \pmod 9\),		\(2 \cdot 5 \equiv 1 \pmod 9\),
\(4 \cdot 7 \equiv 1 \pmod 9\),		\(8 \cdot 8 \equiv 1 \pmod 9\).

De ahí\[1^* = 1, \qquad 2^* = 5, \qquad 4^*=7, \qquad 5^*=2, \qquad 7^* = 4, \qquad 8^* = 8.\nonumber \]

Observe, también, que exigir que\(a\) sea relativamente primo a\(m\) es importante en este caso: tenga en cuenta que no\(a\) podría ser igual a 6, ya que\(\gcd(6,9) \neq 1\), y de hecho, cualquier múltiplo de 6 es congruente con\(0\)\(3\), o\(6\) módulo 9: no hay un entero\(6^*\) que produzca 1 (módulo 9) cuando\(6\) se multiplica por él.

Llamamos a\(a^\ast\) la inversa de\(a\) módulo\(m\). Tenga en cuenta que aquí elegimos no denotar\(a^\ast\) por\(a^{-1}\) (aunque podríamos) ya que esto podría causar cierta confusión. Por supuesto, si\(c \equiv a^\ast \pmod m\) entonces\(ac \equiv 1 \pmod m\) así no\(a^\ast\) es único a menos que lo especifiquemos\(0 < a ^\ast < m\).

Prueba de teorema\(\PageIndex{1}\)

Prueba

Si\(\gcd(a,m)=1\), entonces por Lema de Bezout existen\(s\) y\(t\) tal que\[as+mt=1.\nonumber \] De ahí\[as-1=m(-t),\nonumber \] eso es,\(m\mid (as-1)\) y así\(as\equiv 1\pmod m\). Vamos\(a^\ast=s \bmod m\). Entonces\(a^\ast \equiv s \pmod m\) así\(aa^\ast\equiv1\pmod m\) y claramente\(0 < a ^\ast < m\).

Para mostrar singularidad asumir que\(ac \equiv1\pmod m\) y\(0 < c < m\). Entonces\(ac \equiv aa^\ast \pmod m\). Entonces si multiplicamos ambos lados de esta congruencia a la izquierda por\(c\) y usamos el hecho que\(ca \equiv 1 \pmod m\) obtenemos\(c \equiv a^\ast \pmod m\). Del Ejercicio 1.17.5 se desprende que\(c = a^\ast\), y esto demuestra la singularidad.

OBSERVACIÓN\(\PageIndex{1}\)

De la prueba anterior vemos que el Método de Blankinship puede usarse para calcular la inversa de\(a\) cuando existe, pero para pequeños a menudo\(m\) podemos encontrar\(a^\ast\) por “adivinar y verificar”. Incluso podemos buscarlo sistemáticamente. Por ejemplo, si\(m=15\) tomar\(a=2\). Entonces podemos comprobar cada elemento\(0,1,2,\dotsc,14\):\[\begin{aligned} 2\cdot 0 &\not\equiv 1\pmod{15} \\ 2\cdot 1 &\not\equiv 1\pmod{15} \\ 2\cdot 2 &\not\equiv 1\pmod{15} \\ 2\cdot 3 &\not\equiv 1\pmod{15} \\ 2\cdot 4 &\not\equiv 1\pmod{15} \\ 2\cdot 5 &\not\equiv 1\pmod{15} \\ 2\cdot 6 &\not\equiv 1\pmod{15} \\ 2\cdot 7 &\not\equiv 1\pmod{15} \\ 2\cdot 8 &\equiv 1\pmod{15}\text{ since }15\mid (16-1).\end{aligned}\] Así podemos tomar\(2^\ast=8\).

El teorema nos\(\PageIndex{1}\) dice una manera de saber si\(a\) tiene un módulo inverso\(m\) —podemos verificar para ver si\(a\) y\(m\) son relativamente primos. Pero, ¿es necesario eso\(a\) y\(m\) ser primo relativo\(a\) para tener una inversa? Los siguientes resultados nos dan una respuesta.

Teorema \(\PageIndex{2}\)

Vamos\(m>0\). Si\(ab\equiv 1\pmod m\) entonces ambos\(a\) y\(b\) son relativamente primos para\(m\).

Prueba

Si\(ab\equiv 1\pmod m\), entonces\(m\mid (ab-1)\). Entonces\(ab-1=mt\) para algunos\(t\). De ahí que,\[ab+m(-t)=1.\nonumber \] por el Ejercicio 1.10.3, esto implica que\(\gcd(a,m)=1\) y\(\gcd(b,m)=1\), como se afirma.

Corolario \(\PageIndex{1}\)

El entero\(a\) tiene un módulo inverso\(m\) si y solo si\(a\) y\(m\) son relativamente primos.

Ahora que sabemos exactamente qué enteros tienen módulos inversos\(m\), veamos qué podemos hacer con los inversos. Primero, usémoslos en el siguiente teorema para “simplificar” una congruencia.

Teorema \(\PageIndex{3}\): Cancellation

Dejemos\(m>0\) y asumamos eso\(\gcd(c,m)=1\). Entonces\[\label{eq: thm18.3} ca\equiv cb\pmod m \quad \Rightarrow \quad a\equiv b\pmod m.\]

Si\(\gcd(c,m)=1\), hay un entero\(c^\ast\) tal que\(c^\ast c\equiv 1\pmod m\). Ahora desde\(c^\ast\equiv c^\ast\pmod m\) y\(ca\equiv cb\pmod m\) por Teorema 1.17.3,\[c^\ast ca\equiv c^\ast cb\pmod m.\nonumber \] Pero\(c^\ast c\equiv 1\pmod m\) así\[c^\ast ca\equiv a\pmod m\nonumber \] y\[c^\ast cb\equiv b\pmod m.\nonumber \] Por reflexividad y transitividad esto rinde\[a\equiv b\pmod m.\nonumber \]

Tenga en cuenta que en la prueba anterior “cancelamos” la\(c\) en la ecuación multiplicando por la inversa. Esto es muy similar a lo que sucede en cursos de matemáticas anteriores donde se resuelve\(2x = 6\) multiplicando ambos lados de la ecuación por\(1/2\) (el “inverso multiplicativo” de 2). La diferencia anterior es que estamos tratando congruencias, no ecuaciones, y cuando un entero tiene un módulo inverso\(m\), el inverso es otro entero, no una fracción. (Tenga en cuenta también que podríamos resolver dividiendo\(2x=6\) por 2; no dividimos cuando se trata de congruencias, sino que multiplicamos por inversas).

Ejemplo \(\PageIndex{2}\): Solve Congruences

A veces podemos resolver para un entero desconocido\(x\) en una congruencia. Por ejemplo, considere la congruencia\[7x \equiv 4 \pmod{25}.\nonumber \] ¿Podemos determinar cuál (s) entero (s)\(x\) puede (n) ser?

Ya que\(\gcd(7,25)=1\), Corolario\(\PageIndex{1}\) implica que 7 tiene un módulo inverso 25. En efecto, un poco de prueba y error lo demuestra\(7^* = 18\), ya que\(7 \cdot 18 = 126 \equiv 1 \pmod{25}\).

Ahora, como en la prueba del Teorema\(\PageIndex{3}\), usamos\(7^*\) para “cancelar” el 7 en la congruencia. Multiplicamos ambos lados por\(7^*\), es decir, por\(18\), y obtenemos lo siguiente:\[\begin{aligned} 18(7x)&\equiv 18(4) \pmod{25};\\ (18\cdot 7)x &\equiv 72 \pmod{25};\\ 1x &\equiv 22 \pmod{25}. \end{aligned}\] Vemos que\(x\) debe ser congruente con 22 módulo 25—así que\(x\) debe pertenecer al conjunto\[\{25q+22:q \in \mathbb{Z}\} = \{\dots,-28,-3,22,47,\dots\}.\nonumber \] Efectivamente, sustituyendo\(25q+22\) en por \(x\)en el lado izquierdo de la congruencia produce\[7(25q+22) = 175q + 154 = 25(7q + 6)+4,\nonumber \] y\(25(7q+6)+4\) es congruente con el\(4\) módulo 25 sin importar qué valor entero\(q\) tome. De ahí que cada número en\(\{25q+22:q \in \mathbb{Z}\}\) sea una solución a la congruencia\(7x \equiv 4 \pmod{25}\).

Aunque la ecuación\(\eqref{eq: thm18.3}\) anterior no es generalmente cierta cuando\(\gcd(c,m)>1\), sí tenemos los siguientes otros tipos de “cancelación”:

Teorema \(\PageIndex{4}\)

Si\(c>0\),\(m>0\) entonces\[a\equiv b\pmod m \quad \Leftrightarrow \quad ca\equiv cb\pmod{cm}.\nonumber \]

Ver Ejercicio\(\PageIndex{3}\).

Teorema\(\PageIndex{5}\)

Dejar\(m>0\) y dejar\(d=\gcd(c,m)\). Entonces\[ca\equiv cb\pmod m \quad \Rightarrow \quad a\equiv b\pmod{(m/d)}.\nonumber \]

Prueba

Ya\(d=\gcd(c,m)\) que podemos escribir\(c=d(\frac cd)\) y\(m=d(\frac md)\). Entonces\(\gcd(\frac cd,\frac md)=1\). Ahora reescribiendo\(ca\equiv cb\pmod m\) tenemos\[d\,\frac cd\,a\equiv d\,\frac cd\,b\pmod{d (m/d)}.\nonumber \] Desde\(m>0\)\(d>0\), así que por Teorema\(\PageIndex{4}\) tenemos\[\frac cd\,a\equiv\frac cd\,b\pmod{(m/d)}.\nonumber \] Ahora desde\(\gcd(\frac cd,\frac md)=1\), por Teorema\(\PageIndex{3}\)\[a\equiv b\pmod{(m/d)}.\nonumber \]

Terminamos este capítulo mencionando cómo\(m\) interactúa el concepto de módulo inverso con módulo de congruencia\(m\). Para ello, primero discutimos los mayores divisores comunes de\(m\) y números que son congruentes módulo\(m\).

Teorema \(\PageIndex{6}\)

Si\(m>0\) y\(a\equiv b\pmod m\) tenemos\[\gcd(a,m)=\gcd(b,m).\nonumber \]

Prueba

Ya\(a\equiv b\pmod m\) que tenemos\(a-b=mt\) para algunos\(t\). Para que podamos escribir\[a=mt+b \quad \text{and} \quad b=m(-t)+a.\nonumber \] Let\(d=\gcd(m,a)\) y\(e=\gcd(m,b)\). Desde\(e\mid m\) y\(e\mid b\), la primera ecuación anterior implica que\(e\mid a\), así\(e\) es un divisor común de\(m\) y\(a\). De ahí\(e\le d\). De la segunda ecuación vemos de manera similar eso\(d\le e\). Entonces\(d=e\).

Corolario\(\PageIndex{2}\)

Vamos\(m>0\). Vamos\(a\equiv b\pmod m\). Entonces\(a\) tiene un módulo inverso\(m\) si y solo si\(b\) lo hace.

Prueba

Inmediata de los teoremas\(\PageIndex{1}\), \(\PageIndex{2}\)y \(\PageIndex{6}\).

Ejercicios

Ejercicio\(\PageIndex{1}\)

Mostrar que la inversa de\(2\) módulo no\(7\) es la inversa de\(2\) módulo\(15\).

Ejercicio\(\PageIndex{2}\)

Encontrar enteros positivos específicos\(a,b,c\) y\(m\) tal que\(c \not \equiv 0 \pmod m\),\(\gcd(c,m) >0\), y\(ca\equiv cb\pmod m\), pero\(a \not\equiv b\pmod m\). ¿Qué muestra esto sobre los teoremas de este capítulo?

Ejercicio \(\PageIndex{3}\)

Demostrar teorema\(\PageIndex{4}\).

Ejercicio\(\PageIndex{4}\)

Determinar si es cierto o no cada uno de los siguientes. Dar razones en cada caso.

1. \(x\equiv 3\pmod 7\Rightarrow\gcd(x,7)=1\)
2. \(\gcd(68019,3)=3\)
3. \(12x\equiv 15\pmod{35}\Rightarrow 4x\equiv 5\pmod 7\)
4. \(x\equiv 6\pmod{12}\Rightarrow\gcd(x,12)=6\)
5. \(3x\equiv 3y\pmod{17}\Rightarrow x\equiv y\pmod{17}\)
6. \(5x\equiv y\pmod 6\Rightarrow 15x\equiv 3y\pmod{18}\)
7. \(12x\equiv 12y\pmod{15}\Rightarrow x\equiv y\pmod 5\)
8. \(x\equiv 73\pmod{75}\Rightarrow x\bmod 75=73\)
9. \(x\equiv 73\pmod{75}\)y\(0\le x<75\Rightarrow x=73\)
10. No hay entero\(x\) tal que\[12x\equiv 7\pmod{33}.\nonumber \]

Ejercicio\(\PageIndex{5}\)

1. Determinar la inversa del\(8\) módulo\(13\).
2. Usando su respuesta a (a), y tal vez imitando Ejemplo\(\PageIndex{2}\), determine todos los enteros\(x\) tales que\(8x \equiv 4 \pmod{13}\). (Nota: habrá infinitamente muchos de esos enteros; enumere suficientes de ellos para que quede claro el patrón y justifique su respuesta.)

Ejercicio\(\PageIndex{6}\)

Trate de utilizar los resultados de este capítulo para describir completamente las soluciones enteras a las siguientes congruencias. (Aquí los coeficientes en no\(x\) son relativamente primos al módulo.) Si una congruencia no tiene solución en los enteros, dígalo y explique por qué.

1. \(4x \equiv 6 \pmod{10}\)
2. \(30x \equiv 90 \pmod{200}\)
3. \(6x \equiv 4 \pmod{12}\).

Ejercicio\(\PageIndex{7}\)

¿Es posible encontrar enteros\(a,b,m\) dónde\(m \geq 2\) y\(0<a,b<m\) y\(a \neq b\), y hay al menos tres soluciones a la congruencia\[ax \equiv b \pmod{m}\nonumber \] en el conjunto\(\{0,\dots,m-1\}\)? Si es así, demuéstralo para una elección específica de\(a\)\(b\),, y\(m\). Si no es posible, explique por qué no.