Determine the last three digits of $3^{311}$.
We need to find the least positive residue $x$ such that
$$ 3^{311} \equiv x \pmod {1000} $$
Since $\gcd(3,1000)=1$, Euler's Theorem gives us $3^{\phi(1000)} \equiv 1 \pmod {1000}$. The order of 3 modulo 1000 is a factor of $\phi(1000)=400$. These factors are 1, 2, 4, 5, 8, 10, 16, 20, 25, 40, 50, 80, 100, 200, 400, and are the are the only ones we need to test.
| n | 3^n | 3^n mod 1000 |
| 1 | 3 | 3 |
| 2 | 9 | 9 |
| 4 | 81 | 81 |
| 5 | 243 | 243 |
| 8 | 6561 | 561 |
| 10 | 59049 | 49 |
| 16 | 43046721 | 721 |
| 20 | 3486784401 | 401 |
However, the above numerical calculations show that none of the factors up to and including 20 is the order. Calculations for factors larger than 20 are not feasible on a calculator.
Since we can't use the order, we use slightly less convenient reductions:
- $3^{10} \equiv 59049 \equiv 49 \pmod {1000}$
- $3^{11} \equiv 177147 \equiv 147 \pmod {1000}$
- $49^{6} \equiv 13841287201 \equiv 201 \pmod {1000}$
$$ \begin{align} 3^{311} & \equiv (3^{10})^{30} \times 3^{11} \pmod {1000} \\ \\ & \equiv (49^{6})^5 \times 147 \pmod {1000} \\ \\ & \equiv (201)^5 \times 147 \pmod {1000} \\ \\ & \equiv 48227818947147 \pmod {1000} \\ \\ & \equiv 147 \pmod {1000} \end{align} $$
So the last three digits of $3^{311}$ are 147.
Note: the author's solution assumes that we can calculate $3^{100} \equiv 1 \pmod {1000}$, but this is not possible on most calculators.