Numbers are best

Note that $109^{2017} \; \equiv 9^{2017} + \binom{2017}{1}\times 100 \times 9^{2016} \; \equiv \; 9^{2017} + 1700 \times 9^{2016} \pmod{10000}$ Note that $9 \equiv 1 \pmod{4}$ and $9^2 \equiv 1 \pmod{5}$ , so that $9^{10} \equiv 1 \pmod{25}$ , and hence $9^{10} \equiv 1 \pmod{100}$ . Thus $109^{2017} \equiv 9^{2017} + 1700 \times 9^6 \pmod{10000}$ Now $9^2 \equiv 1 \pmod{16}$ , and $9^{50} \equiv 1 \pmod{125}$ and $9^{250} \equiv 1 \pmod{625}$ , and hence $9^{250} \equiv 1 \pmod{10000}$ . Thus we deduce that $109^{2017} \equiv 9^{17} + 1700 \times 9^6 \pmod{10000}$ and this last is small enough to evaluate by hand. We obtain that $109^{2017} \equiv \boxed{6269} \pmod{10000}$