find the last 4 dgits of $2^{2016}$

Question

I am trying to find the last 4 digits of $2^{2016}$.

Here is where I am up to:

2^2016 = x mod 10000

2^2016 = x mod 625 - I used Eulers function to find that 2^16 = 1 mod 625 = 536

2^2016 = x mod 16

Now I am stuck. The second equation can not use Euler so how do I continue?

Thanks

Answer 1

$2^{2016} = 16 \times 2^{2012} \equiv 0 \mod{16}$.