Tomi's Challenges - #23

Note that the expression can be written as:

$Q = \frac {\phi \left(17(a_1 - a_2 - a_3 - a_4 - a_5 - a_6 - a_7 - a_8) \right)}{4^{15}}$

where

$\begin{aligned} a_1 & = 20^8 = 4^8 5^8 = 4^8 (4+1)^8 \\ & = 4^8 (4^8 + 8 \cdot 4^7 + 28 \cdot 4^6 + 56 \cdot 4^5 + 70 \cdot 4^4 + 56 \cdot 4^3 + 28 \cdot 4^2 + 8 \cdot 4 + 1) \\ & = 16^8 + 8 \cdot 16^7 \cdot 4 + 28 \cdot 16^6 \cdot 4^2 + 56 \cdot 16^5 \cdot 4^3 + 70 \cdot 16^4 \cdot 4^4 + 56 \cdot 16^3 \cdot 4^5 + 28 \cdot 16^2 \cdot 4^6 + 8 \cdot 16 \cdot 4^7 + 4^8 \\ & = 16^8 + a_2 + a_3 + a_4 + a_5 + a_6 + a_7 + a_8 + 4^8 \end{aligned}$

Then

$\begin{aligned} Q & = \frac {\phi \left(17(16^8+4^8)\right)}{4^{15}} \\ & = \frac {\phi \left(17\cdot 4^8(4^8+1)\right)}{4^{15}} \\ & = \frac {\phi \left(17\cdot 4^8 \cdot \blue{65537} \right)}{4^{15}} & \small \blue{\text{Note that }65537 \text{ is a prime.}} \\ & = \frac {17\cdot 4^8 \cdot 65537}{4^{15}} \cdot \frac {16}{17} \cdot \frac 12 \cdot \frac {4^8}{65537} \\ & = \frac {4^{18}}{2\cdot 4^{15}} = \boxed{32} \end{aligned}$

The gist of this problem is the following two things:

• $\phi(p)=p-1$ , for any prime number $p$ .
• $\phi(p)=\frac{p}{2}$ whenever a natural number $p$ is a power of 2.

Knowing these two things, let's solve the problem. The first step is to simplify the numerator:

$\phi(17\cdot 20^8-17\cdot 8\cdot 16^7\cdot 4-17\cdot 28\cdot 16^6\cdot 4^2-17\cdot 56\cdot 16^5\cdot 4^3-17\cdot 70\cdot 16^4\cdot 4^4-17\cdot 56\cdot 16^3\cdot 4^5-17\cdot 28\cdot 16^2\cdot 4^6-17\cdot 8\cdot 16\cdot 4^7)=$ $=\phi(17(20^8-8\cdot 16^7\cdot 4-28\cdot 16^6\cdot 4^2-56\cdot 16^5\cdot 4^3-70\cdot 16^4\cdot 4^4-56\cdot 16^3\cdot 4^5-28\cdot 16^2\cdot 4^6-8\cdot 16\cdot 4^7))=$ $=\phi(17((16+4)^8-8\cdot 16^7\cdot 4-28\cdot 16^6\cdot 4^2-56\cdot 16^5\cdot 4^3-70\cdot 16^4\cdot 4^4-56\cdot 16^3\cdot 4^5-28\cdot 16^2\cdot 4^6-8\cdot 16\cdot 4^7))=$ $=\phi(17(16^8+4^8))$ Since $16^8+4^8$ is even, it's relatively prime with $17$ . Therefore: $=\phi(17)\phi(16^8+4^8)=16\cdot \phi(16^8+4^8)$

The next problem is to find $\phi(16^8+4^8)$ . Notice that $\phi(16^8+4^8)=\phi(4^8\cdot (4^8+1))$ . These two numbers are adjacent so they are relatively prime. We have:

$\phi(4^8\cdot (4^8+1))=\phi(4^8)\phi(4^8+1)$ . Since $4^8=2^{16}$ , it's a power of 2 so $\phi(2^{16})=\frac{2^{16}}{2}=2^{15}$ .

Now we need to find $\phi(4^8+1)$ . Notice that

$4^8+1=2^{16}+1=2^{2^4}+1$ . This is a Fermat number , and it is known that all Fermat numbers up to and including $2^{2^4}+1$ are prime. Therefore $\phi(4^8+1)=2^{16}$ . All in all, we have the following:

$\frac{16\cdot 2^{31}}{4^{15}}=\frac{16\cdot 2^{31}}{2^{30}}=2\cdot 16=32$ .