Autor Tema: Problema calculando restos mediante congruencias

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

06 Septiembre, 2009, 10:32 pm
Leído 1620 veces

Sanva

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 27
  • Karma: +0/-0
  • Sexo: Masculino
Hola!

Mi problema es que no entiendo un ejercicio de los apuntes de Teoría de Números.

La teoría es la siguiente:

Sean \(  \{a_i; i=1,...n\} \) y \( \{b_i; i=1,...n\} \) enteros tales que \( a_i \equiv_m b_i \) para cada \( 1 \leq i \leq n \). Entonces:
\( \displaystyle\sum_{i=1}^n{ a_i \equiv_m \sum_{i=1}^n{b_i}  } \)
y
\( \displaystyle\prod_{i=1}^n{ a_i \equiv_m \prod_{i=1}^n{b_i}  } \)

Junto con el siguiente ejercicio resuelto:

Hallar el resto de la división de \( 37^{7541} \) entre 7.

Puesto que \( 37 \equiv_7 7 \) y que \( 2^3 \equiv_7 1 \), basta tener en cuenta que:
\( 37^{7541} \equiv_7 2^{2513 \cdot 3 + 2} \equiv_7 2^{3^{2513}} \cdot 2^2 \equiv_7 4 \)

Primero... \( 37 \equiv_7 7 \) es una errata, o eso o ya paso de ir al examen. Supongo que sería \( 37 \equiv_7 2 \).

Realmente no logro comprender el ejercicio, y se que es realmente importante —cae en el examen fijo.

¿Alguien sabría explicármelo?

Muchas gracias por vuestro tiempo.

06 Septiembre, 2009, 11:03 pm
Respuesta #1

Teón

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,369
  • Karma: +0/-0
  • Sexo: Masculino
  • C:.J:.T:.
Hola.
\( 37\equiv_7 2 \)
Por otro lado las potencias de 2 módulo 7 son 2,4,1; de esto surge

\( 2^{3k+i}\equiv_7 2^i \mbox{ con } k\in \mathbb{N}_0\; y\; 0\leq i\leq 2 \)

Como \( 7541 \equiv_3 2\Rightarrow 2^{7541}\equiv_7 2^2\equiv_7 4 \)

Saludos.
Eram quod es, eris quod sum.

07 Septiembre, 2009, 12:01 am
Respuesta #2

Sanva

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 27
  • Karma: +0/-0
  • Sexo: Masculino
Ufff... si bien tu forma de resolver el ejercicio me gusta mucho más —parece que sigues un método reproducible, mientras que los pasos de la versión de los apuntes me parecían mágicos o algo así xDDD— sigo sin entenderlo...

Supongo que al ser 37 congruente con 2 módulo 7 puedo utilizar al 2 elevado a algo para reemplazar al 37... y ese algo según tú es \( 3k + i \)... pero no entiendo porqué esa k puede ser cualquier natural al que le sumas 0, 1 o 2... además, ¿\( 2^{3k+i} \) con k un natural cualquiera e i igual a 0, 1 o 2 no es decir exactamente lo mismo que simplemente elevar 2 a cualquier número?

Lamento tener que pedírtelo pero... ¿podrías explicarmelo de una forma un poco más detallada?

07 Septiembre, 2009, 01:29 am
Respuesta #3

Teón

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,369
  • Karma: +0/-0
  • Sexo: Masculino
  • C:.J:.T:.
Hola.
Resulta, que las potencias de 2 módulo 7, serán: 2,4,1,2,4,1....

Es decir

\(
\begin{eqnarray}
2^{3k} &\equiv_7& \left( 2^3\right)^k\\
 &\equiv_7& 1^k\\
&\equiv_7& 1\\[.6cm]
2^{3k+1} &\equiv_7& 2^{3k}2\\
&\equiv_7& 1\times 2\\
&\equiv_7& 2\\[.6cm]
2^{3k+2} &\equiv_7& 2^{3k}2^2\\
&\equiv_7& 1\times 4\\
&\equiv_7& 4
\end{eqnarray}
 \)

Es importante tener en cuenta que

\( (kp+h)^n\equiv_p h^n \)
Ya que
\(
\setcounter{equation}{9}
\begin{eqnarray}
(kp+h)^n &=& \displaystyle\sum_{i=0}^n\displaystyle\binom{n}{i}(kp)^ih^{n-i}\\
&=& h^n+\displaystyle\sum_{i=1}^n\displaystyle\binom{n}{i}(kp)^ih^{n-i}\\
&=& h^n+\displaystyle kp\sum_{i=1}^n\displaystyle\binom{n}{i}(kp)^{i-1}h^{n-i}\\
&\equiv_p& h^n
\end{eqnarray}
 \)

Saludos.
Eram quod es, eris quod sum.

09 Septiembre, 2009, 12:42 pm
Respuesta #4

Sanva

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 27
  • Karma: +0/-0
  • Sexo: Masculino
Sí, esto ya es otra cosa.

Muchas gracias por tu ayuda!