Sum of factors of a huge number.

Solution 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$, ...

Solution 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.$$