¿Cómo encontrar las raices de x²+6≡0 (mod625)?

Es un ejercicio interesante de aritmética modular y que requiere cierto trabajo obtener la solución. La aritmética modular requiere que las soluciones sean números enteros, así que denominaré a la incógnita nn en lugar de x.x. La ecuación pedida se podrá escribir de estas dos maneras:

n2+6≡0(mod625),n2+6≡0(mod625),

n2≡−6(mod625)n2≡−6(mod625) (Ec. 1).

Por otro lado, es fácil demostrar que se cumplen siempre estas dos propiedades, que nos ayudarán a encontrar las soluciones:

Si n≡q(modm),n≡q(modm), entonces n2≡q2(modm)n2≡q2(modm) (Prop. 1),

Si n≡−q(modm),n≡−q(modm), entonces n2≡q2(modm)n2≡q2(modm) (Prop. 2).

Si lo aplicamos al caso del enunciado, con m=625,m=625, vemos que (por la Prop. 1) solo hay que encontrar las soluciones nini para 0≤ni≤625–12=312,0≤ni≤625–12=312, existiendo además una solución distinta de la forma nj=625−ninj=625−ni por cada ni,ni, de manera que todas las soluciones estarán entre los números enteros nn comprendidos entre 0 y 624, ambos incluidos.

Fijémonos por otro lado en que 625=54=252,625=54=252, por lo que podemos empezar acotando las posibles soluciones usando potencias de 5 crecientes, ya que:

n2=625k−6=25⋅25k–6=5⋅125k–6.n2=625k−6=25⋅25k–6=5⋅125k–6.

Por tanto, si se cumple la Ec. 1, entonces en módulo 5 tenemos que:

n2≡−6(mod5),n2≡−6(mod5),

n2≡−1(mod5)n2≡−1(mod5) (Ec. 2).

Según las Props. 1 y 2, solo debemos probar los casos n≡0,1y2(mod5),n≡0,1y2(mod5), pero:

• Si n≡0(mod5),n≡0(mod5), entonces n2≡0(mod5),n2≡0(mod5),
• Si n≡1(mod5),n≡1(mod5), entonces n2≡1(mod5),n2≡1(mod5),
• Si n≡2(mod5),n≡2(mod5), entonces n2≡4≡−1(mod5),n2≡4≡−1(mod5),

por lo que hay dos posibles soluciones:

n≡2(mod5),n≡5–2≡3(mod5).n≡2(mod5),n≡5–2≡3(mod5).

Además, si se cumple la Ec. 1, en módulo 25 tenemos que:

n2≡−6(mod25).n2≡−6(mod25).

Teniendo en cuenta las soluciones módulo 5 y las Props. 1 y 2, solo hay que analizar los números de la forma n=5a+b,n=5a+b, con 0≤n≤25–12=12,bϵ{2,3},0≤n≤25–12=12,bϵ{2,3}, es decir:

nϵ{2,3,7,8,12}.nϵ{2,3,7,8,12}.

• Si n≡2(mod25),n≡2(mod25), entonces n2≡4(mod25),n2≡4(mod25),
• Si n≡3(mod25),n≡3(mod25), entonces n2≡9(mod25),n2≡9(mod25),
• Si n≡7(mod25),n≡7(mod25), entonces n2≡49≡−1(mod25),n2≡49≡−1(mod25),
• Si n≡8(mod25),n≡8(mod25), entonces n2≡64≡−11(mod25),n2≡64≡−11(mod25),
• Si n≡12(mod25),n≡12(mod25), entonces n2≡144≡−6(mod25),n2≡144≡−6(mod25),

por lo que hay dos posibles soluciones:

n≡12(mod25),n≡25–12≡13(mod25).n≡12(mod25),n≡25–12≡13(mod25).

En lo que resta de demostración voy a usar un método distinto, ya que simplifica las operaciones.

Escribamos n=25a+b,n=25a+b, donde, según las soluciones módulo 25 y según las Props. 1 y 2, debe cumplirse:

0≤n≤625–12=312,0≤a≤24,bϵ{12,13}.0≤n≤625–12=312,0≤a≤24,bϵ{12,13}.

• Caso b=12b=12: n2=625a2+600a+144≡600a+144≡12(50a+12)(mod625),n2=625a2+600a+144≡600a+144≡12(50a+12)(mod625), luego:

n2≡12(50a+12)≡−6(mod625).n2≡12(50a+12)≡−6(mod625).

Dividimos por 6 en ambos lados de la equivalencia y operamos:

100a+24≡−1(mod625),100a+24≡−1(mod625),

100a+24=625k−1,100a+24=625k−1,

donde, como a≥0,a≥0, entonces k≥0k≥0 y es entero (Ec. 3a).

100a=625k−25.100a=625k−25.

Dividiendo entre 25 ambos lados de la igualdad:

4a=25k−1=24k+k−1=4⋅6k+(k−1).4a=25k−1=24k+k−1=4⋅6k+(k−1).

k−1=4(a−6k),k−1=4(a−6k), luego:

k≡1(mod4)k≡1(mod4) (Ec. 3b).

Por las Ecs. 3a y 3b, el menor valor de kk posible es k=1,k=1, que da:

a=6,n1≡6⋅25+12=162(mod625).a=6,n1≡6⋅25+12=162(mod625).

El siguiente menor caso posible es k=5,k=5, que da:

a=31>24,a=31>24, luego no es solución y no hay más soluciones.

• Caso b=13b=13: n2=625a2+650a+169≡650a+169,n2=625a2+650a+169≡650a+169, luego:

n2≡650a+169≡−6(mod625).n2≡650a+169≡−6(mod625).

Operamos, usando un entero k:k:

650a+169=625k−6,650a+169=625k−6,

donde, como a≥0,a≥0, es k≥0k≥0 (Ec. 4a).

650a=625k−175.650a=625k−175.

Dividiendo entre 25 ambos miembros de la igualdad:

26a=25k−7=26k−(k+7),26a=25k−7=26k−(k+7),

k+7=26(k−a),k+7=26(k−a), es decir:

k≡−7(mod26)k≡−7(mod26) (Ec. 4b).

Teniendo en cuenta las Ecs. 4a y 4b, el menor valor de kk es:

k=26–7=19,k=26–7=19, que da:

a=k−1=18,n2≡18⋅25+13=463(mod625).a=k−1=18,n2≡18⋅25+13=463(mod625).

El siguiente menor kk posible es:

k=2⋅26–7=45,k=2⋅26–7=45, que da:

a=k−2=43>24,a=k−2=43>24, luego no es solución y no hay más soluciones.

En principio podrían ser soluciones también 625−n1625−n1 y 625−n2,625−n2, pero 625−n1=n2,625−n2=n1,625−n1=n2,625−n2=n1, luego las dos únicas soluciones al ejercicio del enunciado son:

n1≡162≡−463(mod625).n1≡162≡−463(mod625).

n2≡−162≡463(mod625).n2≡−162≡463(mod625).