# Find the last $2$ digits of $2016^{123}$

Find the last $2$ digits of $2016^{123}$

So you have that $2016^{123} \equiv \pmod{100}$

then $16^{123}\equiv \pmod{100}$

Now the $gcd(16,100)=4$ so I divide everything by 4 $4^{123} \equiv \pmod{25}$

I know $4^{\varphi(25)} \equiv 1 \pmod{25}$ then $(4^{20})^6*4^{3} \equiv 14 \pmod{25}$

Then multiplying that by $4$ to get it in the original mod I get $56$ but the answer is $96$ so I"m not sure where I"m making a mistake or if this is the right process to use.

• so I divide everything by 4 That's not what you did on the LHS.
– dxiv
Apr 3, 2017 at 3:52
• I'll give an image of your mistake: if you divide $(2a)^{100}$ by 2 you get $a^{100}$. This is obviously WRONG !
– QFi
Apr 3, 2017 at 4:00
• oh wow thanks I got it I reduced it again and the right hand side was $4^{245}$ Apr 3, 2017 at 4:11
• We can also use the Mod Distributive Law to pull out the factor in common with the modulus, e.g. see this answer. Apr 3, 2017 at 16:18

There are two ways of simplifying the congruence to get the desired result:

$$(2^5\cdot3^2\cdot7)^{123} \equiv (4^2)^{123}\pmod{4\cdot25}$$

Factor $4$ out:

$$2^{613}\cdot3^{246}\cdot7^{123} \equiv 4^{245} \equiv 4^5 \equiv 24 \pmod{25}$$

Now $4\cdot24 = 96$, the desired result.

The $5$ of the last exponent is since $245 \equiv 5 \pmod {\varphi(25)}$

The following for me is the standard approach. Simplifying both congruence class and exponent:

$$\begin{cases} 2016 \equiv 16 \pmod{100} \\ 123 \equiv 3 \pmod{\varphi(100)} \\ 16^3 \equiv 96 \pmod{100} \end{cases}$$