Entre las aplicaciones que se puede dar al pequeño teorema de Fermat (PTF) están las relacionadas con la criptografía y que se vinculan con los famosos “test de primalidad”. Sin embargo, para el PTF, o de forma más general el teorema de Euler (véase entrega anterior), también puede encontrarse otro tipo de aplicación; específicamente, para resolver algunas congruencias binomiales de la forma:
\( x^a\equiv b\pmod {m} \) (2.11)
Donde, \( a \) y \( b \) son números enteros positivos dados y \( x \) se llama incógnita.
Antes de dar el método para resolver esta ecuación de congruencias, previamente demostraremos el siguiente teorema:
TEOREMA: Dada una congruencia en la forma: \( A\equiv B\pmod {m} \), se puede elevar ambos miembros de la congruencia a una potencia positiva “n>1”.
DEMOSTRACIÓN:
Spoiler
Sean, \( A\equiv B\pmod {m} \) (1), \( A\equiv B\pmod {m} \) (2).
Por la LEY DE MULTIPLICACIÓN MIEMBRO A MIEMBRO (véase leyes del algebra de congruencias), multipliquemos ambos miembros de ambas congruencias, para obtener:
\( A\cdot {A}\equiv B\cdot {B}\pmod {m} \) o también: \( A^2\equiv B^2\pmod {m} \) (3)
Repitiendo el proceso con (1) y (3), tenemos,
\( A^3\equiv B^3\pmod {m} \) (3)
Entonces, por inducción,
Supongamos que se verifica para el exponente “k”:
\( A^k\equiv B^k\pmod {m} \) (4)
Multiplicando miembro a miembro (por la ley citada) las ecuaciones (1) y (4), tenemos:
\( A^{k+1}\equiv B^{k+1}\pmod {m} \) (5)
Lo cual demuestra y justifica que se puede elevar una congruencia dada a la n-ésima potencia (n>1)
Resolver la siguiente ecuación binomial de quinto grado,
\( x^5\equiv 94\pmod {103} \) (1)
NOTA: Aunque este método es excelente (para resolver este tipo de ecuaciones de congruencias), no se puede aplicar a todos los casos posibles. Desafiamos al lector a averiguar a partir del siguiente ejemplo por qué ocurre eso).
SOLUCIÓNRecordemos que el PTF dice:
\( x^{103-1}\equiv 1\pmod {103} \) o mejor (pos SIMETRÍA) \( 1\equiv x^{102}\pmod {103} \) (2)
1) Relacionemos los exponentes de (1) y de (2), o sea, 102 y 5, para hallar su m.c.d. Dado que el lector ya sabe cómo hacer eso, a continuación escribimos directamente en forma de combinación lineal (Bézout). O sea:
\( (-2)\cdot {102}+(41)\cdot {5}=1 \) (3)
Despejando convenientemente:
\( (41)\cdot {5}=(2)\cdot {102}+ 1 \) (3) ’
2) Ahora teniendo en cuenta (3) ‘; por el teorema anterior, elevamos ambos miembros de la congruencia (1) a: \( n=41 \). O sea,
\( (x^5)^{41}\equiv 94^{41}\pmod {103} \) (1) ’
Dado que: \( (x^5)^{41}= x^{(2)\cdot {102}+ 1}= x^{(2)\cdot {102}}x \) . Entonces,
\( x^{(2)\cdot {102}}x \equiv 94^{41}\pmod {103} \) (1) ’’
Análogamente, elevamos ambos miembros de la congruencia (2) a \( n=2 \). O sea,
\( 1\equiv (x^{102})^2\pmod {103} \) (2) ’
3) Multiplicando miembro a miembro las ecuaciones (1) ’’ y (2) ’, resulta,
\( x^{(2)\cdot {102}}x \equiv 94^{41}(x^{102})^2\pmod {103} \)
Por la “ley cancelativa del producto” nos deshacemos de: \( (x^{102})^2 \) , resultando,
\( x \equiv 94^{41}\pmod {103} \) (4)
(4) prácticamente es la solución de la ecuación binomial de quinto grado. Sin embargo, podemos simplificar el segundo miembro para que el resto sea menor que el módulo. O sea,
Spoiler
Tengamos en cuenta que:
\( 41=2^5+2^8+1=32+8+1 \)
Entonces procedemos a elevar al cuadrado, y el resultado volvemos a elevar al cuadrado, y así sucesivamente. Tenemos:
Primera potenciación: \( 94^2\equiv 81\pmod {103} \)
Segunda potenciación: \( 94^4\equiv 81^2\equiv 72\pmod {103} \)
Tercera potenciación: \( 94^8\equiv 72^2\equiv 34\pmod {103} \)
Cuarta potenciación: \( 94^{16}\equiv 34^2\equiv 23\pmod {103} \)
Quinta potenciación: \( 94^{32}\equiv 23^2\equiv 14\pmod {103} \)
Los restos que nos interesan son de la quinta y de la tercera potenciación. Entonces, tenemos:
\( 94^{41} \equiv 94^{32}\cdot{}94^8\cdot{94}\pmod {103} \)
\( 94^{41} \equiv (14)\cdot{}(34)\cdot{94}\equiv 42\pmod {103} \)
De donde finalmente,
\( x \equiv 42\pmod {103} \) (5)
Lo cual se puede verificar reemplazando este resultado en la ecuación original (1). O sea,
\( 42^5\equiv 94\pmod {103} \) (que es cierto)
ACLARACIÓN: Para resolver este ejercicio, hemos justificado cada paso teniendo en cuenta las leyes del algebra de congruencias. Sin embargo, una vez que ya somos conscientes de la veracidad de dichas leyes, el lector podrá agilizar la resolución de ejercicios similares sin tanta justificación (así como cuando se resuelve una ecuación ordinaria de algebra, no hay que justificar cada vez las leyes que están involucradas. Por eso, en adelante vamos a efectuar la resolución de congruencias con la mayor brevedad posible.
EJERCICIO PARA EL LECTOREmpleando el método descrito en los anteriores párrafos, resolver:
\( x^{341} \equiv 127\pmod {893} \)
Sugerencia: 893 no es primo, entonces, emplee el teorema de Euler, en lugar del PTF.
Spoiler
Ayuda: \( \phi (893)=\phi(19)\cdot {\phi (47)}=18\cdot {46}=828 \)
Respuesta: \( x \equiv 630\pmod {893} \)
Consideremos la siguiente congruencia:
\( 3^x\equiv u\pmod {11} \) donde \( 0\leq{}u<11 \)
A medida que damos valores a “x” de la siguiente sucesión:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, …
“u” adquiere los siguientes valores
1, 3, 9, 5, 4, 1, 3, 9, 5, 4, 1, 3, 9, 5, 4, 1, 3, 9, 5, 4, 1, 3, 9, 5, 4, 1, 3, 9, 5, 4, 1, …
Esto se puede apreciar mejor en la siguiente gráfica:
Podemos observar que en la segunda sucesión están ausentes los valores: 2, 6, 7, 8, 10. Esto reduce la “amplitud del periodo (fundamental) de la congruencia”. Su valor ya no es como habíamos visto en ocasiones anteriores igual al módulo (recuérdese la LEY PERIODICA). En este caso particular, la amplitud del periodo (fundamental) es igual a \( T_0=5 \).
O sea, los valores de la ordenada "u" (en la gráfica) se repiten cada vez que la abscisa “x” se ha recorrido en 5 unidades hacia la derecha. Este valor (o amplitud del periodo fundamental de la congruencia) se llama también “orden de 3 con respecto del módulo 11” (donde 3 es el valor de la base de la función exponencial). Vamos a definir esta idea con mejor precisión.
Definición (orden de “a” con respecto del módulo “m”)Se llama orden de \( a \) con respecto del módulo \( m \) al entero positivo más pequeño \( d \) tal que se verifique la congruencia:
\( a^d\equiv 1\pmod {m} \) (2.12)
Obsérvese la similitud con el PTF (o con el teorema de Euler). Entonces, se requiere que,
\( 1\leq{}d\leq{}\phi (m) \).
Este valor lo denotaremos del siguiente modo:
\( d=Ord_m(a) \).
que se lee: "d es igual al orden de a, módulo m"
TEOREMASean \( a \) y \( m \) dos enteros positivos tales que, \( mcd(a,m)=1 \). Sea, \( d=Ord_m(a) \). Entonces, \( a^k\equiv a^l\pmod {m} \), sí y solo sí, \( k\equiv l\pmod {d} \). En particular, \( a^n\equiv 1\pmod {m} \), si y solo si, \( d \) divide a \( n \); y además, \( d \) divide a \( \phi (m) \).
DEMOSTRACIÓNSpoiler
PRIMERA PARTE: \( a^k\equiv a^l\pmod {m} \), sí y solo sí, \( k\equiv l\pmod {d} \)
1) Sea \( a \) de orden \( d \), módulo \( m \). Además, sean \( a \) y \( m \), coprimos entre sí. Supongamos además, que tenemos la congruencia: \( k\equiv l\pmod {d} \), luego, por definición:
\( k=l+d\cdot {M} \) (M es algún número entero). (1)
Por otro lado, siempre es posible, \( a^k\equiv a^k\pmod {m} \) (reflexividad) (2)
Podemos reemplazar (1) en (2), para obtener:
\( a^k\equiv a^{ l+d\cdot {M}}\pmod {m} \)
Expresando esto en forma más conveniente,
\( \displaystyle{a^k\equiv a^l(a^d)^M\pmod {m}} \) (3)
Por ser “a” de orden “d”, módulo “m”, tenemos,
\( a^d\equiv 1\pmod {m} \)
Elevemos a la potencia “M”,
\( \displaystyle{(a^d)^M\equiv 1\pmod {m}} \) (4)
Se puede multiplicar (3) y (4) miembro a miembro, para obtener,
\( \displaystyle{(a^k)( a^d)^M\equiv a^l(a^d)^M\pmod {m}} \)
Además, dado que: \( mcd(a, m)=1 \) en ambos miembros se cancela la expresión: \( \displaystyle{( a^d)^M } \) ,
\( \displaystyle{a^k\equiv a^l\pmod {m}} \)
Lo cual prueba que: \( k\equiv l\pmod {d} \) implica \( \displaystyle{a^k\equiv a^l\pmod {m}} \)
2) Recíprocamente, sea
\( \displaystyle{a^k\equiv a^l\pmod {m}} \) (5)
Sin perder generalidad, podemos suponer que \( k\geq{}l \) , entonces, por el algoritmo de la división (tomando “d” como divisor),
\( k-l=d\cdot {q}+r \) y donde \( 0\leq{}r<=d-1 \) (6)
Podemos reemplazar (6) en (2),
\( a^k\equiv a^{ l+d\cdot {q}+r}\pmod {m} \)
Que se puede, escribir en esta otra forma:
\( \displaystyle{a^k\equiv a^l(a^d)^qa^r\pmod {m}} \) (7)
Por ser “a” de orden “d”, módulo “m”, tenemos,
\( a^d\equiv 1\pmod {m} \)
Elevemos a la potencia “q”,
\( \displaystyle{(a^d)^q\equiv 1\pmod {m}} \) (8)
Luego de multiplicar (7) y (8), miembro a miembro, podremos cancelar la expresión: \( \displaystyle{( a^d)^q} \) . Además, por la condición inicial (5), y teniendo en cuenta que “a” y “m” son coprimos entre sí, se podrá cancelar: \( a^k \) con \( a^l \), de donde resultará finalmente,
\( 1\equiv a^r\pmod {m} \)
Pero, habíamos dicho que “a” es de orden “d”, módulo “m”. Luego, por (6), sólo queda una posibilidad. Que sea,
\( r=0 \)
De donde inmediatamente, por definición de congruencia, (6) nos dice que:
\( k\equiv l\pmod {d} \)
Lo cual demuestra que: \( \displaystyle{a^k\equiv a^l\pmod {m}} \) implica \( k\equiv l\pmod {d} \)
De donde, el teorema es cierto (en su primera parte).
SEGUNDA PARTE:
\( a^n\equiv 1\pmod {m} \), si y solo si, \( d \) divide a \( n \); y además, \( d \) divide a \( \phi (m) \).
3) En efecto, dado que “a” es de orden “d”, módulo “m”; sólo puede darse que n=d o que n>d. Si n=d (no hay nada que probar). Si n>d, entonces por la PRIMERA PARTE, tendríamos: \( \displaystyle\a^n\equiv a^d\equiv 1\pmod {m} \) si y solo si \( n\equiv d\pmod {d} \) ; de donde, \( n\equiv 0\pmod {d} \) que nos dice que “d” es divisor de “n”.
4) Por el teorema de Euler \( a^{\phi(m)}\equiv a^d\equiv 1\pmod {d} \). Entonces, por el anterior inciso (3), “d” es divisor de \( \phi (m) \).
Los cuales completan la demostración del teorema dado.
En base a los conceptos recien enunciados, se puede resolver una ecuación lineal de congruencias conociendo el ORDEN DE UN NUMERO, MÓDULO M. O en general, conociendo la FUNCIÓN PHI DE EULER.
Supongamos que buscamos resolver la ecuación:
\( ax\equiv b\pmod {m} \)
siendo \( mcd(a,m)=1 \). entonces, existe única solución.
Supongamos que "a" es de orden "d", módulo "m". O sea, \( d=Ord_m(a) \), entonces,
\( a^d\equiv 1\pmod{m} \) o también, \( 1\equiv a^d\pmod{m} \)
Multiplicando con la ecuación original, resulta,
\( ax\equiv b\cdot {a^d}\pmod {m} \)
Como a y m son coprimos entre sí y como \( d\geq{1} \), se puede dividir miembro a miembro por "a", resultando,
\( x\equiv b\cdot {a^{d-1}}\pmod {m} \)
Con lo que hemos enconcontrado la solución general de la ecuación de congruencias.
NOTA: A veces, no es fácil conocer el valor \( d=Ord_m(a) \), por eso, en su lugar podemos emplear la función totient de Euler..
Con esto concluimos este breve recorrido a la teoria elemental de números. En el futuro, sólo nos queda analizar los simbolos de Legendre y de Jacobi junto con la ley de reciprocidad cuadrática.
En posteriores entregas realizaremos una introducción al algebra lineal, con principal énfasis en el cálculo matricial.
(continuará)
