lunes, 9 de agosto de 2010

Problema del Dia 10 de Agosto

Encuentra los últimos tres dígitos de $2003^{2002^{2001}}$.

23 comentarios:

Flavio dijo...
Este comentario ha sido eliminado por el autor.
Flavio dijo...

Lo que queremos encontrar es
$2003^{2002^{2001}} \pmod{1000}$
Pero $2003^{2002^{2001}} \equiv 3^{2002^{2001}} \pmod{1000}$
Como mcd(3,1000)=1 entonces por teorema de euler
$3^{\phi (1000)} \equiv 1 \pmod{1000}$
y $\phi(1000) = 400$
$\rightarrow 3^{2002^{2001}} \equiv 3^{2002^{2001} \pmod{400}} \pmod{1000}$
Entonces hay que encontrar
$2002^{2001}\equiv 2^{2001}\pmod{400}$
y basta encontrar
$2^{2001}\pmod{16}$
y
$2^{2001}\pmod{25}$
pero
$16=2^4$ entonces
$2^{2001}\equiv 0\pmod{16}$
Luego $\phi(25)=20$
y como mcd(2,25)=1
$2^{2001}\equiv 2^{2001\pmod{20}}\equiv 2\pmod{25}$
$2^{2001}\equiv 0\pmod{16}$
y
$2^{2001}\equiv 2\pmod{25}$
entonces la unica solucion por teorema chino del residuo es
$2^{2001}\equiv 352\pmod{400}$
$\rightarrow 3^{2002^{2001}} \equiv 3^{352}\equiv 9^{176} \pmod{1000}$
$\rightarrow 3^{2002^{2001}} \equiv (10-1)^{176} \pmod{1000}$
$\rightarrow 3^{2002^{2001}} \equiv \binom{176}{2}10^2(-1)^{174}+\binom{176}{1}10^1(-1)^{175}$
$+\binom{176}{0}10^0(-1)^{176} \pmod{1000}$
$\rightarrow 3^{2002^{2001}} \equiv \frac{100\cdot 176 \cdot 175}{2}-176\cdot 10+1 \pmod{1000}$
$\rightarrow 3^{2002^{2001}} \equiv 100\cdot 88 \cdot 175-1760+1 \pmod{1000}$
$\rightarrow 3^{2002^{2001}} \equiv 100\cdot 2\cdot 44 \cdot 5\cdot 35-760+1 \pmod{1000}$
$\rightarrow 3^{2002^{2001}} \equiv -760+1 \equiv -759 \equiv 241 \pmod{1000}$
Entonces las ultimas 3 cifras de
$2003^{2002^{2001}}$ son 241

Enrique Treviño dijo...

Buen trabajo Flavio. Yo cuando vi $3^352$ se me hizo dificil ver como terminar y me fui por otro lado en la solución. Esta padre la tuya.

Georges dijo...
Este comentario ha sido eliminado por el autor.
Georges dijo...

Yo llegue de la misma forma que Flavio a que $2003^{2002^{2001}} \equiv 3^{352} \pmod{1000}$
Luego vemos que $3^{352} \equiv 1 \pmod{8}$
Y que $\phi (125)=100$ por lo tanto $3^{100} \equiv 1 \pmod{125}$ y entonces $(3^{50}-1)(3^{50}+1) \equiv 0 \pmod{125}$ Pero como estos productos difieren en 2, su maximo comun divisor es 2 y entonces $3^{50} \equiv 1$ ó $-1$ Pero si $3^{50} \equiv 1$ entonces $3^{352} \equiv 9$ y entonces resolviendo el sistema de congruencias obtenemos que $3^{352} \equiv 9 \pmod {1000}$ y por lo tanto $\pmod {10} $ Pero es facil ver que $3^{352} \equiv 1 \pmod {10}$ por lo tanto tenemos una contradicción. Por lo tanto $3^{50} \equiv -1 \pmod {125}$ y entonces $3^{352} \equiv 9 \pmod {125}$ por lo tanto resolviendo el sistema de congruencias vamos a obtener que $3^{352} \equiv 241 \pmod {1000}$
Por lo tanto $2003^{2002^{2001}}$ acaba en 241. Fin

Georges dijo...

Me falto un menos.. al final vamos a obtener que $3^{352} \equiv -9 \pmod {125}$ en vez de $\equiv 9$ y luego ya resuelves el sistema
$3^{352} \equiv {-9} \pmod {125}$
$3^{352} \equiv 1 \pmod {8}
Y obtienes que acaba en 241

Enrique Treviño dijo...

Georges, esta buena la tecnica de observar modulo 10 para ayudarte con modulo 1000.
La manera que yo resolvi $3^{52} \pmod{125}$ fue la siguiente. $3^100 \equiv 1 \pmod{125}$, por lo tanto usando la ley de la reciprocidad cuadratica: $3^50 \equiv \left(\frac{3}{125}\right) \equiv \left(\frac{125}{3}\right) \equiv \left(\frac{2}{3}\right) \equiv -1 \pmod{125}$

Manuel Dosal dijo...
Este comentario ha sido eliminado por el autor.
Manuel Dosal dijo...
Este comentario ha sido eliminado por el autor.
Manuel Dosal dijo...

Solucion.
Primero lo que necesitamos es $2003^{2002^{2001}}\pmod{1000}$, entonces veamos que $2003^{2002^{2001}}\equiv 3^{2002^{2001}}\equiv 3^{2k}\equiv 9^{k}\equiv 1\pmod{8}$.
Luego veamos cuanto es $2003^{2002^{2001}}\pmod{125}$, que es $3^{2002^{2001}}\pmod{125}$, pero $(3,125)=1$, entonces $3^{\phi(125)}\equiv 1\pmod{125}$ $\rightarrow 3^{100}\equiv 1\pmod{125}$, entonces necesitamos $2002^{2001}\pmod{100}$ $\rightarrow 2^{2001}\pmod{100}$.
Veamos que $2^{2001}\equiv 0\pmod{4}$ y veamos cuanto es $2^{2001}\pmod{25}$ pero $(2,25)=1$ $\rightarrow 2^{\phi(25)}\equiv 0\pmod{25}$ $\rightarrow 2^{2001}\equiv (2^{2000})(2)\pmod{25} \rightarrow 2^{2001}\equiv 2\pmod{25}$ y $2^{2001}\equiv 0 \pmod{4}$
Ahora la unica congruencia $\pmod{100}$ que es $2 \pmod{25}$ y $0 \pmod{4}$ es $52$. Por lo tanto $2^{2001}\equiv 52\pmod{100}$ y entonces $3^{2002^{2001}}\equiv 3^{52}\pmod{125}$.
Y sabemos que $3^{5}\equiv 243\equiv -7\pmod{125}$$\rightarrow 3^{52}\equiv (3^{50})(3^{2})\pmod{125}$
$(3^{50})(9)\equiv (3^{5})^{10}(9)\equiv (-7)^{10}(9)\equiv (7^{10})(9)\pmod{125}$
$7^{3}\equiv 343\equiv -32\pmod{125}$$\rightarrow (7^{10})(9)\equiv (7^{3})^{3})(7)(9)\equiv(-32)^{3}(63)\pmod{125}$$\rightarrow (-32768)(63)\equiv (-18)(63)\pmod{125}$ ya que $-32750 \equiv 0\pmod{125}$$\rightarrow (-18)(63)\equiv -1134 \equiv -9\pmod{125}$ entonces $2003^{2002^{2001}}\equiv -9\pmod{125}$ y $2003^{2002^{2001}}\equiv 1\pmod{8}$ entonces la unica congruencia $\pmod{1000}$ $1 \pmod{8}$ y $-9 \pmod{125}$ es $241$. Por lo tanto $2003^{2002^{2001}}\equiv 241\pmod{1000}$.FIN.

Flavio dijo...

no me queda claro por que $3^{50}\equiv \left(\frac{3}{125}\right) \pmod{125}$

Unknown dijo...

También ya tengo este, espero mañana tener tiempo para postearlo, es que ya entré a clases y esta semana estoy todavía en Toluca, iendo diario a la UNAM...

Enrique Treviño dijo...

Flavio,
Como $3^{100} \equiv 1 \pmod{125}$ entonces $3^{50}\equiv 1 o -1$. Si es $1$ entonces $3$ es residuo cuadratico, si es -1 entonces no lo es. Lo cual se expresa con el simbolo de Jacobi $\left(\frac{3}{125}\right) (Nota: el simbolo de Jacobi es una generalizacion del simbolo de Legendre. Tambien cumple la ley de la reciprocidad cuadratica).

DANIELIMO dijo...
Este comentario ha sido eliminado por el autor.
DANIELIMO dijo...
Este comentario ha sido eliminado por el autor.
DANIELIMO dijo...
Este comentario ha sido eliminado por el autor.
DANIELIMO dijo...

vemos que:
lo que buscamos es congruente con $1 \pmod{8}$.
$2002^{2001} \equiv 2^{100\phi(25)+1} \equiv 2 \pmod{25}$ y $2002^{2001} \equiv 0 \pmod{4} $ por lo tanto $ 2002^{2001} \equiv 52 \pmod{100} \equiv 2 \pmod{50} $ vemos que $ 3^{50} \equiv -1 \pmod{125} $ y como $\phi(125)=100$ lo que buscamos es congruente con $(-1)(3^2) \pmod{125}$ y de ahi encontramos que lo que buscamos es congruente con $241 \pmod{1000}$ y por lo tanto termina en 241

Unknown dijo...

Hola, se que esto no va aquí pero tengo problemas para acceder.
El problema del día 11 es el siguiente:
Probar que la secuencia 1, 11, 111,... contiene una subsecuencia de primos relativos por parejas.

Flavio dijo...

Con respecto a lo que decia quique de que 3^50 congruente a (3/125) no es cierto siempre por que el simbolo de jacobi no es reciproco, o sea si (a/n)=-1 entonces a no es residuo cuadratico mod n, pero si es 1 no necesariamente a es residuo cuadratico, aunque creo que para n potencia de primo si se cumple (no estoy seguro), pero de cualquier manera lo usas como si fuera cierto siempre.

Enrique Treviño dijo...

Tienes razon Flavio. Si $125$ fuera primo, entonces la ecuacion seria cierta.

Ahora si $\left(\frac{3}{125}\right) = -1$ entonces $3$ no es residuo cuadratico. Por lo tanto para ningun $x$ tenemos que $x^2 \equiv 3 \pmod{125}$. Por lo tanto $(x^2)^{50} \not\equiv 3^{50} \pmod{125}$, por lo tanto $1 \not\equiv 3^{50} \pmod{125}$. Por lo tanto $3^{50} \equiv -1 \pmod{125}.$

En resumen, en el caso que $\left(\frac{a}{p^k}\right) = -1$ tenemos que $a^{\frac{\phi(p^k)}{2}} = \left(\frac{a}{p^k}\right)$. En el caso que $\left(\frac{a}{p^k}\right) = 1$ no podemos garantizar que $a^{\frac{\phi(p^k)}{2}} = \left(\frac{a}{p^k}\right)$.

Flavio dijo...

Pues eso de que $\left(x^2\right)^50 \not\equiv 3^{50} \pmod{125}$ como que no es un argumento valido (por ejemplo 3 no es congruente a 4 pero 3^100 si es congruente a 4^100 mod 125)mas bien podrias ver que hay 50 residuos cuadraticos, los cuales cumplen que a la 50 dan 1 y que esa ecuacion entonces no tiene mas de 50 soluciones, entonces $3^50 $ no puede dar 1 y entonces debe dar -1 (para cualquier residuo no cuadratico)

Enrique Treviño dijo...

Tienes razon de que mi argumento no es valido. Tu argumento es correcto, pero es dificil de demostrar. Para demostrar que hay 50 residuous cuadraticos, necesitas saber que 125 tiene una raiz primitiva. Un teorema nos dice que los modulos que tienen raices primitivas son $1,2,4,p^k, 2\times p^k$ para todo primo impar.

José Luis Miranda Olvera dijo...
Este comentario ha sido eliminado por el autor.

Publicar un comentario