Autor Tema: Determinar el resto de la división (congruencias)

0 Usuarios y 1 Visitante están viendo este tema.

28 Junio, 2019, 08:20 pm
Leído 860 veces

yuzo

  • $$\Large \color{red}\pi$$
  • Mensajes: 8
  • Karma: +0/-0
  • Sexo: Masculino
Hola a todos, tengo el siguiente ejercicio:

Determinar el resto de dividir \( (102^{73}+55)^{37} \) entre \( 111 \)

Me piden \( (102^{73}+55)^{37} \)\( \equiv x {(mod 111)} \)

Para empezar he calculado la función \( \varphi \) de Euler de 111; \( \varphi(111) = \varphi(3)\varphi(37)=72 \)

He calculado las congruencias módulo 111 de la base y el exponente para simplificar:

\( 102^{73}+55\equiv{46}(mod 111) \) y \( 37\equiv{37}(mod 111) \)

Tendría \( 46^{37}\equiv{x(mod 111)} \) pero a partir de aquí no sé como seguir, he pensado plantear un sistema de congruencias

\begin{array}{c} a\equiv{x(mod3)} \\ a\equiv{y(mod 37)} \end{array} al ser los módulos primos entre sí tendría solución común en (mod 111) pero no sé cómo seguir.

Gracias, un saludo.

28 Junio, 2019, 08:59 pm
Respuesta #1

feriva

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 9,310
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Hola a todos, tengo el siguiente ejercicio:

Determinar el resto de dividir \( (102^{73}+55)^{37} \) entre \( 111 \)

Me piden \( (102^{73}+55)^{37} \)\( \equiv x {(mod 111)} \)

Para empezar he calculado la función \( \varphi \) de Euler de 111; \( \varphi(111) = \varphi(3)\varphi(37)=72 \)

He calculado las congruencias módulo 111 de la base y el exponente para simplificar:

\( 102^{73}+55\equiv{46}(mod 111) \) y \( 37\equiv{37}(mod 111) \)

Tendría \( 46^{37}\equiv{x(mod 111)} \) pero a partir de aquí no sé como seguir, he pensado plantear un sistema de congruencias

\begin{array}{c} a\equiv{x(mod3)} \\ a\equiv{y(mod 37)} \end{array} al ser los módulos primos entre sí tendría solución común en (mod 111) pero no sé cómo seguir.

Gracias, un saludo.

Hola; sólo una idea.

Mi consejo es que, antes de aplicar Euler, el teorema del pequeño Fermín o lo que sea, expreses todo lo que puedas en función del módulo

Perdón, que creí era módulo 11

Spoiler

\( (102^{73}+55)^{37}=(102^{66}\cdot102^{7}+5\cdot11)^{33}\cdot(102^{66}\cdot102^{7}+5\cdot11)^{4}
  \)

y a partir de ahí, mira a ver qué se te ocurre.

[cerrar]

Saludos.

28 Junio, 2019, 10:46 pm
Respuesta #2

ingmarov

  • Moderador Global
  • Mensajes: 4,936
  • País: hn
  • Karma: +0/-0
  • Sexo: Masculino
Hola

Otra forma es, desde el inicio, calcular por separado los restos,

\( (102^{73}+55)^{37}\equiv x_1(mod 3) \)

Y

\( (102^{73}+55)^{37}\equiv x_2(mod 37) \)


Luego aplicar el teorema chino del resto.


Por ejemplo
No he revisado tus cálculos, suponiendo que todo está bien

\( 46^{37}\equiv 1(mod 3) \)

\( 46^{37}\equiv 46\equiv 9(mod 37) \)


Entonces

\( (102^{73}+55)^{37}=(3\cdot 3+37)+111k=46+111k \) para un valor entero k.

Luego el resto buscado sería 46.  Debes tener un error, si no me equivoco el resto debe dar 103
46 es la respuesta correcta!!!

Saludos
No te confíes, revisa lo que escribo. Yo también me equivoco.
Odio el autocorrector de Android...

29 Junio, 2019, 06:35 pm
Respuesta #3

ingmarov

  • Moderador Global
  • Mensajes: 4,936
  • País: hn
  • Karma: +0/-0
  • Sexo: Masculino
Pongo la resolución que te propuse

\( (102^{73}+55)^{37}\equiv 1(mod 3) \)

\( (102^{73}+55)^37\equiv (-9(-9^{36})^2+18)^{37}\equiv (-9+18)^37\equiv 9(9^{36})\equiv 9(mod 37) \)

Ahora con el teorema chino del resto

3(3)+37=46

Saludos

No te confíes, revisa lo que escribo. Yo también me equivoco.
Odio el autocorrector de Android...

29 Junio, 2019, 07:56 pm
Respuesta #4

yuzo

  • $$\Large \color{red}\pi$$
  • Mensajes: 8
  • Karma: +0/-0
  • Sexo: Masculino


Hola; sólo una idea.

Mi consejo es que, antes de aplicar Euler, el teorema del pequeño Fermín o lo que sea, expreses todo lo que puedas en función del módulo

Perdón, que creí era módulo 11

Spoiler

\( (102^{73}+55)^{37}=(102^{66}\cdot102^{7}+5\cdot11)^{33}\cdot(102^{66}\cdot102^{7}+5\cdot11)^{4}
  \)

y a partir de ahí, mira a ver qué se te ocurre.

[cerrar]

Saludos.

Hola feriva, gracias por contestar, no sabría como seguir, no lo veo tan sencillo como simplificándolo, ¿cómo seguiría?


Pongo la resolución que te propuse

\( (102^{73}+55)^{37}\equiv 1(mod 3) \)

\( (102^{73}+55)^37\equiv (-9(-9^{36})^2+18)^{37}\equiv (-9+18)^37\equiv 9(9^{36})\equiv 9(mod 37) \)

Ahora con el teorema chino del resto

3(3)+37=46

Saludos



Perfecto ingmarov! Es justo lo que buscaba, gracias  ;)

29 Junio, 2019, 08:26 pm
Respuesta #5

feriva

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 9,310
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino


Hola feriva, gracias por contestar, no sabría como seguir, no lo veo tan sencillo como simplificándolo, ¿cómo seguiría?



Por congruencias yo lo he estado mirando y no sé cómo acortar, queda aparatoso

\( (46)^{37}
  \)

Ahora

\( 46^{2}=2116\equiv7(mod111)
  \)

Entonces

\( (46)^{37}=(46^{2})^{18}\cdot46\equiv
  \)

\( 7^{18}\cdot46
  \)

y ahora

\( 7^{3}=343\equiv10(mod111)\equiv
  \)

\( (7^{3})^{6}\cdot46\equiv(10)^{6}\cdot46
  \)

y tenemos

\( 10^{3}=1000\equiv1(mod111)
  \)

finalmente

\( (10^{3})^{2}\cdot46\equiv1^{2}\cdot46\equiv46(mod111)
  \)

Saludos.

29 Junio, 2019, 10:29 pm
Respuesta #6

ingmarov

  • Moderador Global
  • Mensajes: 4,936
  • País: hn
  • Karma: +0/-0
  • Sexo: Masculino


Hola feriva, gracias por contestar, no sabría como seguir, no lo veo tan sencillo como simplificándolo, ¿cómo seguiría?



Por congruencias yo lo he estado mirando y no sé cómo acortar, queda aparatoso

\( (46)^{37}
  \)

Ahora

\( 46^{2}=2116\equiv7(mod111)
  \)

Entonces

\( (46)^{37}=(46^{2})^{18}\cdot46\equiv
  \)

\( 7^{18}\cdot46
  \)

y ahora

\( 7^{3}=343\equiv10(mod111)\equiv
  \)

\( (7^{3})^{6}\cdot46\equiv(10)^{6}\cdot46
  \)

y tenemos

\( 10^{3}=1000\equiv1(mod111)
  \)

finalmente

\( (10^{3})^{2}\cdot46\equiv1^{2}\cdot46\equiv46(mod111)
  \)

Saludos.

Me gusta... ;D

Y agregar que si no tuviéramos a 111 sino a un número primo, no podríamos utilizar el método que sugerí, estaríamos obligados a utilizar algo como lo que feriva nos ha mostrado.

Saludos compañeros
No te confíes, revisa lo que escribo. Yo también me equivoco.
Odio el autocorrector de Android...

29 Junio, 2019, 10:37 pm
Respuesta #7

feriva

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 9,310
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino