[Nub]

Hola, hice varios de estos y no se si hay otros métodos para hacerlo, o lo estoy haciendo mal. Por ejemplo \( 12^{1257},mod(5) \) lo que hago es tomar la base y buscar algo congruente a ella, busco su resto, \( 12\equiv{2}(5) \) ahora elevo ambos lados a la 1257 \( 12^{1257}\equiv{2^{1257}}(5) \) y se reduce bastante el problema y seguí así sucesivamente hasta llegar \( 2^{1257}\equiv{2\equiv{12^{1257}}} \)

Ahora quiero hacer este:

1) Calcular  \( 71^{10},mod(141) \)

El problema aca es que creo que para seguir con lo que hice arriba es demasiadas cuentas, por ejemplo para reducir la base no podemos tomar 71, pues no le puedo calcular el resto (podria tomar algo negativo pero bueno) tendría que tomar 71^2 y dividirlo entre 141 y eso es congruente a 106, luego elevo y queda \( 71^{10}=106^5 \) y seguir asi, no se si reduce el problema, el exponente si pero la base no

Gracias

[feriva]

Hola, hice varios de estos y no se si hay otros métodos para hacerlo, o lo estoy haciendo mal. Por ejemplo \( 12^{1257},mod(5) \) lo que hago es tomar la base y buscar algo congruente a ella, busco su resto, \( 12\equiv{2}(5) \) ahora elevo ambos lados a la 1257 \( 12^{1257}\equiv{2^{1257}}(5) \) y se reduce bastante el problema y seguí así sucesivamente hasta llegar \( 2^{1257}\equiv{2\equiv{12^{1257}}} \)

Ahora quiero hacer este:

1) Calcular  \( 71^{10},mod(141) \)

El problema aca es que creo que para seguir con lo que hice arriba es demasiadas cuentas, por ejemplo para reducir la base no podemos tomar 71, pues no le puedo calcular el resto (podria tomar algo negativo pero bueno) tendría que tomar 71^2 y dividirlo entre 141 y eso es congruente a 106, luego elevo y queda \( 71^{10}=106^5 \) y seguir asi, no se si reduce el problema, el exponente si pero la base no

Gracias

Si tomas 71 al cubo te da un resto más pequeño, 53, entonces son tres veces 71 al cubo por 71, pero sigue siendo pesado haciéndolo a mano. Es que cuando salen muchos primos suele ser más pesado; y depende de los casos.

Saludos.

[Luis Fuentes]

Hola

Hola, hice varios de estos y no se si hay otros métodos para hacerlo, o lo estoy haciendo mal. Por ejemplo \( 12^{1257},mod(5) \) lo que hago es tomar la base y buscar algo congruente a ella, busco su resto, \( 12\equiv{2}(5) \) ahora elevo ambos lados a la 1257 \( 12^{1257}\equiv{2^{1257}}(5) \) y se reduce bastante el problema y seguí así sucesivamente hasta llegar \( 2^{1257}\equiv{2\equiv{12^{1257}}} \)

Ahora quiero hacer este:

1) Calcular  \( 71^{10},mod(141) \)

El problema aca es que creo que para seguir con lo que hice arriba es demasiadas cuentas, por ejemplo para reducir la base no podemos tomar 71, pues no le puedo calcular el resto (podria tomar algo negativo pero bueno) tendría que tomar 71^2 y dividirlo entre 141 y eso es congruente a 106, luego elevo y queda \( 71^{10}=106^5 \) y seguir asi, no se si reduce el problema, el exponente si pero la base no

En general cuando quiere calcularse \( x^n \) mod \( m \) (con \( x,m \) coprimos), se aplica el Teorema de Euler:

\( x^{k}\equiv 1 \) mod \( m \) siendo \( k=\varphi(m) \)

No sé si lo has estudiado. Después se tiene que:

\( x^n\equiv x^r \) siendo \( r \) el resto de dividir \( n \) por \( k \)

En el ejemplo que pones... esto no ayuda nada.

En el primero si. Tenemos que \( \varphi(5)=5-1=4 \) y el resto de dividir \( 1257 \) por \( 4 \) es \( 1 \). Por tanto:

\( 12^{1257}\equiv 2^{1257}\equiv 2^1\equiv 2 \) mod \( 5 \)

Saludos.

[Nub]

Hola

Hola, hice varios de estos y no se si hay otros métodos para hacerlo, o lo estoy haciendo mal. Por ejemplo \( 12^{1257},mod(5) \) lo que hago es tomar la base y buscar algo congruente a ella, busco su resto, \( 12\equiv{2}(5) \) ahora elevo ambos lados a la 1257 \( 12^{1257}\equiv{2^{1257}}(5) \) y se reduce bastante el problema y seguí así sucesivamente hasta llegar \( 2^{1257}\equiv{2\equiv{12^{1257}}} \)

Ahora quiero hacer este:

1) Calcular  \( 71^{10},mod(141) \)

El problema aca es que creo que para seguir con lo que hice arriba es demasiadas cuentas, por ejemplo para reducir la base no podemos tomar 71, pues no le puedo calcular el resto (podria tomar algo negativo pero bueno) tendría que tomar 71^2 y dividirlo entre 141 y eso es congruente a 106, luego elevo y queda \( 71^{10}=106^5 \) y seguir asi, no se si reduce el problema, el exponente si pero la base no

En general cuando quiere calcularse \( x^n \) mod \( m \) (con \( x,m \) coprimos), se aplica el Teorema de Euler:

\( x^{k}\equiv 1 \) mod \( m \) siendo \( k=\varphi(m) \)

No sé si lo has estudiado. Después se tiene que:

\( x^n\equiv x^r \) siendo \( r \) el resto de dividir \( n \) por \( k \)

En el ejemplo que pones... esto no ayuda nada.

En el primero si. Tenemos que \( \varphi(5)=5-1=4 \) y el resto de dividir \( 1257 \) por \( 4 \) es \( 1 \). Por tanto:

\( 12^{1257}\equiv 2^{1257}\equiv 2^1\equiv 2 \) mod \( 5 \)

Saludos.

Hola Luis, todavía no llegue al teorema de euler, pero casi estoy, igual para ese ejercicio no debería usarlo. Lo único que me queda es o hacerlo a mano o también que vi por ahi que capaz es útil el inverso modular, pero no se me ocurre como usarlo en esto

Hola, hice varios de estos y no se si hay otros métodos para hacerlo, o lo estoy haciendo mal. Por ejemplo \( 12^{1257},mod(5) \) lo que hago es tomar la base y buscar algo congruente a ella, busco su resto, \( 12\equiv{2}(5) \) ahora elevo ambos lados a la 1257 \( 12^{1257}\equiv{2^{1257}}(5) \) y se reduce bastante el problema y seguí así sucesivamente hasta llegar \( 2^{1257}\equiv{2\equiv{12^{1257}}} \)

Ahora quiero hacer este:

1) Calcular  \( 71^{10},mod(141) \)

El problema aca es que creo que para seguir con lo que hice arriba es demasiadas cuentas, por ejemplo para reducir la base no podemos tomar 71, pues no le puedo calcular el resto (podria tomar algo negativo pero bueno) tendría que tomar 71^2 y dividirlo entre 141 y eso es congruente a 106, luego elevo y queda \( 71^{10}=106^5 \) y seguir asi, no se si reduce el problema, el exponente si pero la base no

Gracias

Si tomas 71 al cubo te da un resto más pequeño, 53, entonces son tres veces 71 al cubo por 71, pero sigue siendo pesado haciéndolo a mano. Es que cuando salen muchos primos suele ser más pesado; y depende de los casos.

Saludos.

Igual no se que es mejor, dividir numeros grandes o mas chicos pero con restos un poco mas grande

[Luis Fuentes]

Hola

Hola Luis, todavía no llegue al teorema de euler, pero casi estoy, igual para ese ejercicio no debería usarlo. Lo único que me queda es o hacerlo a mano o también que vi por ahi que capaz es útil el inverso modular, pero no se me ocurre como usarlo en esto

Tienes que:

\( 71\cdot 2=142=141+1 \) por tanto \( 71=2^{-1} \) mod \( 141 \)

(aqui he usado que uno ve a ojo que \( 71\cdot 2=142=141+1 \) y eso hace que uno vea cuál es su inverso y además que éste es muy sencillito)

Entonces:

\( 71^{10}=(2^{-1})^{10}=(2^{10})^{-1} \) mod \( 141 \)

Ahora tendrías que hallar \( 2^{10} \) mod \( 141 \) que es más fácil y luego su inverso mód \( 141 \), que te supone resolver una ecuación diofántica.

Saludos.

[Nub]

Hola

Hola Luis, todavía no llegue al teorema de euler, pero casi estoy, igual para ese ejercicio no debería usarlo. Lo único que me queda es o hacerlo a mano o también que vi por ahi que capaz es útil el inverso modular, pero no se me ocurre como usarlo en esto

Tienes que:

\( 71\cdot 2=142=141+1 \) por tanto \( 71=2^{-1} \) mod \( 141 \)

(aqui he usado que uno ve a ojo que \( 71\cdot 2=142=141+1 \) y eso hace que uno vea cuál es su inverso y además que éste es muy sencillito)

Entonces:

\( 71^{10}=(2^{-1})^{10}=(2^{10})^{-1} \) mod \( 141 \)

Ahora tendrías que hallar \( 2^{10} \) mod \( 141 \) que es más fácil y luego su inverso mód \( 141 \), que te supone resolver una ecuación diofántica.

Saludos.

No se como hiciste osea todas las notaciones (y que no usaste congruencias) yo tengo algo parecido con congruencias, un entero en este caso 71 es invertible si existe x entero tal que \( 71x\equiv{1} \) podemos ver que si x=2 se cumple, entonces 2 es el inverso de \(  71 ,mod(141) \)
Luego tenemos \( 71*2\equiv{1} \) mod(141), elevo a la 10, \( (71*2)^{10}\equiv{1^{10}} \)
Tenemos  \( 71^{10}*2^{10}\equiv{1} \) y por lo que tu dices, probablemente creo que haya que quitar el 2^10 encontrando su inverso y multiplicar ambos lados no?

[Nub]

Ya pude, me dio que era congruente a 61, gracias a los dos