0

What is the remainder when $5,000, 000^{500 ,000 ,000 ,000}$ is divided by the prime number $10^{6}+3$?

I tried to use Fermat's Little Theorem but the exponent is still pretty high.

suklay
  • 671
  • 4
  • 8
  • 3
    Hint: $5 \times 10^{11} \equiv 2 \bmod (10^6+2)$. – Robert Israel Mar 01 '19 at 15:25
  • 2
    From $5000000=5\cdot(10^6+3)-15$ $$5000000^{500 000 000 000}\equiv 15^{500 000 000 000} \pmod{10^6+3}$$ also $$15^{10^6+2} \equiv 1 \pmod{10^6+3}$$ and $$500 000 000 000 \equiv 2 \pmod{10^6+2}$$ I can see the answer. – rtybase Mar 01 '19 at 16:03

1 Answers1

1

Yes, we can apply little Fermat. But don't be afraid of the large numbers. They have been designed so that they simplify nicely and provide illuminating exercise on modular arithmetic. Indeed, notice

$$\begin{align} &\bmod 10^{\large 6}\!+3\!:\,\ 10^{\large 6}\equiv -3\ \ \overset{\large \times 5}\Longrightarrow\ \ \color{#c00}{5(10^{\large 6})}\equiv5(-3)\equiv \color{#c00}{-15}\\ &\bmod 10^{\large 6}\!+2\!:\,\ 10^{\large 6}\equiv -2\overset{\large \times 5(10)^{\Large 5}}\Longrightarrow\!\! \color{#0a0}{5(10^{11}})\equiv\, -10^{\large 6}\equiv\,\color{#0a0}2\\[.6em] {\rm thus}\ \ &\bmod 10^{\large 6}\!+3\!:\ \ \color{#c00}{5(10^{\large 6}})^{\large\color{#0a0}{ 5(10^{11})}}\equiv (\color{#c00}{-15})^{\large\color{#0a0}2}\ \ \ \rm by\ little\ Fermat \end{align}$$

Remark $ $ Most likely the point of the exercise is to lead you to discover how to efficiently perform modular computations such as those in the first two equations above, since if one sought merely to give an exercise on little Fermat then that could be done more effectively via much smaller numbers.

Bill Dubuque
  • 272,048