Autor Tema: Resolver una congruencia

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

02 Abril, 2007, 02:55 am
Leído 2188 veces

Ked

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 945
  • Karma: +0/-0
  • Sexo: Masculino
Calcular \( \displaystyle 347^{231}\!\!\pmod{35} \)

Yo lo resolví observando que \( 347 \equiv 32 \!\!\pmod{35} \) y que \( 32 = 2^5 \). Después usé \( \varphi(35) = 24 \) para obtener \( 2^{24} \equiv 1 \!\!\pmod{35} \) y uniendo todo, al final me dio 8 (resultado que ya verifiqué).

Mi duda es, que el ejercicio trae una sugerencia: "Sugerencia: Usar el teorema Chino del resto"

¿Qué tiene que ver el teorema del resto chino con esto? ¿En qué se puede aplicar en este caso? En caso que sí sirva, ¿simplifica las cosas?

Saludos

02 Abril, 2007, 04:26 am
Respuesta #1

Rogelio Yoyontzin

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 874
  • País: mx
  • Karma: +1/-0
  • Sexo: Masculino
    • web
No sé si simplifique, ahí tu diras.

Si \( x=347^{231} \) y como \( 35=7*5 \), entonces usando el teorema chino puedes resolver el sistema:

\(
\begin{eqnarray}
x\equiv 347^{231} \equiv 2^{231}\equiv 2^3 \equiv 3 \mod 5 \\
x\equiv 347^{231}= 4^{231}\equiv 4^3 \equiv 1 \mod 7
\end{eqnarray}
  \)

y entonces por el teorema chino:

\( x=3(7)(3)+1(5)(3)+k(35)= 78+k(35)=8+k(35) \)
y entonces \( x\equiv 8 \mod 35 \)
Yoyontzin.

02 Abril, 2007, 04:43 am
Respuesta #2

Ked

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 945
  • Karma: +0/-0
  • Sexo: Masculino
Ya veo por donde venía la cosa, pero, para saber que \( 2^{231} \equiv 2^3 \!\!\pmod{5} \) y \( 4^{231} \equiv 1 \!\!\pmod{7} \), ¿qué hiciste? No usaste también la función \( \varphi \), ¿o lo hiciste por tanteo?

Quiero ver si existe alguna forma rápida de darse cuenta de estas cosas, sin tener que calcular \( \varphi \) todo el tiempo.

02 Abril, 2007, 04:47 am
Respuesta #3

Rogelio Yoyontzin

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 874
  • País: mx
  • Karma: +1/-0
  • Sexo: Masculino
    • web
pues si, digamos que use la \( \phi \), como \( \phi(5)=4 \) entonces reduje 231 modulo 4, y análogamente reduje 231 modulo 6 para la segunda congruencia.
Yoyontzin.

02 Abril, 2007, 04:49 am
Respuesta #4

Ked

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 945
  • Karma: +0/-0
  • Sexo: Masculino
Ahora si quedó clarísimo, gracias ;)

02 Abril, 2007, 04:56 am
Respuesta #5

Rogelio Yoyontzin

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 874
  • País: mx
  • Karma: +1/-0
  • Sexo: Masculino
    • web
Aunque en este caso, es muy fácil calcular las phi pues son números primos... y la reducción modulo 4 y 6 también son rápidas... no sé si exista una forma rápida de darse cuenta... o más rápida...
Yoyontzin.