Foros de matemática
18/11/2017, 01:29:10 am *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.
¿Perdiste tu email de activación?

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: Homenaje a NUMERARIUS
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: Hallar resto de división mas rápidamente  (Leído 251 veces)
0 Usuarios y 1 Visitante están viendo este tema.
mathspirit
Semi pleno
***

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 64


Ver Perfil
« : 18/06/2017, 10:27:56 pm »

Tengo que hallar el resto de [texx]3^{385}[/texx] por 400.

Puedo sacarlo de esta manera:

[texx]3^{385} = 3.3^{384} = 3. 9 ^{192} = 3 . 81 ^{96} = 3. 6561^{48} = 3 . 161^{48} [/texx] ... etc.

Pero me pregunto si hay alguna propiedad o forma mas eficiente de hacerlo.

Gracias!
En línea
ingmarov
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Honduras Honduras

Mensajes: 3.657



Ver Perfil
« Respuesta #1 : 19/06/2017, 01:34:22 am »

Hola

Teorema de Fermat-Euler te servirá

Mira este hilo

http://rinconmatematico.com/foros/index.php?topic=87357.msg350516#msg350516


Y un vídeo

https://youtu.be/Zthnjzyd_RE


Yo no lo he utiliado hasta hoy (si mal no recuerdo) y llego hasta

[texx]3^{385}\equiv 3^{65}(mod\; 400)[/texx]

Creo que se puede continuar así Ah! esta es la forma que tu usas.

Fallé en algún punto y obtuve un resultado incorrecto

Spoiler (click para mostrar u ocultar)
Saludos

En línea

No te confíes, revisa lo que escribo. Yo también me equivoco.
Ignacio Larrosa
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 1.576


Ver Perfil WWW
« Respuesta #2 : 19/06/2017, 05:09:05 am »

Tengo que hallar el resto de [texx]3^{385}[/texx] por 400.

Puedo sacarlo de esta manera:

[texx]3^{385} = 3.3^{384} = 3. 9 ^{192} = 3 . 81 ^{96} = 3. 6561^{48} = 3 . 161^{48} [/texx] ... etc.

Pero me pregunto si hay alguna propiedad o forma mas eficiente de hacerlo.

Gracias!

El teorema de Euler-Fermat te asegura que  [texx]a^{\varphi(n)}\equiv{}1 \;(\textrm{mod }n)\textrm{ si mcd}(a, n) = 1[/texx], donde [texx]\varphi(n)[/texx] es la función totient de Euler, que cuenta el número de enteros positivos menores que [texx]n[/texx] y primos con [texx]n[/texx]. Esta función es multiplicativa, de manera que [texx]mcd(a, b) = 1\; \Rightarrow{}\; \varphi(ab)=\varphi(a)\cdot{}\varphi(b)[/texx]. Además se comprueba fácilmente que si [texx]p[/texx] es primo, [texx]\textcolor{red}{\varphi(p^k) = p^k - p^{k-1}}[/texx]. Por tanto,

[texx]\varphi(400) = \varphi(2^4\cdot{}5^2)=(16-8)(25-5) = 160[/texx]

Por tanto,

[texx]3^{385} = 3^{2\cdot{}160 + 65} = (3^{160})^2\cdot{}3^{65}\equiv{}1^23\cdot{}^{65} \equiv{} 3^{65} \;(\textrm{mod }400)[/texx]

Para calcular esta última potencia, descomponemos [texx]65[/texx] en suma de potencias de [texx]2[/texx], equivalente a expresarlo en base [texx]2[/texx]:

[texx]65 = 64 + 1 \;\Longrightarrow{}\;3^{65}=3^{64}\cdot{}3^1[/texx]

Por elevaciones sucesivas al cuadrado hallamos estás potencias de [texx]3 \;(\textrm{mod }400)[/texx]

[texx]3^1 \equiv{} 3\;(\textrm{mod }400)[/texx]

[texx]3^2 \equiv{} 9\;(\textrm{mod }400)[/texx]

[texx]3^4 \equiv{} 81\;(\textrm{mod }400)[/texx]

[texx]3^8 \equiv{} 81^2 \equiv{} 6561 \equiv{} 161\;(\textrm{mod }400)[/texx]

[texx]3^{16} \equiv{} 161^2   \equiv{}25921\equiv{}321\;(\textrm{mod }400)[/texx]

[texx]3^{32} \equiv{} 321^2   \equiv{}103041\equiv{}241\;(\textrm{mod }400)[/texx]

[texx]3^{64} \equiv{} 241^2   \equiv{}58081\equiv{}81\;(\textrm{mod }400)[/texx]


Entonces,

[texx]3^{65} \equiv{} 81\cdot{}3 \equiv{}243 \;(\textrm{mod }400)[/texx]

El Teorema de Euler-Fermat nos garantiza que [texx]a^{\varphi(n)}\equiv{}1 \;(\textrm{mod }n)[/texx], pero no que [texx]\varphi(n)[/texx] sea el mínimo exponente para el que ocurre esto. Ahora bien, si hay otro, más pequeño, debe ser un divisor de [texx]\varphi(n), \textcolor{red}{160}[/texx] en nuestro caso. Un cálculo similar al que se ha echo para [texx]3^{65}[/texx] nos convencería de que [texx]20[/texx] es el mínimo exponente [texx]k[/texx] para el que [texx]3^k = 1 \;(\textrm{mod }400), 20[/texx] es el orden de [texx]3\;(\textrm{mod }400)[/texx], con lo que [texx]3^{385}\equiv{}3^5\equiv{}243\;(\textrm{mod }400)[/texx]. Lo que en este caso supone un importante ahorro.

Saludos,
En línea

Daría todo lo que se por la mitad de lo que ignoro (R. Descartes)
O incluso por mucho menos ...
mathspirit
Semi pleno
***

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 64


Ver Perfil
« Respuesta #3 : 24/06/2017, 04:34:12 pm »

Muchas gracias a ambos!

ilarrosa, me sirvió la primera parte y la segunda tardé en entenderla pero la entendí y parece super útil!  Mas que nada porque puede comprobarse con la calculadora, que [texx]3^{20} \equiv{1} (mod400)[/texx] y de ahí reducir rápidamente el resto de las cuentas. Porque para números mas grandes, por algún motivo no sirve (ej: [texx]3^{40}[/texx]), calculo que tiene que ver con la representación de estos números en formato binario.
En línea
Ignacio Larrosa
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 1.576


Ver Perfil WWW
« Respuesta #4 : 24/06/2017, 08:26:59 pm »

Muchas gracias a ambos!

ilarrosa, me sirvió la primera parte y la segunda tardé en entenderla pero la entendí y parece super útil!  Mas que nada porque puede comprobarse con la calculadora, que [texx]3^{20} \equiv{1} (mod400)[/texx] y de ahí reducir rápidamente el resto de las cuentas. Porque para números mas grandes, por algún motivo no sirve (ej: [texx]3^{40}[/texx]), calculo que tiene que ver con la representación de estos números en formato binario.

No consigo entender a que te refieres aquí. De todas formas había un error en mi mensaje, donde decía:

"Ahora bien, si hay otro, más pequeño, debe ser un divisor de [texx]\varphi\ (n),\; 40[/texx] en nuestro caso."

Debería decir:

"Ahora bien, si hay otro, más pequeño, debe ser un divisor de [texx]\varphi\ (n),\; 160[/texx] en nuestro caso."

Ahora lo corrijo.

Saludos,

En línea

Daría todo lo que se por la mitad de lo que ignoro (R. Descartes)
O incluso por mucho menos ...
Páginas: [1]   Ir Arriba
  Imprimir  
 
Ir a:  

Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.1 | SMF © 2006, Simple Machines LLC XHTML 1.0 válido! CSS válido!