Question

2^2^22 divided by 9 then what is the remainder?

Answer 1

First we find which remainder is left on dividing 2²² by 9.

We have,

$2^3\equiv-1\pmod{9}\\\\\therefore\ (2^3)^2=2^6\equiv(-1)^2=1\pmod{9}$

Hence,

$(2^6)^3=2^{18}\equiv1\pmod{9}\\\\2^{18}\times2^4=2^{22}\equiv16\equiv7\pmod{9}$

So the remainder on dividing 2²² by 9 is 7.

Let 2²² = 9q + 7.

Since LHS is even, hence the RHS, 9q + 7, is also even. Since 7 is odd, this implies 9q must be odd, so is 'q'.

So,

$2^{2^{22}}=2^{9q+7}\\\\=(2^9)^q\times2^7$

But,

$2^3\equiv-1\pmod{9},\\\\\implies(2^3)^3=2^9\equiv(-1)^3=-1\pmod{9}$

and,

$2^7=(2^3)^2\times2\equiv2\pmod{9}\\\\\\\therefore\ (2^9)^q\times2^7\equiv(-1)^q\times2\\\\=-2\equiv\mathbf{7}\pmod{9}$

Hence 7 is the answer. Here $(-1)^q = -1$ since q is odd.