Find The Last Two Digits Of $12^{1996}$

We need to find $12^{1996} \bmod 100$ . Since $\gcd (12,100) \ne 1$ , we consider the factors $4$ and $25$ factors of $100$ separately using Chinese remainder theorem as follows:

Factor 4: $12^{1996} \equiv 0 \text{ (mod 4)}$

Factor 25: Since $\gcd(12, 25) = 1$ , Euler's theorem applies; and Euler's totient function $\phi (25) = 25 \times \frac 45 = 20$ .

$\begin{aligned} 12^{1996} & \equiv 12^{1996\ \color{#3D99F6} \bmod \phi (25)} \text{ (mod 25)} \\ & \equiv 12^{1996\ \color{#3D99F6} \bmod 20} \text{ (mod 25)} \\ & \equiv 12^{16} \equiv 144^8 \equiv 44^8 \text{ (mod 25)} \\ & \equiv 2^{16}(10+1)^8 \text{ (mod 25)} \\ & \equiv 1024(64)(80+1) \text{ (mod 25)} \\ & \equiv (-1)(14)(6) \text{ (mod 25)} \\ & \equiv -9 \equiv 16 \text{ (mod 25)} \end{aligned}$

Since $16 \equiv 0 \text{ (mod 4)}$ , $\implies 2^{1998} \equiv \boxed{16} \text{ (mod 100)}$ .

We start with some simple observations: (a) $12\times 2 \equiv -1 \pmod{25}$ , so (b) $12^4 \times 2^4 \equiv 1 \pmod{25}$ , and (c) $12^{20} \equiv 1 \pmod{25}$ by Euler. Now

$12^{1996} \equiv 12^{2000} \times 16 \equiv \boxed{16} \pmod{25}$ and this congruency holds modulo 4 (and 100) as well since both sides are divisible by 4.

The most exciting approach is to view the problem as

$12^{y} \hspace{0.2cm}mod \hspace{0.2cm}(25 \times 4)$ .

We can generate a reusable formula applying chineese remainder theorem and then minify the exponention using the shortcut:

$(a.p - 1)^{n}\hspace{0.2cm} mod \hspace{0.2cm}p^{2} = (n.a.p - 1) mod \hspace{0.2cm}p^{2}$ .

The above two methods yield this final shortcut:

Let r = y mod 5.

$Let \hspace{0.2cm}b = 12^{r}\hspace{0.2cm} mod \hspace{0.2cm}5^{2} = (r.10 - 1) mod \hspace{0.2cm}5^{2}$ .

If y is divisible by 4:

$12^{y}\hspace{0.2cm}mod\hspace{0.2cm}(100) = (-24\times - b \hspace{0.2cm} mod \hspace{0.2cm}(100)))$

If y is divisible by 2:

$12^{y}\hspace{0.2cm}mod\hspace{0.2cm}(100) = (-24\times b \hspace{0.2cm} mod \hspace{0.2cm}(100)))$

In the given problem, y = 1996;

r = 1996 mod 5 = 1

b = (10.1 - 1) mod 25 = 9

Since 1996 is divisible by 4,

Solution = $(-24\times - 9 ) \hspace{0.2cm} mod \hspace{0.2cm}100$

= 16

.