3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Jan 25, 2020 at 17:31
  • $\begingroup$ 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}$. $\endgroup$
    – fleablood
    Jan 25, 2020 at 18:40

4 Answers 4

6
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Jan 25, 2020 at 18:37
  • $\begingroup$ @BillDubuque Good point, and the discussion you link to is well worth studying. $\endgroup$
    – lulu
    Jan 25, 2020 at 18:39
1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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.\ \ \ $ $\endgroup$ Jan 25, 2020 at 17:45
  • $\begingroup$ Further, said law is in fact a convenient operational form of CRT, as explained in the linked post. $\endgroup$ Jan 25, 2020 at 18:10
  • $\begingroup$ 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}$ $\ \ \ $ $\endgroup$ Jan 25, 2020 at 22:26
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.