[manooooh]

Hola comunidad! Tengo un problema con esta ecuación de congruencia. Al principio la sigo normalmente, pero luego me doy cuenta que tengo que trabajar con números grandes, por lo tanto, quisiera saber si existe alguna manera fácil de resolverlo. Gracias!

Dice así:

\( 19x \equiv{1} \) \( (140) \)

Compruebo si la ecuación tiene solución (si tiene, cuántas):

\( (m.c.d.(19, 140) = 1  \wedge  1|1)  \Longrightarrow{\exists{1}} \) \(  solución \)


Para hallar la única solución, primero escribo la forma general de la ecuación de congruencia lineal:
\( ax \equiv{b} \) \( (n) \)

luego

\( x = a^{φ(n) - 1} * b \)
siendo \( φ(n) \) la Función de Euler.

Así que tengo: \( x = 19^{φ(140) - 1} * 1 \)

Para hallar \( φ(140) \) factorizo \( 140 \) y veo que los primos que lo componen son \( 2, 5 \) y \( 7 \) (sin repetir). Entonces sigo: \( φ(140) = 140 * (1 - \displaystyle\frac{1}{2}) * (1 - \displaystyle\frac{1}{5}) * (1 - \displaystyle\frac{1}{7}) = 48 \) (acá usé lo que el profesor llamó "la productoria de los primos que dividen a \( n \)").


Luego vuelvo para hallar \( x \):

\( x = 19^{48 - 1} * 1 = 19^{47} \). Como \( 19^{47} \) no está dentro del universo de \( \mathbb{Z}_{140} \) tengo que seguir, así que hago:

\( 19^{47} \equiv{x} \) \( (140) \)

Y hasta acá llegué . Una simple congruencia que no logro sacar. No puedo usar el Pequeño Teorema de Fermat porque la maldita \( n \) (\( 140 \)) no es prima...
Lo que no estoy seguro es usar el Teorema de Euler-Fermat, que asegura que (no pongo el caso para \( n \) primo):

\( (n \in{\mathbb{N}}, a \in{\mathbb{Z}}, m.c.d.(a, n) = 1) \Longrightarrow{a^{φ(n)} \equiv{1 (n)}} \)

EDIT:
Debería poner \( 19^{47} \) dentro del universo de \( \mathbb{Z}_{140} \). Esto lo consigo elevando el \( 19 \) hasta que sea igual o "un poquito más" a \( 140 \). Entonces me queda \( 19^2 = 361 \), que es el primer número que "se pasa" del \( 140 \). Pero me queda un choclaso de números, porque debo expresar el número como "suma de potencias", o sea:
\( 19^{47} = 19^2 * 19^2 * 19^2 * ... \equiv{81 * 81 * 81 * ... \equiv{x (140)}} \)


Por favor, ¿alguno me puede decir en qué estoy mal o cómo seguir el ejercicio? Comprobé la ecuación en Wolfram y me dice que \( x = 59 \), lo compruebo y efectivamente el resto de dividir \( 19 * 59 \) por \( 140 \) es \( 1 \).

AYUDAAAA!

Gracias!!

[robinlambada]

Spoiler

Hola comunidad! Tengo un problema con esta ecuación de congruencia. Al principio la sigo normalmente, pero luego me doy cuenta que tengo que trabajar con números grandes, por lo tanto, quisiera saber si existe alguna manera fácil de resolverlo. Gracias!

Dice así:

\( 19x \equiv{1} \) \( (140) \)

Compruebo si la ecuación tiene solución (si tiene, cuántas):

\( (m.c.d.(19, 140) = 1  \wedge  1|1)  \Longrightarrow{\exists{1}} \) \(  solución \)


Para hallar la única solución, primero escribo la forma general de la ecuación de congruencia lineal:
\( ax \equiv{b} \) \( (n) \)

luego

\( x = a^{φ(n) - 1} * b \)
siendo \( φ(n) \) la Función de Euler.

Así que tengo: \( x = 19^{φ(140) - 1} * 1 \)

Para hallar \( φ(140) \) factorizo \( 140 \) y veo que los primos que lo componen son \( 2, 5 \) y \( 7 \) (sin repetir). Entonces sigo: \( φ(140) = 140 * (1 - \displaystyle\frac{1}{2}) * (1 - \displaystyle\frac{1}{5}) * (1 - \displaystyle\frac{1}{7}) = 48 \) (acá usé lo que el profesor llamó "la productoria de los primos que dividen a \( n \)").


Luego vuelvo para hallar \( x \):

\( x = 19^{48 - 1} * 1 = 19^{47} \). Como \( 19^{47} \) no está dentro del universo de \( \mathbb{Z}_{140} \) tengo que seguir, así que hago:

\( 19^{47} \equiv{x} \) \( (140) \)

Y hasta acá llegué . Una simple congruencia que no logro sacar. No puedo usar el Pequeño Teorema de Fermat porque la maldita \( n \) (\( 140 \)) no es prima...
Lo que no estoy seguro es usar el Teorema de Euler-Fermat, que asegura que (no pongo el caso para \( n \) primo):

\( (n \in{\mathbb{N}}, a \in{\mathbb{Z}}, m.c.d.(a, n) = 1) \Longrightarrow{a^{φ(n)} \equiv{1 (n)}} \)

EDIT:
Debería poner \( 19^{47} \) dentro del universo de \( \mathbb{Z}_{140} \). Esto lo consigo elevando el \( 19 \) hasta que sea igual o "un poquito más" a \( 140 \). Entonces me queda \( 19^2 = 361 \), que es el primer número que "se pasa" del \( 140 \). Pero me queda un choclaso de números, porque debo expresar el número como "suma de potencias", o sea:
\( 19^{47} = 19^2 * 19^2 * 19^2 * ... \equiv{81 * 81 * 81 * ... \equiv{x (140)}} \)


Por favor, ¿alguno me puede decir en qué estoy mal o cómo seguir el ejercicio? Comprobé la ecuación en Wolfram y me dice que \( x = 59 \), lo compruebo y efectivamente el resto de dividir \( 19 * 59 \) por \( 140 \) es \( 1 \).

AYUDAAAA!

Gracias!!

[cerrar]

Hola:

Partimos de:

\(  19^{47}\equiv{}x (mod\,140) \)

\(  19^{3\cdot{3\cdot{5}}+2}\equiv{}x (mod\,140) \)

\(  (19^5)^{3\cdot{3}}\cdot{19^2}\equiv{}x (mod\,140) \)

\(  (59^3)^3\cdot{81}\equiv{}x (mod\,140) \)

\(  (139)^3\cdot{81}\equiv{}x \equiv{}(-1)^3\cdot{81}\equiv{}-81  (mod\,140) \)

Entonces \( x=140-81=59 \)

Saludos.

[manooooh]

¿Cómo llegás a que \( 19^{47} = 19^{3.3.5 + 2} \)? ¿Por simpleza de descomponer el número? Porque no se lo puede factorizar.

[robinlambada]

¿Cómo llegás a que \( 19^{47} = 19^{3.3.5 + 2} \)? ¿Por simpleza de descomponer el número? Porque no se lo puede factorizar.

Efectivamente por simpleza, para ir reduciendo poco a poco la potencia a calcular, por eso la descomposición de 47 puede ser la que te interese.

Saludos.

[manooooh]

Ahhh, que yo recuerde el profesor nunca explicó esa manera :/.

Otra cosa, ¿por qué elegís elevar el \( 19 \) a la quinta? Porque, como escribí, supuestamente hay que conseguir elevar el número que más se acerque a \( n \) (\( 140 \)), que sería en este caso elevarlo al cubo primero.

Gracias por responder!

[robinlambada]

Ahhh, que yo recuerde el profesor nunca explicó esa manera :/.

Otra cosa, ¿por qué elegís elevar el \( 19 \) a la quinta? Porque, como escribí, supuestamente hay que conseguir elevar el número que más se acerque a \( n \) (\( 140 \)), que sería en este caso elevarlo al cubo primero.

Gracias por responder!

En el fondo da igual por que potencia empieces, aunque en este caso si es más rápido elevarlo al cubo primero pues: \( 19^3\equiv{139\equiv{-1\,(mod\,140)}} \)

[manooooh]

Genial! Es cierto. Última cuestión, ¿qué propiedad / método usás para hacer \( 140 - 81 \)?

[manooooh]

Genial! Es cierto. Última cuestión, ¿qué propiedad / método usás para hacer \( 140 - 81 \)?

Además, tengo entendido que no se puede utilizar la calculadora para sacar, por ejemplo, \( 19^5 \). ¿Habrá otra manera de hacerlo sin calculadora?

[robinlambada]

Genial! Es cierto. Última cuestión, ¿qué propiedad / método usás para hacer \( 140 - 81 \)?

Tienes \( x\equiv{}-81\Leftrightarrow{}x+140\equiv{}140-81\Leftrightarrow{}x+0\equiv{}140-81  \, (mod\,140) \)


Siempre si \( x\equiv{}b\,\equiv{}-c (mod\,a) \) con \( a=b+c \) y \( a,b,c>0 \)

Ejemplo \( 4\equiv{}-1\, (mod\,5) \) ó \( 3\equiv{}-2\, (mod\,5) \)

Esto se puede ver en la solución general de la ecuación.

 \( x\equiv{}-81   \, (mod\,140) \) (*)

Tanto x=-81 y x=59 son soluciones particulares de (*)

La solución general es:

\( x=-81 +140t \) pero si hacemos el cambio de variable \( t=t'+1 \) entonces la solución queda:

\( x=-81 +140(t'+1)=140-81+140t'=59+140t' \)

Saludos.

[manooooh]

¿Y con respecto a no hacer cuentas, qué me dices?