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

Question

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.

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