MODBasic PolynomialAndEquation Basic

Problem - 2811

Find the largest positive integer $n$ such that $(3^{1024} - 1)$ is divisible by $2^n$.


Note that $$3^{1024 - 1} = (3^{512} + 1)(3^{256} + 1)(3^{128} + 1)\cdots (3^2+1)(3 + 1)(3 - 1)$$

All the $11$ factors are even. Among them

  • $(3-1)$ is clearly not divisible by $4$.
  • $(3+1)$ is a multiple of $4$.
  • We claim none of the remaining terms is a multiple of $4$.

The last conclusion holds because when $k$ is a positive integer, $$3^{2k} + 1\equiv (-1)^{2k} + 1\equiv 2\pmod{4}$$

Therefore, $n=1+2+9=\boxed{12}$.

report an error