# Find $15^{100!} \bmod 5000$ using elementary number theory

If 15 was coprime to $$\varphi(5000) = 2000$$ we could use Euler's theorem, but it's not.

I solved this question by observing that for even $$r \geq 4$$ we have $$15^r \equiv 625 \bmod 5000$$, which I proved by induction, and observing that $$100!$$ is even. But this question appears early in the number theory course that I'm taking, so I feel like there must be a direct solution via that relies only only on basic number theory ideas: Fermat's Little Theorem, Euler's theorem, Chinese Remainder Theorem, etc.

I suspect we can use Chinese Remainder Theorem but I don't have a good intuition for how to use it yet.

• Your suspicion is correct - in fact we can use an operational form of CRT to reduce the computation to a single line of trivial mental arithmetic - see my answer. This is the easiest way to do problems like this. See here for over $75$ worked examples, from trivial to complex. Commented Jan 25, 2020 at 17:31
• I guess the real issue is how do you solve $(ak)^{humongous}\pmod {ck^{small}}$ where $a$ and $c$ are relatively prime to $k$ and to each other. And I'd say CRT and Eulers tells us $(ak)^{humongous}\equiv 1\pmod {c^{small}}$ (assuming $\phi(c^{small})|humongous$ which it does if $humongous=highlydivisible$) while $(ak)^{humogous}\equiv 0\pmod{k^{small}}$ has a single solution which is solvable via $1+ kc^{small} = ma^{small}$. Commented Jan 25, 2020 at 18:40

I think the method you used is the best way to go.

Still, if you want to do it via the Chinese Remainder theorem....

Note that $$5000=2^3\times 5^4$$ so solve the problem mod $$2^3$$ and mod $$5^4$$ separately. Clearly the answer is $$0\pmod {5^4}$$ so that just leaves $$2^3$$. But $$15\equiv -1\pmod {2^3}$$ so the answer is $$1\pmod {2^3}$$. Now apply the CRT to $$n\equiv 0 \pmod {625}\quad \&\quad n\equiv 1\pmod {8}$$

Since $$625\equiv 1 \pmod {8}$$ the answer is $$625$$.

• Worth emphasis: we can eliminate the CRT calculation by essentially factoring $\,5^4 = 625\,$ out of the mod computation - as explained in my answer and its link. This often (greatly) simplifies modular computations of this sort. Commented Jan 25, 2020 at 18:37
• @BillDubuque Good point, and the discussion you link to is well worth studying.
– lulu
Commented Jan 25, 2020 at 18:39

$$\, \ 1\color{#c00}5^{\!\!\overbrace{\large \color{#c00}4+2n}^{\!\LARGE {\rm e.g.}\ 100!}}\!\!\!\!\bmod \overbrace{\color{#c00}{5^{\large 4}}(8)}^{\large 5000}\, =\, \color{#c00}{5^{\large 4}}(\overbrace{(\color{#0a0}{3^{\large 2}})^{\large 2}}^{\textstyle \color{#0a0}1^{\large 2}}\!\overbrace{\color{#90f}{15}^{\large 2n}}^{\!\textstyle (\color{#90f}{{\small {\bf -}}1})^{\large 2n}\!}\!\! \bmod 8) = \color{#c00}{5^{\large 4}}\! =\, \bbox[5px,border:1px solid #c00]{625}$$
by using $$\, \color{#c00}ab\bmod \color{#c00}ac^{\phantom{|^{|^i}}}\!\!\!\:\! =\: \color{#c00}a\,(b\bmod c) =$$ $$\!\bmod\!$$ Distributive Law to factor $$\,\color{#c00}{a = 5^{\large 4}}$$ out of $$\!\bmod$$

• Note that every even integer $\,k\ge 4\,$ has form $\,4+2n,\, n\ge 0,\,$ including $\,k = 100!\,$ in the OP. Indeed $\,k\ge 4\,\Rightarrow\, k = 4+N,\ N\ge 0,\,$ and $\,k\,$ even $\,\Rightarrow\, N\,$ even, so $\,N = 2n.\ \ \$ Commented Jan 25, 2020 at 17:45
• Further, said law is in fact a convenient operational form of CRT, as explained in the linked post. Commented Jan 25, 2020 at 18:10
• Or: $\ \ \underbrace{{5^{\large 4}}\mid 15^{\large 2N}}_{\textstyle 4\le 2N}\Rightarrow\, 15^{\large 2N}\!\bmod 5^{\large 4}\cdot 8\,=\, 5^{\large 4}\underbrace{\left[\dfrac{\color{#0a0}{15}^{\large 2N}}{\color{#c00}{5^{\large 4}}}\bmod 8\right]}_{\textstyle \color{#0a0}{15}\equiv-1,\ \color{#c00}{5^{\large 2}}\!\equiv 1}\!\! =\, 5^{\large 4}$ $\ \ \$ Commented Jan 25, 2020 at 22:26

Well $$100!$$ has so many divisors it's obvious that $$\phi(5000)|100!$$[1] so for any $$a$$ where $$\gcd(a,5000)=1$$ or for any $$k|5000$$ where $$\gcd(a,k) = 1$$ that $$a^{100!} \equiv 1\pmod {5000\text{ or } k}$$.

And as $$100!$$ is ginormous, $$(dn)^{100!}\equiv 0 \pmod{n^{v}}$$ for any $$v < 100!$$[2] and $$dn$$ being any multiple of $$n$$.

So for $$5000= 2^3*5^4$$ we have $$15^{100!}\equiv 1 \pmod {2^3=8}$$ and $$15^{100!}\equiv 0 \pmod {5^4=625}$$.

By CRT we know there is only one solution and as $$625\equiv 1\pmod 8$$ we know it is $$15^{100!} \equiv 625 \pmod {5000}$$.

====

[1] $$\phi(5000) = \phi (2^3*5^4) = \phi 2^3 \phi 5^4 = 2^2*4*5^3$$. Now $$100!=\prod$$ all numbers up to $$100$$ so surely its elementary to find enough factors to cover two $$2$$s a $$4$$ and three $$5$$s. After all $$2^2*4*5^3=4*4*5*25|4*8*5*25=4*5*8*25|1*..*4*5....*8*....*25*....100=100!$$.

This almost goes without saying.

[2] And it does go without saying that $$4< 100!$$.

We can use the algorithm used here and it makes sense to make a couple of preliminary calculations:

$$\; 15^2 \equiv 15 \cdot 15 \equiv 225 \text{ mod 5000}$$
$$\; 225^2 \equiv 225 \cdot 225 \equiv 625 \text{ mod 5000}$$
$$\; 625^2 \equiv 625 \cdot 625 \equiv 625 \text{ mod 5000}$$

Now that is a stroke of luck!

$$15^{100!} \equiv 225^{\frac{100!}{2}} \equiv 625^{{\frac{100!}{4}}} \equiv 625^{{\frac{100!}{8}}} \equiv \dots \text{ mod 5000}$$

At some point the exponent $$\frac{100!}{2^k}$$ will not be even and the algorithm will begin to accrue multiplicands equal to $$625$$. But since $$625$$ is an idempotent, the final answer is $$625$$.