Encontrar los últimos tres cero dígitos de $1^1 \cdot 2^2 \cdot 3^3 \cdot ... \cdot 25^{25}$

Question

$1^1 \cdot 2^2 \cdot 3^3 \cdot ... \cdot 25^{25}$

Yo había estado sentado con este problema todo el día ahora, lo que había probado hasta ahora:

Dividiendo el producto por $10^{100}$ (ya que hay que $5^{100}$ (tomando cinco años a partir de factores)). Y jugando con el teorema del resto Chino.

$1^1 \cdot 2^2 \cdot 3^3 \dots 25^{25} \equiv 0 \pmod{8}$

Pero yo no veo ninguna manera, aparte de la fuerza bruta el módulo de $125$.

Yo también lo había notado que el producto puede ser reescrita como: $$ \frac{25!}{0!}\cdot \frac{25!}{1!} \cdot \frac{25!}{2!} \cdot \frac{25!}{3!} \cdot \cdot \cdot \frac{25!}{24!}$$ Pero me parece que no puede obtener ninguna información útil a partir de eso.

Answer 1

Aquí es muy crudo enfoque que se puede hacer a mano y con paciencia, pero no es bastante:

La valoración de $n=1^1\cdot2^2\cdot\ldots\cdot25^{25}$ en cada uno de los prime es $$v_p(n)=v_p\left(\prod_{k=1}^{25}k^k\right)=\sum_{k=1}^{25}v_p(k^k)=\sum_{k=1}^{25}v_p(k)\cdot k,$$ que es fácil de calcular, para el mayor de los números primos, y es un poco más de trabajo para los más pequeños: \begin{eqnarray*} v_{23}(n)&=&1\cdot23=23,\\ v_{19}(n)&=&1\cdot19=19,\\ v_{17}(n)&=&1\cdot17=17,\\ v_{13}(n)&=&1\cdot13=13,\\ v_{11}(n)&=&1\cdot11+1\cdot22=33,\\ v_7(n)&=&1\cdot7+1\cdot14+1\cdot21=42,\\ v_5(n)&=&1\cdot5+1\cdot10+1\cdot15+1\cdot20+2\cdot25=100,\\ v_3(n)&=&1\cdot3+1\cdot6+2\cdot9+1\cdot12+1\cdot15+2\cdot18+1\cdot21+1\cdot24=135\\ v_2(n)&=&1\cdot2+2\cdot4+1\cdot6+3\cdot8+1\cdot10+2\cdot12+1\cdot14+4\cdot16\\ &\ &+1\cdot18+2\cdot20+1\cdot22+3\cdot24=304. \end{eqnarray*} Esto demuestra que $10^{100}$ divide $n$, pero $10^{101}$ no. Así queremos encontrar $0\leq k<1000$ tal que $$10^{-100}n\equiv k\pmod{1000}.$$ Basta para resolver la congruencia modulo $8$ $125$ como podemos entonces aplicar el teorema del resto Chino. De $v_2(n)=304$ es claro que $10^{-100}n\equiv0\pmod{8}$. Modulo $125$ tenemos que hacer algo más de trabajo. Vamos a suponer que $2$ es una raíz primitiva módulo $125$. Las identidades $$2^7\equiv128\equiv3\pmod{125}\qquad\text{ and }\qquad 12^2\equiv144\equiv19\pmod{125},$$ ya muestran que $3\equiv 2^7$ $19\equiv 2^4\times3^2\equiv2^{18}$ modulo $125$. Del mismo modo las identidades $$9\cdot 19\equiv171\equiv46\equiv2\cdot23$$ $$6\cdot23\equiv138\equiv13$$ $$13^2\equiv169\equiv44\equiv4\cdot11$$ $$8\cdot17\equiv136\equiv11$$ $$11\cdot12\equiv132\equiv7,$$ mostrar que $$23\equiv2^{31}\qquad13\equiv2^{39}\qquad11\equiv2^{76}\qquad17\equiv2^{73}\qquad7\equiv2^{85},$$ donde todas las congruencias son modulo $125$. Ahora podemos reescribir el producto $10^{-100}n$ en términos de potencias de $2$, y simplificar mediante el teorema de Euler con $\varphi(125)=100$ para obtener \begin{eqnarray*} 10^{-100}n &\equiv&2^{304-100}3^{135}5^{100-100}7^{42}11^{33}13^{13}17^{17}19^{19}23^{23}\\ &\equiv&2^{204}2^{7\cdot135}2^02^{85\cdot42}2^{76\cdot33}2^{39\cdot13}2^{73\cdot17}2^{18\cdot19}2^{31\cdot23}\\ &\equiv&2^42^{45}2^{70}2^82^72^{41}2^{42}2^{13}\equiv2^{4+45+70+8+7+41+42+13}\\ &\equiv&2^{230}\equiv2^{30}\equiv2^{-1}\cdot23\equiv2^{-1}(23+125)\equiv74, \end{eqnarray*} donde de nuevo todas las congruencias son modulo $125$. Entonces por el teorema del resto Chino tenemos $$10^{-100}n\equiv824\pmod{1000}.$$

Answer 2

Así que mirando lo que queda después de los factores de $5$ y un mismo número de $2$s se borran (aquí de $10, 20$ y los poderes de la $2$): $$ R = 2^{48}\cdot3^{3+15}\cdot6^{6}\cdot7^{7}\cdot9^{9} \cdot11^{11}\cdot12^{12}\cdot13^{13}\cdot14^{14} \cdot17^{17}\cdot18^{18}\cdot19^{19} \cdot21^{21}\cdot22^{22} \cdot23^{23} \cdot24^{24} $$

y la reducción de los números primos $$ R = 2^{204}\cdot3^{135}\cdot7^{42} \cdot11^{33}\cdot13^{13}\cdot17^{17}\cdot19^{19}\cdot23^{23}$$

Para la búsqueda de $R \bmod 1000$, podemos echar fuera a $100$'s como la multiplicación el orden de cada primer mod 1000 debe dividir $100$, y desde $7\times 11\times 13 = 1001$, vamos a limpiar esos también.

$$(R\bmod 1000) \equiv 2^{4}\cdot3^{35}\cdot7^{29} \cdot11^{20}\cdot17^{17}\cdot19^{19}\cdot23^{23} $$

Así que, básicamente, todavía hay un montón de recta exponenciación modular de hacer. De cada uno de los factores mencionados:

$$(R\bmod 1000) \equiv 16\cdot 707\cdot 607\cdot 201\cdot 177\cdot 979\cdot 567 = 824$$

Un montón de espacio para el error en ese proceso, a pesar de, y no bastante de acceso directo.

Answer 3

Tomando los factores primos de a $1,2,3,….,25$ y teniendo en cuenta los números de $n^n$ obtenemos los exponentes correspondientes a $2,3,5,7,11,13,17,19,23$. Tenemos $$N=2^{304}\cdot3^{135}\cdot5^{100}\cdot7^{42}\cdot11^{33}\cdot13^{13}\cdot17 ^{17}\cdot19^{19}\cdot23^{23}$$ $$N= 10^{100}(2^{204}\cdot3^{135}\cdot7^{42}\cdot11^{33}\cdot13^{13}\cdot17 ^{17}\cdot19^{19}\cdot23^{23})$$ Por lo tanto tenemos que calcular el$X$ en el sistema modular de la ecuación $$2^{204}\cdot3^{135}\cdot7^{42}\cdot11^{33}\cdot13^{13}\cdot17 ^{17}\cdot19^{19}\cdot23^{23} \equiv X\pmod{1000}$$ Por separado uno tiene, modulo $1000$ $$2^{204}=2^{50\cdot4+4}\equiv 624^4\cdot2^4\equiv016\\3^{135}=3^{27\cdot5}\equiv 987^5\equiv 707\\7^{42}=7^{21\cdot2}\equiv(007)\equiv 049\\11^{10\cdot3+3}\equiv (601\cdot11)^3\equiv131\\13^{13}\equiv253\\17^{17}\equiv177\\19^{19}\equiv 979\\23^{23}\equiv567$$ It remains to find modulo $1000$ el producto $$16\cdot707\cdot49\cdot131\cdot253\cdot177\cdot979\cdot567$$ Hay varias maneras de calcular este. El resultado es $$\color{red}{824}$$ NOTA.- Yo no descartar cualquier posible error en los cálculos.