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

Question

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.

Answer 1

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$.

Answer 2

$\, \ 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$

Answer 3

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!$.

Answer 4

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$.