Estonian Math Competitions

We have $3^{2016} - 1 = (3^{63} - 1)(3^{63} + 1)(3^{126} + 1)(3^{252} + 1) \cdot (3^{504} + 1)(3^{1008} + 1)$.

Numbers $3^{126}$, $3^{252}$, $3^{504}$ and $3^{1008}$ are squares of odd numbers, hence congruent to $1$ modulo $8$. Thus $3^{126} + 1$, $3^{252} + 1$, $3^{504} + 1$ and $3^{1008} + 1$ are congruent to $2$ modulo $8$. Consequently, these four factors are divisible by $2$ but not by $4$.

As $3^{62} \equiv 1 \pmod{8}$, we have $3^6 \equiv 3 \pmod{8}$ (mod $8$). Hence $3^{63} - 1$ and $3^{63} + 1$ are congruent to $2$ and $4$ modulo $8$, respectively. The former thus is divisible by $2$ but not by $4$ and the latter is divisible by $4$ but not by $8$.

Putting it all together, the exponent of $2$ in the product is $1+2+1+1+1+1=7$.