Remainder of large power of 3

What is the remainder when $$3^{2^{2016}}-1$$ is divided by $2^{2019}$?

My thought was that we could split it up in $$\left( 3^{2^{2015}}-1 \right)\left( 3^{2^{2015}}+1 \right)$$ and then keep doing that until we get something like $$8 \prod_{k=1}^{2015} \left( 3^{2^{k}}+1 \right)$$

Well I see that each term is divisible by 2 at least once, and there's a $2^3$ left over so the whole thing is at least divisible by $2^{2018}$, but I'm not quite sure how to find it modulo $2^{2019}$?

Note This is an old competition problem, but I unfortunately do not know the correct answer.

1 Answer

Hint: Prove by induction that $3^{2^{n-3}} \equiv 1 + 2^{n-1} \bmod 2^n$ for $n \ge 4$.

(This implies that $3$ has order $2^{n-2}$ mod $2^n$, the largest possible order.)

• How could I suspect this myself? – mysatellite Apr 6 '17 at 16:30
• @Sky, by trying a few examples with small $n$. I knew that from the structure of $U(2^n)$, hence my remark in the last sentence. – lhf Apr 6 '17 at 16:31
• @Sky, or you could expand $3^{2^k}=(1+2)^{2^k}$ using the binomial theorem. – lhf Apr 6 '17 at 17:20