Autor Tema: Congruencia

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

07 Diciembre, 2007, 12:09 am
Leído 2822 veces

Buti

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 14
  • Karma: +0/-0
Necesito que me orienten para poder resolver este ejercicio:
Hallar todos los naturales tal que
25n ≡ 3n (mód 16.17)

En primer lugar planteo que se debe cumplir simultáneamente que 16 divida a 25n-3n y 17 divida a 25n-3n

Lo encaro por separado, mi idea es armar dos tablas de posibles restos y compararlas. Cuando un determinado n tenga el mismo resto para 16 y para 17, entonces satisface.

Para encontrar todos los restos de 16 no tengo problemas porque 25n es múltiplo de 16 y el problema se reduce a hallar los restos de 3n.

Cuando quiero calcularlos para módulo 17, los números se me hacen inmanejables. Lo estoy tratando de resolver así:
Expreso 25n como 32n y uso Fermat aprovechando que 32 y 17 son coprimos, y 17 es primo.

3216 ≡ 1 (mód 17)
Expreso n como n = 16k + r , donde r es el resto y 0<ó= r < 16. Luego:

3216k + r ≡ 32r (mód 17)
y mi planteo se completa con que

32r ≡ 3n (mód 17)

y después de hallar todos los restos compararlos con los de módulo 16.

No "siento" que mi razonamiento esté mal, pero sí lo siento tremendamente retorcido y laborioso. ¿En qué me estoy confundiendo? ¿Cómo me conviene encarar el problema para que sea más facil de resolver?
Gracias.

07 Diciembre, 2007, 05:04 am
Respuesta #1

Rogelio Yoyontzin

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 874
  • País: mx
  • Karma: +1/-0
  • Sexo: Masculino
    • web
Tienes que resolver estas dos congruencias y luego puedes usa rel teorema chino del residuo:

  • \( 32^n=3n (\mod16) \)  y
  • \( 32^n=3n (\mod 17) \)

entonces como \( 32=0 (\mod 16) \) se tiene que la primer congruencia es equivalente a resolver \( 3n=0 (\mod 16)\iff n=0 \mod 16 \). 

como \( 32\cong -2 \mod 17 \) entonces tu segunda congruencia es equivalente a
\( (-2)^n= 3n \mod 17 \).

Yoyontzin.

11 Diciembre, 2007, 06:10 am
Respuesta #2

juanmaflyer

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 13
  • Karma: +0/-0
  • Sexo: Masculino
Y en ese caso puede usar Teorema Chino del Resto por el hecho de que 16 y 17 son coprimos cierto? Si fueran otros números NO coprimos no se podría usar teorema chino del resto o si?

Bien entendí la primera congruencia, ahora la segunda, o sea esta:

\( (-2)^n \equiv{3n} (17) \) no se me ocurre otra manera de hallarla más que usando una tabla de congruencia y pequeño teorema de fermat.

30 Julio, 2008, 01:27 pm
Respuesta #3

bepro

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 331
  • Karma: +0/-0
  • Sexo: Masculino
    • GENERALIZACION DE LA REGLA DE RUFFINI
Quizás se pueda resolver tomando indices es decir:\(  n\cdot{ind(-2)}\equiv{ind(3n)}(mod\phi(17)) \),utilizando las propiedades de los indices y de la función de Euler obtenemos\(  n\cdot{ind (-1)}+n\cdot{ind 2}\equiv{ind 3}+ind n` \)( mod 16)como\(  ind(-1)=\displaystyle\frac{\phi(16)}{2} pero \phi(16)=2^4-2^3=8\Rightarrow{ind(-1)=\displaystyle\frac{8}{2}=4} \)luego \(  4\cdot{n}+14\cdot{n}\equiv{1+ind n} \)( mod 16 )es decir \(  18\cdot{n}\equiv{1+ind n} \)( mod 16)pero para que ésta congruencia tenga solución debe de cumplirse que \( 1+ind n\equiv{0} \)(mod 2) donde ind n se toma respecto a 17.De aquí se deduce que ind n solamente puede ser un número impar. Por ejemplo si n=3 ind 3 es 1 luego tenemos que \( 1+ind 3=2\equiv{0} \)(mod 2), luego la ecuación que tenemos que resolver nos queda \( 54\equiv{2} \) (mod 16) es decir que \( 17\equiv{1} \)( mod 8) la cual siempre es cierta.
Saludos

31 Julio, 2008, 10:43 am
Respuesta #4

Buti

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 14
  • Karma: +0/-0
Muchas gracias bepro por la aportación.