2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.)

$\endgroup$
  • $\begingroup$ How could I suspect this myself? $\endgroup$ – mysatellite Apr 6 '17 at 16:30
  • $\begingroup$ @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. $\endgroup$ – lhf Apr 6 '17 at 16:31
  • $\begingroup$ @Sky, or you could expand $3^{2^k}=(1+2)^{2^k}$ using the binomial theorem. $\endgroup$ – lhf Apr 6 '17 at 17:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.