Math in Christmas: Number Theory Fun

Since $2016 = 2^53^27$ , and $\gcd (12,2) \ne 1$ and $\gcd(12,3) \ne 1$ , let us consider the three prime factors separately.

$\begin{aligned} 12^{25^{2016}} & \equiv (2^23)^{25^{2016}} \equiv 0 \text{ (mod }2^5) \\ 12^{25^{2016}} & \equiv (2^23)^{25^{2016}} \equiv 0 \text{ (mod }3^2) \\ 12^{25^{2016}} & \equiv 12^{25^{2016} \text{ mod }{\color{#3D99F6}\phi(7)}} \text{ (mod 7)} & \small \color{#3D99F6} \text{Since }\gcd(12,7) = 1 \text{, Euler's theorem applies.} \\ & \equiv 12^{25^{2016} \text{ mod }{\color{#3D99F6}6}} \text{ (mod 7)} & \small \color{#3D99F6} \text{Euler's totient function }\phi(7) = 6 \\ & \equiv 12^{25^{2016 \text{ mod }{\color{#3D99F6}\phi(6)}} \text{ mod }6} \text{ (mod 7)} & \small \color{#3D99F6} \text{Since }\gcd(25,6) = 1 \text{, Euler's theorem applies.} \\ & \equiv 12^{25^{2016 \text{ mod }{\color{#3D99F6}2}} \text{ mod }6} \text{ (mod 7)} & \small \color{#3D99F6} \text{Euler's totient function }\phi(6) = 2 \\ & \equiv 12^{25^0 \text{ mod }6} \text{ (mod 7)} \\ & \equiv 12^1 \equiv 5 \text{ (mod 7)} \end{aligned}$

Since $12^{25^{2016}} \equiv \begin{cases} 0 \text{ (mod }2^5) \\ 0 \text{ (mod }3^2) \end{cases} \implies 2^53^2n \equiv 288n \text{ (mod 2016)}$ , where $n$ is an integer.

Now, we have:

$\begin{aligned} 12^{25^{2016}} & \equiv 5 \text{ (mod 7)} \\ 288n & \equiv 5 \text{ (mod 7)} & \small \color{#3D99F6} \text{Note that } 288 \equiv 1 \text{ (mod 7)} \\ n & \equiv 5 \text{ (mod 7)} \\ \implies n & = 5 \\ \implies 12^{25^{2016}} & \equiv 288n \text{ (mod 2016)} \\ & \equiv \boxed{1440} \text{ (mod 2016)} \end{aligned}$

The given expression may be very intimidating when it comes to terms not relatively prime, but if you observe their prime factorizations carefully, this problem becomes the nice breeze. :)

Let $a$ denote the given value to be evaluated. Notice that $2016 = 2^5 \times 3^2 \times 7$ and $12 = 2^2 \times 3$ . Since $\gcd(a,2016) \neq 1$ , the first step is to evaluate $\bmod 2^5$ , $\bmod 3^2$ and $\bmod 7$ separately. Then, apply Chinese Remainder Theorem to determine the answer.

Evaluating Separately

Since $a$ contains $2^{5} = 32$ and $3^{2} = 9$ as its divisors, $\begin{array}{rl} a &\equiv 0 \bmod \left(2^{5} \cdot 3^{2}\right) \end{array}$

Note: You can also split into two factors for $\left(2^{5} \cdot 3^{2}\right)$ . However, that wouldn't be necessary since it suffices that $a \equiv 0$ for both of these factors.

Since $\gcd(a,7) = 1$ , we can use Euler's Theorem to evaluate $a \bmod 7$ , which shows that if $b^6 \equiv 1 \bmod 7$ where $(b,7) = 1$ , for exponents $25^{2016} \equiv \left(6 \cdot 4 + 1\right)^{2016} \equiv 1 \bmod 6$ so $a \equiv 12 \equiv 5 \bmod 7$

Final Results

Since we already know that for $\bmod 2^5$ and $\bmod 3^2$ , $a \equiv 0$ , apply Chinese Remainder Theorem to obtain $a \equiv 0 \bmod \left(2^5 \cdot 3^2\right)$ . Evaluating the following $\begin{array}{rl} a &\equiv 0 \bmod \left(2^5 \cdot 3^2\right)\\ a &\equiv 5 \bmod 7 \end{array}$ gives $a = \boxed{1440}$ . You can simply verify this by Euclidean algorithm to see that $a$ works for both congruences.