The last four digits, part 2

First, we show that $123^{1000}\equiv 1 \pmod {10000}$ . To see this, we note that $\phi(2500)=\phi(2^2 5^4)=(2^2-2)(5^4-5^3)=1000$ and hence $123^{1000}\equiv 1 \pmod {2500}$ . Moreover, $123^{1000}\equiv 1 \pmod {16}$ . Since $lcm (16,2500)=10000$ , then $123^{1000}\equiv 1 \pmod {10000}$ .

Now let $123^{999}\equiv \overline{abcd} \pmod {10000}$ . Then $123\overline{abcd} \equiv 1 \pmod {10000}$ . This means that $d=7$ . Since $123\times 7=861$ , then $123c \equiv 4 \pmod {10}$ and so $c=8$ , we carry on the same procedure till we obtain $\overline{abcd} =9187$ .

Remark : using the similar technique, we can show that any 3-digit odd number, says A, not ends in 5, will fulfil $A^{1000}\equiv 1 \pmod {10000}$ .