Sum of factors of a huge number.

Question

I recently appeared in a math olympiad and it had this one question which had me stumped. This was a few weeks back and I have been looking for a way to find its answer ever since, but with no success. Searched the internet for the solution, but couldn't find any on it too! Anyway, here's how the question goes:

The value of $2^{96} - 3^{16}$ has two factors between 60 and 70. What is the sum of these two factors?

BTW, I should add that I did use wolframalpha to actually find the answer so I am more interested in knowing how to work it out manually than just knowing the answer. Any feedback would be appreciated.

Thanks!

Answer 1

Using $a^2-b^2 = (a+b)(a-b)$ \begin{align*} 2^{96}-3^{16} ={} & (2^{48}+3^8)(2^{48}-3^8) \\ ={} & (2^{48}+3^8)(2^{24}+3^4)(2^{24}-3^4) \\ ={} & (2^{48}+3^8)(2^{24}+3^4)(2^{12}+3^2)(2^{12}-3^2) \\ ={} & (2^{48}+3^8)(2^{24}+3^4)(2^{12}+3^2)(2^6+3)(2^6-3) \end{align*} and $2^6+3=67$, $2^6-3=61$, ...

Answer 2

Modulo $61$: $$2^6=64=3,2^{12}=9,2^{24}=81=20,2^{48}=400=34,\color{green}{2^{96}}=1156=\color{green}{58},$$ $$3^2=9=2^{12},\color{green}{3^{16}}=2^{96}=\color{green}{58}.$$

Similarly, modulo $67$ yields twice $25$.

---

Actually there is no need to perform the whole computation. Just observe

$$2^{12}\equiv3^2\mod61,\\2^{12}\equiv3^2\mod67.$$