A question by mohit

Note that $107^{2017} \; \equiv \; 7^{2017} + 2017 \times 100 \times 7^{2016} \; \equiv \; 7^{2017} + 1700 \times 7^{2016} \pmod{10000}$ Now $7^2 \equiv 1 \pmod{4}$ and $7^2 \equiv -1 \pmod{5}$ , so that $7^4 \equiv 1 \pmod{5}$ and $7^{20} \equiv 1 \pmod{25}$ . Thus $7^{20} \equiv 1 \pmod{100}$ , and hence $107^{2017} \equiv 7^{2017} + 1700 \times 7^{16} \pmod{10000}$ Moreover $7^2 \equiv 1 \pmod{16}$ and $7^{100} \equiv 1 \pmod{125}$ and $7^{500} \equiv 1 \pmod{625}$ , so that $7^{500} \equiv 1 \pmod{10000}$ , and hence $107^{2017} \equiv 7^{17} + 1700 \times 7^6 \pmod{10000}$ This last expression can be calculated by hand, and so $107^{2017} \equiv \boxed{8907} \pmod{10000}$ .

Let $N=107^{2017}$ . We need to find $N \bmod 10000$ . Since $\gcd (107, 10000) = 1$ , we can apply the Euler's theorem and Carmichael's lambda function $\lambda(\cdot)$ as follows:

$\begin{aligned} N & \equiv 107^{2017 \bmod \color{#3D99F6} \lambda (10000)} \text{ (mod 10000)} \quad \quad \small \color{#3D99F6} \text{Since }\lambda(10000) = 500 \\ & \equiv 107^{2017 \bmod \color{#3D99F6} 500} \text{ (mod 10000)} \\ & \equiv 107^{17} \text{ (mod 10000)} \\ & \equiv (100+7)^{17} \text{ (mod 10000)} \\ & \equiv \left(100^{17} + \cdots + \frac {17\times 16}2 \times 100^2 \times 7^{15} + 17 \times 100 \times 7^{16} + 7^{17} \right) \text{ (mod 10000)} \\ & \equiv 1707\times 7^{16} \text{ (mod 10000)} \\ & \equiv 1707(50-1)^8 \text{ (mod 10000)} \\ & \equiv 1707 \left(50^8 - \cdots +70000-400+1\right) \text{ (mod 10000)} \\ & \equiv 1707 (-399) \text{ (mod 10000)} \\ & \equiv -1093 \text{ (mod 10000)} \\ & \equiv \boxed{8907} \text{ (mod 10000)} \end{aligned}$