A two-year-old problem

Here's an alternative solution that doesn't use the Chinese Remainder Theorem. To be clear, CRT is a solid approach for these problems in general, but in this specific case there are some shortcuts.

Let $A_n=\underbrace{5\cdots 5}_{n \, 5s}7$ . We want to find $2016^{A_{21}} \pmod{100}$ .

We can simplify immediately by noting $2016 \equiv 16 \pmod{100}$ , so we need $16^{A_{21}} \pmod{100}$ .

Now, this is where CRT would normally be used. But it's worth trying to see what happens to the last two digits of different powers of $16$ . We have $16^2=256$ , so the next last digit pair is $56$ ; continuing, we have $16 \to 56 \to 96 \to 36 \to 76 \to 16$ , and the cycle repeats with period $5$ .

Since $A_n \equiv 2 \pmod{5}$ for all $n$ , we in fact have $16^{A_n} \equiv 16^2 \equiv \boxed{56} \pmod{100}$ for all $n$ .

Just a footnote on this approach: it may seem wildly optimistic to try looking for this cycle. But there are at most $100$ distinct pairs of last digits, so they must repeat at some point. And better than this, we know that all positive integer powers of $16$ end with a $6$ , so the cycle can have length at most $10$ .

Power cycle of $2016$

To determine the last two digits of the expression, we observe its power cycle and observe its cyclicity. Since only the last two digits of $2016$ determine the expressions last two digits, we can find the power cycle of $16$ only

$\begin{aligned} 16^{1} = 16 &\rightarrow \color{#3D99F6}{\boxed{16}} \\ 16^{2} = 256 &\rightarrow \color{#3D99F6}{\boxed{56}} \\ 16^{3} = 4096 &\rightarrow \color{#3D99F6}{\boxed{96}} \\ 16^{4} = 65536 &\rightarrow \color{#3D99F6}{\boxed{36}} \\ 16^{5} = 1048576 &\rightarrow \color{#3D99F6}{\boxed{76}} \\ 16^{6} = 16777216 &\rightarrow \color{#D61F06}{\boxed{16}} \end{aligned}$

$\begin{array}{lcr} \\ \begin{aligned} 2016^{\textcolor{#D61F06}{1}} & \rightarrow \color{#3D99F6}{\boxed{16}} \\ 2016^{\textcolor{#D61F06}{2}} & \rightarrow \color{#3D99F6}{\boxed{56}} \\ 2016^{\textcolor{#D61F06}{3}} & \rightarrow \color{#3D99F6}{\boxed{96}} \\ 2016^{\textcolor{#D61F06}{4}} & \rightarrow \color{#3D99F6}{\boxed{36}} \\ 2016^{\textcolor{#D61F06}{5}} & \rightarrow \color{#3D99F6}{\boxed{76}} \end{aligned} & \begin{aligned} 2016^{\textcolor{#D61F06}{6}} & \rightarrow \color{#3D99F6}{\boxed{16}} \\ 2016^{\textcolor{#D61F06}{7}} & \rightarrow \color{#3D99F6}{\boxed{56}} \\ 2016^{\textcolor{#D61F06}{8}} & \rightarrow \color{#3D99F6}{\boxed{96}} \\ 2016^{\textcolor{#D61F06}{9}} & \rightarrow \color{#3D99F6}{\boxed{36}} \\ 2016^{\textcolor{#D61F06}{10}} & \rightarrow \color{#3D99F6}{\boxed{76}} \end{aligned} & \ldots \end{array}$

Evaluating Expression

$5555555555555555555557 \equiv 2 \mod(5)$ $\therefore \textcolor{#3D99F6}{\text{Last two digits }}2016^{5555555555555555555557} \rightarrow 2016^{2} \rightarrow \color{#3D99F6}{\boxed{56}}$

​

Let $N$ be the given number. We need to find $N \bmod 100$ . Since $\gcd(N,100) \ne 1$ , we can use Chinese remainder theorem on the factors $4$ and $25$ of $100$ as follows.

Factor 4: $\color{#D61F06} N \equiv 0 \text{ (mod 4)}$

Factor 25:

$\begin{aligned} 2016^{\underbrace{555\cdots5}_{\text{\# of 5 = 21}}7} & \equiv 16^{\underbrace{555\cdots5}_{\text{\# of 5 = 21}}7} \text{(mod 25)} \\ & \equiv 2^{4 \times \underbrace{555\cdots5}_{\text{\# of 5 = 21}}7} \text{(mod 25)} & \small \color{#3D99F6} \text{Since }\gcd(2, 25) = 1 \text{, Euler's theorem applies.} \\ & \equiv 2^{4 \times \underbrace{555\cdots5}_{\text{\# of 5 = 21}}7 \bmod \color{#3D99F6} \phi(25)} \text{(mod 25)} & \small \color{#3D99F6} \text{Euler's totient function }\phi(25) = 25 \times \frac 45 = 20 \\ & \equiv 2^{4 \times \underbrace{555\cdots5}_{\text{\# of 5 = 21}}7 \bmod \color{#3D99F6} 20} \text{ (mod 25)} \\ & \equiv 2^{4 \times 57 \bmod \color{#3D99F6} 20} \text{ (mod 25)} \\ & \equiv 2^8 \equiv 256 \equiv 6 \text{ (mod 25)} \\ \implies N & \equiv 25 n + 6 & \small \color{#3D99F6} \text{where }n \text{ is an integer.} \\ \implies \color{#D61F06} 25n + 6 & \equiv \color{#D61F06} 0 \text{ (mod 4)} \\ n + 2 & \equiv 0 \text{ (mod 4)} \\ \implies n & = 2 \\ \implies N & \equiv 25n + 6 \equiv \boxed{56} \text{ (mod 100)} \end{aligned}$

---

References:

• Euler's theorem
• Euler's totient function

$(2016)^{5555555555555555555557}$ = $((2016)^{10})$ $^{555555555555555555555}$ $\times$ $(2016)^7$

2016 end in 6, we can find the last two digits with the help of the following points :

• $2016^{10}$ $\Rightarrow$ end in 76
• (Number end in 76) $^{any-number}$ $\Rightarrow$ end in 76
• $(2016)^7$ $\Rightarrow$ end in 56

Finally, using basic multiplication technique, the last two digits of the product of the numbers ending in 76 and 56 are : 56

I used a calculator and found that:

$2016^7 \equiv 56 \pmod{100}$

$2016^{57} \equiv 56 \pmod{100}$

$2016^{557} \equiv 56 \pmod{100}$

I didn't check anymore; I just assumed it kept repeating, so I typed in $56$ and that gave me a ✓.

Finding its last two digits is equivalent to finding the last two digits of $16^{5555555555555555555557}$ We first express $16$ as $2^{4}$

Note that if we multiply $555555.....7$ (where $5$ is repeated $n$ times) by $4$ , we get $222...8$ ( $2$ is repeated $n+1$ times)

The expression becomes $2^{2222...8}= 2^{222...0}*2^{8}$

$=(2^{10})^{222.....2}*2^8$ which is equivalent to finding the last 2 digits of :-

$(24)^{22....2}*2^8$

It may be proved that the last $2$ digits of $24^{even } = 76$

Hence, we need to find last two digits of $76*2^8$ (There is a short trick to it as well. If we multiply $76$ by $2^n,$ it becomes

$(75+1)2^n=75*2^n+2^n$

last $2$ digits of $75*2^n = 00.$ Hence last two digits of $76*2^n =$ last two digits of $2^n$ )

$=\boxed{56}$

Let the exponent be denoted as $A = \underbrace{555\cdots 5 }_{\text{ 21 times }} 7$ since we are asked to find $2016^{A}\bmod(100)$ which we further can write as $\begin{aligned} (2000+16)^A \bmod(100) &\\ = \sum_{r=0}^{A} \binom{A}{r}(2000)^{A -r} (16)^A\bmod(100) \\ = \underbrace{0+0+\cdots +0}_{\text{A-1 times }} + \binom{A}{A}16^A\bmod(100) \\ =2^{4A}\bmod(100) \end{aligned}$ we note that $\text{g.c.d} (2, 100)\neq 1$ so we will consider the following $\begin{cases} 2^{4A }\bmod (4) =0 \\ 2^{4A}\bmod(25)=\,?\end{cases}$ thus we will find the $2^{4A}\bmod (25)$ and $\text{g.c.d}(2,25)=1$ so by Euler's theorem we have $2^{\phi(25)}\equiv 1 \bmod(25) \implies 2^{20} \equiv 1 \bmod (25)$ as $4A \bmod (20) = 8$ therefore we have $2^{4A} \bmod25=2^{8}\bmod(25) \\= 256\bmod(25)=6$ combining these two results and hence by Chinese remainder theorem we find the solution $\mod 100$ such $x\equiv 0\bmod 4$ and $x\equiv 6\bmod(25)$ is 56

The brute force method, using cryptographic methods: $(2016^{555555555555555555555557} \bmod 100)\Rightarrow 56$ . In this case, the power mod function, which applies the mod 100 function whenever applicable.

$5555555555555555555557\Rightarrow 12d2ad2372ed4ce38e5_{16} \Rightarrow \\ 1001011010010101011010010001101110010111011010100110011100011100011100101_2$

The methodology of the power mod function is not difficult.:

The binary bits reversed:

$\{1,\, 0,\, 1,\, 0,\, 0,\, 1,\, 1,\, 1,\, 0,\, 0,\, 0,\, 1,\, 1,\, 1,\, 0,\, 0,\, 0,\, 1,\, 1,\, 1,\, 0,\, 0,\, \\ 1,\, 1,\, 0,\, 0,\, 1,\, 0,\, 1,\, 0,\, 1,\, 1,\, 0,\, 1,\, 1,\, 1,\, 0,\, 1,\, 0,\, 0,\, 1,\, 1,\, 1,\, 0,\, \\ 1,\, 1,\, 0,\, 0,\, 0,\, 1,\, 0,\, 0,\, 1,\, 0,\, 1,\, 1,\, 0,\, 1,\, 0,\, 1,\, 0,\, 1,\, 0,\, 0,\, 1,\, 0,\, \\ 1,\, 1,\, 0,\, 1,\, 0,\, 0,\, 1\}$

The repeated squares of the previous value immediately reduced by the mod 100 function are:

$\{16,\, 56,\, 36,\, 96,\, 16,\, 56,\, 36,\, 96,\, 16,\, 56,\, 36,\, 96,\, 16,\, 56,\, 36,\, 96,\, 16,\, \\ 56,\, 36,\, 96,\, 16,\, 56,\, 36,\, 96,\, 16,\, 56,\, 36,\, 96,\, 16,\, 56,\, 36,\, 96,\, 16,\, 56,\, \\ 36,\, 96,\, 16,\, 56,\, 36,\, 96,\, 16,\, 56,\, 36,\, 96,\, 16,\, 56,\, 36,\, 96,\, 16,\, 56,\, 36,\, \\ 96,\, 16,\, 56,\, 36,\, 96,\, 16,\, 56,\, 36,\, 96,\, 16,\, 56,\, 36,\, 96,\, 16,\, 56,\, 36,\, 96,\, \\ 16,\, 56,\, 36,\, 96,\, 16\}$

Selecting just the squarings corresponding to the $1$ bits in the reversed binary representation of 555555555555555555555557:

$\{16,\, 36,\, 56,\, 36,\, 96,\, 96,\, 16,\, 56,\, 56,\, 36,\, 96,\, 36,\, 96,\, 36,\, 16,\, 36,\, 96,\, \\ 56,\, 36,\, 96,\, 56,\, 16,\, 56,\, 36,\, 16,\, 56,\, 56,\, 16,\, 36,\, 96,\, 56,\, 96,\, 56,\, 16,\, \\ 36,\, 96,\, 56,\, 16\}$

The accumulative products and immediate mod 100 reductions are:

$\{16,\, 76,\, 56,\, 16,\, 36,\, 56,\, 96,\, 76,\, 56,\, 16,\, 36,\, 96,\, 16,\, 76,\, 16,\, 76,\, 96,\, \\ 76,\, 36,\, 56,\, 36,\, 76,\, 56,\, 16,\, 56,\, 36,\, 16,\, 56,\, 16,\, 36,\, 16,\, 36,\, 16,\, 56,\, \\ 16,\, 36,\, 16,\, 56\}$

The desired answer is the last number: 56.

The numbers never get huge! Even in this problem, doing it with pencil and paper is imaginable.