Olimpiada Propuesto: Calcular las últimas cifras de un número

[angel relativamente]

Hola compañeros, dejo aquí la modificación de un problema que me he encontrado en un libro con problemas tipo olimpiada, para quien esté practicando o para quien le apetezca divertirse resolviéndolo.

Calcula las 500 últimas cifras del número $2017^{2000!}$

¡Suerte!

[Richard R Richard]

Re: Propuesto: Calcular las últimas cifras de un número

Yo colaboro dando la ultima, les dejo las siguientes 499 a ustedes

Ocultar contenido

Mostrar solución Ocultar solución

1


bonito problema angel pero no me le atrevo, segfuro que la cosa va por el lado de los Logaritmos

[angel relativamente]

Re: Propuesto: Calcular las últimas cifras de un número

Hola Richard, es correcta la última cifra. Quizá sería interesante que dijeses, aunque sea solo el 0.2% de la respuesta, cómo has llegado a ella. De paso dejo una pista, el problema no es nada trivial


PISTA:

Ocultar contenido

Mostrar solución Ocultar solución

Encontrar las 500 últimas cifras equivale a encontrar el resto $R$ de la division por $10^{500}$, o equivalentemente, encontrar $R$ tal que $2017^{2000!}\equiv R \left(\text{mod} 10^{500} \right)$

[Richard R Richard]

Re: Propuesto: Calcular las últimas cifras de un número

Hola angel

Ocultar contenido

Mostrar solución Ocultar solución

la solucion consiste en presentar la fórmula o un metodo algoritmico con la que la obtendría las 500 cifras , o es presentar las 500 cifras una detrás de la otra? ,

había pensado contestar continuando el miniaporte , que lo que estamos buscando es lo que quedaba después de la coma luego de dividir efectivamente por 10^{500} Sabia que se podia usar Mod, pero como no supe como continuar, preferi no decirlo.

La ultima cifra la obtengo por este planteo , el ultimo número de 2017 es un 7 cuando lo elevas a un exponente x hay una serie periódica que se repite en el ultimo numero por ej

$7^0=1\quad \to 1$
$7^1=7\quad \to 7$
$7^2=49\quad \to 9$
$7^3=343\quad \to 3$
$7^4=2401\quad \to 1$
$7^5=16807\quad \to 7$
$7^6=117649\quad \to 9$
......

es decir la serie 1793 se repite como último número dando 1 cuando el exponente es divisible por 4

como cualquier factorial de un numero mayor a 4 es divisible por 4 , el factorial de 2000 lo será y entonces cualquier número terminado en 7 elevado a esa potencia tendrá un 1 como ultima cifra.

Saludos

[angel relativamente]

Re: Propuesto: Calcular las últimas cifras de un número

Ocultar contenido

Mostrar solución Ocultar solución

La clásica de estudiar el patrón, lástima que para más de 1 cifra no suele ser viable.
No hay que dar algoritmo de cálculo hay que darlas todas, como tú dices, una detrás de otra. Obviamente no son totalmente aleatorias y siguen algún patrón para que sea cómodo de explicitar. En cualquier caso el problema no es tanto de siéntate y calcula, es más de intuir una solución y demostrar que en efecto lo es.

-Añadido-

Como el problema es muy complicado, voy a dar la solución de cómo calcular la siguiente cifra. Si se entiende debería ser fácil generalizarlo y sacar las 498 restantes, si no lo hace nadie dare la respuesta definitiva en un par de días. Primeramente dare una pista para quien quiera seguir pensándolo y esté atascado, y después escribo la solución particular para la penúltima cifra.

PISTA:

Ocultar contenido

Mostrar solución Ocultar solución

Conviene conocer el teorema de Euler: Si $a,n$ son enteros primos relativos entonces $a^{\varphi(n)} \equiv 1 \left(\text{mod} \; n \right)$. Obviamente hay que saber qué es la función $\varphi$ de Euler y sus propiedades

SOLUCIÓN (particular)
-SPOILER ALERT-

Ocultar contenido

Mostrar solución Ocultar solución

Para calcular la segunda cifra necesitamos conocer el resto de la division por 100. Tenemos que $\varphi(100)=\varphi(2^25^2)=\varphi(2^2)\varphi(5^2)=2\cdot 4\cdot 5 =40$ y claramente $40 \;| \;2000!$ por lo que si llamo $k=2000!/40$ y teniendo en cuenta que $2017$ es primo, entonces $\text{mcd}\;(100,2017)=1 \; \Rightarrow \; \text{mcd}\;(100,2017^k)=1$ y por el teorema de Euler $2017^{2000!}=2017^{40k}=\left(2017^k\right)^{\varphi(100)} \equiv 1 (\text{mod}\; 100 )$ y por tanto al ser $1$ el resto de la division por 100 se deduce que las dos últimas cifras son 01

[angel relativamente]

Re: Propuesto: Calcular las últimas cifras de un número

Dejo la solución definitiva. No obstante, quienquiera seguir intentándolo por su cuenta es libre de ignorar la solución y postear. Aunque voy a dejar la solución escueta y elegante, conviene leer la solución de cómo sacar la segunda cifra para imaginar cuál podría ser el razonamiento inductivo antes de sacarse la solución de la manga.

-SOLUCIÓN DEFINITIVA-

Ocultar contenido

Mostrar solución Ocultar solución

Vamos a probar que $2017^{2000!} \equiv 1 \; \left( \text{mod}\; 10^{500} \right)$, que será equivalente a decir que las 500 últimas cifras son $\underbrace{00\cdots 0}_{499} 1$. En primer lugar observamos que $\varphi\left(10^{500} \right)=\varphi\left(2^{500} \cdot 5^{500} \right) = \varphi\left(2^{500} \right) \varphi \left(5^{500} \right) = 1\cdot 2^{499} \cdot 4 \cdot 5^{499}=2^{501}\cdot 5^{499}$. Es claro que $2^{501} \; | \; 2000!$ (ya que en $2000!$ hay un producto de más de 1000 pares). Por otro lado en $2000!$ hay multiplicando $\left[ 2000/5 \right]=400$ múltiplos de $5$, $\left[2000/25\right]=80$ múltiplos de $5^2$, $\left[2000/125 \right] = 16$ múltiplos de $5^3$ y $\left[2000/625 \right]=3$ múltiplos de $5^4$, por lo que $2000!$ es divisible por $5^{400+80+16+3}=5^{499}$ y como $\text{mcd}\;(2,5)=1$ se tiene que $2^{501}5^{499}=\varphi\left(10^{500} \right) \; | \; 2000!$. Sea $k=2000!/\varphi\left(10^{500} \right) \in \mathbb{Z}$. Podemos escribir $2017^{2000!}=2017^{k \varphi\left(10^{500} \right) }=\left(2017^k \right) ^{\varphi\left(10^{500} \right)}$ y como 2017 es primo, $\text{mcd} \; (2017 , 10^{500} )=1 \Rightarrow \text{mcd} \; (2017^k , 10^{500} ) =1$ y por el teorema de Euler se concluye que $\left(2017^k \right) ^{\varphi\left(10^{500} \right)}=2017^{2000!} \equiv 1 \; \left( \text{mod}\; 10^{500} \right) \; \square$

[Richard R Richard]

Re: Propuesto: Calcular las últimas cifras de un número

Hola angel ,

Ocultar contenido

Mostrar solución Ocultar solución

me he perdido aquí, de movida nomás

[Error LaTeX: Compilación LaTeX fallida]

$\varphi\left(10^{500} \right)=\varphi\left(2^{500} \cdot 5^{500} \right) = \varphi\left(2^{500} \right) \varphi \left(5^{500} \right) = 1\cdot 2^{499} \cdot 4 \cdot 5^{499}=2^{501}\cdot 5^{499}$.

las últimas dos igualdades de cada cita no las comprendo, es decir los 3 primeros términos son iguales, perfecto y los dos últimos entre si perfecto, pero no entiendo(desconozco) la igualdad que une los 5, puedes brindarme algo de luz, alguna referencia a la operación matemática o propiedad.Gracias.

[angel relativamente]

Re: Propuesto: Calcular las últimas cifras de un número

Hola Richard, entiendo que lo que no conoces bien es la función $\varphi$ de Euler. Puedes buscar en la wiki que hay mucha información, pero dejo aquí lo básico: Si n es un natural, la función $\varphi(n)$ te da el número de coprimos menores o iguales que n. Por ejemplo $\varphi(10)=4$ ya que hay 4 coprimos con 10 menores o iguales que él (el 1, el 3, el 7 y el 9). Es facil ver que si p es primo entonces $\varphi(p)=p-1$, que si m,n son coprimos entonces $\varphi(mn)=\varphi(n)\varphi(m)$ y por inducción de esto puedes ver que si p es primo $\varphi(p^k)=(p-1)p^{k-1}$. Con esas propiedades deberías entender los pasos que hago, aunque aun así sería interesante ver las aplicaciones de dicha función en aritmética (el teora de Euler que comento) y en teoría de grupos.
Saludos,