0

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?

mathnw
  • 89
  • 1
    Why are you calculating powers of $3$ modulo $17$? Those should be calculated modulo $17-1 = 16$, since they are the exponent. – Arthur Dec 10 '16 at 17:12
  • If you know that $2^{16}\equiv1\pmod{17}$ then you probably want to find out the remainder of $3^{2011}$ when divided by $16$, no? – Jyrki Lahtonen Dec 10 '16 at 17:40

3 Answers3

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.

Serenity
  • 834
1

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$
πr8
  • 10,800
  • :( I dont undestand,, why, mod 8 or mod 2 – mathnw Dec 10 '16 at 17:39
  • So, we're looking at $2^n \mod 17$, and the easiest way to simplify this is to find the order of $2$, $\mod 17$. Given that $2^8\equiv 1 \mod 17$, we see that $2^{8k}\equiv 1 \mod 17$ for any integer $k$, so really we just need to find what remainder $n$ has $\mod 8$. The same argument works for the inner exponent. – πr8 Dec 10 '16 at 22:45
0

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} $$

egreg
  • 238,574