# 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. 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}$. 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. Jan 25, 2020 at 18:37
• @BillDubuque Good point, and the discussion you link to is well worth studying.
– lulu
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.\ \ \$ Jan 25, 2020 at 17:45
• Further, said law is in fact a convenient operational form of CRT, as explained in the linked post. 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}$ $\ \ \$ 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!$$.

Since the OP did not show their work using their method, I was interested and came up with the following; I marked it community wiki.

We have

$$\quad 5000 = 2^3 \times 5^4$$

and

$$\quad 15 = 3 \times 5$$

We need to 'get something going' with $$15$$ and find some even factors.

But

$$\tag 1 15^4 - 15^2 = (15^2 + 15)(15^2-15) = 240 \times 210$$

We are happy to see that $$2^3$$ and $$5^2$$ both divide the number in $$\text{(1)}$$. OK, jacking up the exponent for $$5$$ we get the number

$$\tag 2 15^2(15^4 - 15^2)$$

specifically constructed so that it is divisible by $$5000$$.

So we have

$$\tag 3 15^6 \equiv 15^4 \pmod{5000}$$

It is easy to see that if $$n \ge 6$$ is even then $$15^n \equiv 15^4 \pmod{5000}$$.

Since $$100!$$ is even and greater than $$6$$ we have

$$\tag 4 15^{100!} \equiv 15^4 \equiv 625 \pmod{5000}$$