Autor Tema: Dos congruencias con dos primos

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

03 Abril, 2007, 01:57 am
Leído 1676 veces

Ked

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 945
  • Karma: +0/-0
  • Sexo: Masculino
Si p y q son dos primos distintos tal que \( a^p \equiv a \!\!\!\pmod q \) y \( a^q \equiv a \!\!\!\pmod p \), demostrar que \( a^{pq} \equiv a \!\!\!\pmod {pq} \)

No sé si hay algo muy obvio que no estoy viendo, pero probé varias cosas y no llego a nada. Acá van algunas de las cosas que hice:

PRIMERA IDEA
Spoiler
\( a^p \equiv a _{\;(q)} \Rightarrow a = a^p + k_1q \)
\( a^q \equiv a _{\;(p)} \Rightarrow a^p + k_1q \equiv a _{\;(p)} \Rightarrow k_1q \equiv a-a^p _{\;(p)} \)

Por Fermat, \( q^{p-1} \equiv 1 _{\;(p)} \), entonces:
\( k_1 q q^{p-2} \equiv k_1 \equiv q^{p-2}(a-a^p) _{\;(p)} \Rightarrow k_1 = q^{p-2}(a-a^p) + k_2 p \)

Sustituyendo \( k_1 \) en \( a = a^p + k_1q \) queda:
\( a = a^p + (q^{p-2}(a-a^p) + k_2 p)q = a^p + q^{p-1}(a-a^p) + k_2pq \)

Llegamos a:
\( a \equiv a^p + q^{p-1}(a-a^p) _{\;(pq)} \)

Acá probé reordenar, factorizar, pero no llego a nada. No sé cómo ver que eso también es congruente con \( a^{pq} \)
[cerrar]

SEGUNDA IDEA
Spoiler
Otra cosa que probé fue factorizar \( \displaystyle a^{pq}-a = a(a-1)\sum_{k=0}^{pq-2}{a^{pq-2-k}} \) pero no llego por ningún lado a ver que eso es múltiplo de pq.
[cerrar]

Capaz me fui por las ramas y todo era mucho más simple. A ver si me iluminan :P

03 Abril, 2007, 02:23 am
Respuesta #1

Rogelio Yoyontzin

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 874
  • País: mx
  • Karma: +1/-0
  • Sexo: Masculino
    • web
Hola Ked,

\( a^p\equiv a \mod q \Rightarrow a^{pq}=(a^p)^q\equiv a^q\equiv a \mod q \)

La última congruencia es el teorema de Fermat.

Lo mismo lo haces pero ahora modulo p.

\( a^{pq}\equiv a^p\equiv a \mod p \)

por lo que tanto \( p \) como  \( q \) dividen a \( a^{pq}-a \) y entonces su producto lo ha de dividir, esto es, \( a^{pq}\equiv a \mod pq \)
Yoyontzin.

03 Abril, 2007, 02:28 am
Respuesta #2

Ked

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 945
  • Karma: +0/-0
  • Sexo: Masculino
Y tan fácil que era... definitivamente me iba por las ramas :P

Saludos y gracias