Find the residue to divide $2^{3^{2011}}$ between $17$

Question

help with this excercises.

Find the residue to divide $2^{3^{2011}}$ between $17$

I try:

$$3^3 \equiv 10(mod\ 17)$$ $$3^{10} \equiv 8(mod\ 17)$$ $$3^{120} \equiv -1(mod\ 17)$$ $$3^{2011} \equiv 7(mod\ 17)$$

Then

$$2^{3^{2011}}=2^7*2^{17k}, k\in \mathbb{Z}$$

• $2^{16}\equiv1(mod\ 17)$

then??

Other way?

Answer 1

Write it as $$2^{3^2.3^{2009}} = 512^{3^{2009}} = (510+2)^{3^{2009}}$$ 510 is divisible by 17. Now use binomial expansion. All terms except the last one, i.e. $2^{3^{2009}}$ will be divisible by 17. So the problem reduces to finding the remainder when $2^{3^{2009}}$ is divided by 17.

Again do the same process, until you reach $2^{3^1}$ = 8

Hence remainder is 8.

Answer 2

Note that:

• $2^8\equiv 1\mod 17 \implies$ worth looking at $3^{2011} \mod 8$
• $3^2 \equiv 1\mod8, \,2011\equiv 1 \mod2\implies 3^{2011}\equiv3^1=3 \mod8$
• $\implies 2^{3^{2011}}\equiv2^3=8\mod 17$

Answer 3

Since $17$ is prime and $2\not\equiv0\pmod{17}$, Euler-Fermat tells you that $2^{16}=1$, so you can first try finding the remainder of $3^{2011}$ when divided by $16$. Since $\gcd(3,16)=1$, again Euler-Fermat tells you that $3^{\varphi(16)}\equiv 1\pmod{16}$. Now $\varphi(16)=\varphi(2^4)=2^4-2^3=8$.

Since $2011\equiv 3\pmod{8}$, we have $3^{2011}\equiv 3^3\equiv 11\pmod{16}$ and therefore $$ 2^{3^{2011}}\equiv 2^{11}\pmod{17} $$ Finally $$ 2^{11}=2^{4}\cdot2^{4}\cdot2^3\equiv(-1)\cdot(-1)\cdot8\equiv 8\pmod{17} $$