Autor Tema: Hallar resto y cociente

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

14 Diciembre, 2009, 10:29 pm
Leído 2218 veces

niniodinho

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 188
  • Karma: +0/-0
  • Sexo: Masculino
Hola gente. Tengo un ejercicio que me pide calcular cociente y resto de dividir \( 2004^{16.949.687} \) por \( 1373 \). Aplicando teorema de fermat llegué a que la primera expresión es congruente con \( 631 \) \( mod \) \( 1373 \). Hasta eso estará bien? No subo el desarrollo porque estoy con el móvil. Muchas gracias

15 Diciembre, 2009, 10:37 am
Respuesta #1

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

 No estoy seguro de a que te refieres con "la primera expresión".

 Es claro que trabajando módulo \( 1373 \):

\(  2004\equiv{}631 \)

 Por otra parte como \( 1373 \) es primo, por el pequeño teorema de Fermat:

\(  a^{1373-1}\equiv 1 \) para cualquier \( a\not\equiv 1373 \)

 Por tanto:

\(  2004^{16949687}\equiv 631^{16949687}\equiv 631^{12353\cdot 1372+1371}\equiv 631^{1371}\equiv 631^{-1} \)

 Tu problema se reduce a calcular el inverso de \( 631 \) módulo \( 1373 \). Equivalentemente a resolver esta ecuación:

\(  631x\equiv 1\mbox{ mod }1373 \)

 y a su vez a resolver esta ecuación diofántica:

\(  631x+1373k=1 \)

 Para esto último puedes usar el algoritmo extendido de euclides.

Saludos.

16 Diciembre, 2009, 10:57 am
Respuesta #2

Teón

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,369
  • Karma: +0/-0
  • Sexo: Masculino
  • C:.J:.T:.
Hola.

Aún si no te tocara trabajar con un número primo como 1373, puedes utilizar la función \( \varphi \) de Euler.
En nuestro caso particular de:

\( \\ \omega=16949687\\
n=1373\\
 \)

Obtenemos

\(
\\
2004\equiv 631 \mod n\\
\omega \equiv \varphi(n)-1 \mod \varphi(n)\\
 \)

Luego:

\( \begin{eqnarray}
2004^\omega &\equiv& 631^\omega\mod n\\
&\equiv&  631^{k\varphi(n)+\varphi(n)-1}\mod n\\
&\equiv& 631^{-1} \mod n\\
&\equiv& 235 \mod n
\end{eqnarray}
 \)

El resultado de la (4) se puede obtener por medio del algoritmo de Euclides, como dice El-Manco.

Saludos.
Eram quod es, eris quod sum.

27 Enero, 2010, 07:20 pm
Respuesta #3

niniodinho

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 188
  • Karma: +0/-0
  • Sexo: Masculino
Hola. Estoy retomando este tema de estudio, por lo que revivo este posteo. Mi pregunta es si llegas a la siguiente congruencia por aplicar nuevamente el teorema pequeño de Fermat \( 631^{1371}\equiv 631^{-1} \).
Luego, la ecuación modular que planteas es para cualquier caso general?
Gracias

27 Enero, 2010, 07:42 pm
Respuesta #4

Teón

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,369
  • Karma: +0/-0
  • Sexo: Masculino
  • C:.J:.T:.
Hola.

Hola. Estoy retomando este tema de estudio, por lo que revivo este posteo. Mi pregunta es si llegas a la siguiente congruencia por aplicar nuevamente el teorema pequeño de Fermat \( 631^{1371}\equiv 631^{-1} \).
Es el paso que me falta para entender el ejercicio.
Gracias

Sabiendo que \( \varphi (1373)=1372 \),
se tiene

\(
\begin{eqnarray}
631^{1371} &=& 631^{\varphi (1373)-1}\\
&=& 631^{\varphi (1373)}631^{-1}\\
&\equiv & 1\times 631^{-1}\mod 1373
\end{eqnarray}
 \)

Saludos.
Eram quod es, eris quod sum.

27 Enero, 2010, 07:45 pm
Respuesta #5

niniodinho

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 188
  • Karma: +0/-0
  • Sexo: Masculino
Aa, entiendo. Y luego plantea una ecuación modular. ¿Esto es siempre así ó lo es sólo para este caso por estar buscando el inverso de 631?
Muchas gracias

27 Enero, 2010, 07:52 pm
Respuesta #6

Teón

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,369
  • Karma: +0/-0
  • Sexo: Masculino
  • C:.J:.T:.
Hola.

Aa, entiendo. Y luego plantea una ecuación modular. ¿Esto es siempre así ó lo es sólo para este caso por estar buscando el inverso de 631?
Muchas gracias

La ecuación modular la planteo para hacer
\( 631^{\varphi(1373)}\equiv 1 \mod 1373 \)

En realidad las igualdades las he utilizado con el fin de dar más claridad al desarrollo.
Pero pude haber planteado todas congruencias.

Saludos.
Eram quod es, eris quod sum.