Find last three nonzero digits of $1^1 \cdot 2^2 \cdot 3^3 \cdot ... \cdot 25^{25}$

Question

Find the last three nonzero digits of $1^1 \cdot 2^2 \cdot 3^3 \cdot ... \cdot 25^{25}$.

I had been sitting with this problem whole day now, what I had tried so far:

Dividing the product by $10^{100}$ (since there are $5^{100}$ (taking fives from factors as well)). And playing with Chinese remainder theorem.

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

But I don't see any way apart from brute forcing the modulus $125$.

I had also noticed that the product can be rewritten as: $$ \frac{25!}{0!}\cdot \frac{25!}{1!} \cdot \frac{25!}{2!} \cdot \frac{25!}{3!} \cdot \cdot \cdot \frac{25!}{24!}$$ But I can't seem to get any useful information from that.

Answer 1

Here is a very crude approach that is doable by hand and with patience, but it isn't pretty:

The valuation of $n=1^1\cdot2^2\cdot\ldots\cdot25^{25}$ at each prime is $$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,$$ which is easily computed for larger primes, and is a bit more work for the smaller ones: \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*} This shows that $10^{100}$ divides $n$, but $10^{101}$ does not. So we want to find $0\leq k<1000$ such that $$10^{-100}n\equiv k\pmod{1000}.$$ It suffices to solve the congruence modulo $8$ and $125$ as we can then apply the Chinese remainder theorem. From $v_2(n)=304$ it is clear that $10^{-100}n\equiv0\pmod{8}$. Modulo $125$ we need to do some more work. Let's guess that $2$ is a primitive root modulo $125$. The identities $$2^7\equiv128\equiv3\pmod{125}\qquad\text{ and }\qquad 12^2\equiv144\equiv19\pmod{125},$$ already show that $3\equiv 2^7$ and $19\equiv 2^4\times3^2\equiv2^{18}$ modulo $125$. Similarly the identities $$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,$$ show that $$23\equiv2^{31}\qquad13\equiv2^{39}\qquad11\equiv2^{76}\qquad17\equiv2^{73}\qquad7\equiv2^{85},$$ where all congruences are modulo $125$. Now we can rewrite the product $10^{-100}n$ in terms of powers of $2$, and simplify using Euler's theorem with $\varphi(125)=100$ to get \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*} where again all congruences are modulo $125$. Then by the Chinese remainder theorem we have $$10^{-100}n\equiv824\pmod{1000}.$$

Answer 2

So looking at what's left after the factors of $5$ and a matching number of $2$s are cleared (here from $10, 20$ and the powers of $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} $$

and reducing to primes $$ R = 2^{204}\cdot3^{135}\cdot7^{42} \cdot11^{33}\cdot13^{13}\cdot17^{17}\cdot19^{19}\cdot23^{23}$$

For finding $R \bmod 1000$, we can cast out $100$'s since the multiplicative order of each prime mod 1000 must divide $100$, and since $7\times 11\times 13 = 1001$, we'll clean those up too.

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

So basically there is still a lot of straight modular exponentiation to do. From each of the above factors:

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

Plenty of room for error in that process, though, and no pretty shortcut.

Answer 3

Taking the prime factors of $1,2,3,….,25$ and considering the numbers $n^n$ we get the exponents corresponding to $2,3,5,7,11,13,17,19,23$. We get $$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})$$ Hence we have to calculate$X$ in the modular equation $$2^{204}\cdot3^{135}\cdot7^{42}\cdot11^{33}\cdot13^{13}\cdot17 ^{17}\cdot19^{19}\cdot23^{23} \equiv X\pmod{1000}$$ Separately one has, 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$ the product $$16\cdot707\cdot49\cdot131\cdot253\cdot177\cdot979\cdot567$$ There are several ways to calculate this. The result is $$\color{red}{824}$$ NOTE.- I do not rule out any possible error in the calculations.

Answer 4

We can use a $\sharp$ algorithm that 'digests'

$\quad \displaystyle \prod_{k=1}^{25}k^k$

from right to left.

$\; 25^{25} \cdot 1 \, \sharp \, 24^{24} \cdot 25^{25} \cdot 1 \, \sharp \, (24\cdot 25)^{24} \cdot (25 \cdot 1) \, \sharp$
$\; 6^{24} \cdot 25 \, \sharp \, 23^{23} \cdot 6^{24} \cdot 25 \, \sharp \, (23\cdot 6)^{23} \cdot (6 \cdot 25) \, \sharp$
$\; 138^{23} \cdot 15 \, \sharp \, 22^{22} \cdot 138^{23} \cdot 15 \, \sharp \, (22\cdot 138)^{22} \cdot (138 \cdot 15) \, \sharp$
$\; 36^{22} \cdot 207 \, \sharp \, 21^{21} \cdot 36^{22} \cdot 207 \, \sharp \, (21\cdot 36)^{21} \cdot (36 \cdot 207) \, \sharp$
$\; 756^{21} \cdot 452 \, \sharp \, 20^{20} \cdot 756^{21} \cdot 452 \, \sharp \, (20\cdot 756)^{20} \cdot (756 \cdot 452) \, \sharp$
$\; 512^{20} \cdot 712 \, \sharp \, 19^{19} \cdot 512^{20} \cdot 712 \, \sharp \, (19\cdot 512)^{19} \cdot (512 \cdot 712) \, \sharp$

To speed it up we'll skip the middle step.

$\; 728^{19} \cdot 544 \, \sharp \, (18\cdot 728)^{18} \cdot (728 \cdot 544) \, \sharp$
$\; 104^{18} \cdot 32 \, \sharp \, (17\cdot 104)^{17} \cdot (104 \cdot 32) \, \sharp$
$\; 768^{17} \cdot 328 \, \sharp \, (16\cdot 768)^{16} \cdot (768 \cdot 328) \, \sharp$
$\; 288^{16} \cdot 904 \, \sharp \, (15\cdot 288)^{15} \cdot (288 \cdot 904) \, \sharp$
$\; 432^{15} \cdot 352 \, \sharp \, (14\cdot 432)^{14} \cdot (432 \cdot 352) \, \sharp$
$\; 48^{14} \cdot 64 \, \sharp \, (13\cdot 48)^{13} \cdot (48 \cdot 64) \, \sharp$
$\; 624^{13} \cdot 72 \, \sharp \, (12\cdot 624)^{12} \cdot (624 \cdot 72) \, \sharp$
$\; 488^{12} \cdot 928 \, \sharp \, (11\cdot 488)^{11} \cdot (488 \cdot 928) \, \sharp$
$\; 368^{11} \cdot 864 \, \sharp \, (10\cdot 368)^{10} \cdot (368 \cdot 864) \, \sharp$
$\; 368^{10} \cdot 952 \, \sharp \, (9\cdot 368)^{9} \cdot (368 \cdot 952) \, \sharp$
$\; 312^{9} \cdot 336 \, \sharp \, (8\cdot 312)^{8} \cdot (312 \cdot 336) \, \sharp$
$\; 496^{8} \cdot 832 \, \sharp \, (7\cdot 496)^{7} \cdot (496 \cdot 832) \, \sharp$
$\; 472^{7} \cdot 672 \, \sharp \, (6\cdot 472)^{6} \cdot (472 \cdot 672) \, \sharp$
$\; 832^{6} \cdot 184 \, \sharp \, (5\cdot 832)^{5} \cdot (832 \cdot 184) \, \sharp$
$\;416^{5} \cdot 88 \, \sharp \, (4\cdot 416)^{4} \cdot (416 \cdot 88) \, \sharp$
$\;664^{4} \cdot 608 \, \sharp \, (3\cdot 664)^{3} \cdot (664 \cdot 608) \, \sharp$
$\;992^{3} \cdot 712 \, \sharp \, (2\cdot 992)^{2} \cdot (992 \cdot 712) \, \sharp$
$\;984^{2} \cdot 304 \, \sharp \, (1\cdot 984)^{1} \cdot (984 \cdot 304) \, \sharp$
$\;984^{1} \cdot 136$ $\quad \sharp \text{ has finished executing.}$

Final calculation,

$\quad 984 \cdot 136 \equiv 824 \pmod{1000}$