If both sides of $2^{31}\equiv (-1)^{31}\equiv 2\mod 3$ is multiplied by $2$ then will it be $2^{32}\equiv4\mod 3$ or $2^{32}\equiv4\mod 6$?

Question

We have to find the remainder of

$$32^{({32^{32}})}\mod 9$$

$\gcd(9,32)=1$ and by Euler's theorem we find $\phi(9)=9\cdot\frac{2}{3}=6$

Now

$$32\equiv5\mod 9 \ \\ 32 \equiv 2 \mod 6$$

$$\therefore32^{32}\equiv 2^{32}\mod 6$$

Now here comes a part where I am stuck. We know $2\equiv 2\mod 6$,

hence $2^{32}\equiv2^{32}\mod 6 \\ \Rightarrow 2^{31}\equiv (-1)^{31}\equiv 2\mod 3$

Now if I multiply both sides by $2$, then will it be $2^{32}\equiv4\mod 3$
or $2^{32}\equiv4\mod 6$?

I know that $a\cdot c\equiv b\cdot c \mod m$ but we don't multiply $m$ with $c$. Here I am little confused.

But I know the method to solve the whole but I am stuck in this little area.
Please help me. Any help is appreciated.

Answer 1

Another way without theorems. $$32^N=(27+5)^N\equiv5^N\pmod9\\32^{32}\equiv5^{32}\pmod9$$ $$\begin{cases}5^1\equiv5\pmod9\\5^2\equiv7\pmod9\\5^3\equiv8\pmod9\\5^4\equiv4\pmod9\\5^5\equiv2\pmod9\\5^6\equiv1\pmod9\end{cases}\Rightarrow \begin{cases}5^6\equiv1\pmod9\\5^9\equiv8\pmod9\\5^{9(2n+1)}\equiv8\pmod9\\5^{9(2n)}\equiv1^\pmod9\end{cases}$$ It follows $$5^{32}=5^{30+2}\equiv5^2\equiv7^\pmod9\iff5^{32}=7+9M$$ So we have $$32^{32^{32}}=32^{7+9M}\Rightarrow\text{$M$ is odd }$$ It follows $$32^{32^{32}}=5^{7+9(2n+1)}=5^7\cdot8\equiv5\cdot8\equiv\color{red}{4}\pmod9$$

Answer 2

$\gcd(32,9) = 1$ so $32^{\phi (9)} = 32^{6} \equiv 1 \mod 9$ via Eulers theorem.

So if $32^{32} \equiv k \mod 6$ then $32^{32^{32}} \equiv 32^k \equiv 5^k \mod 9$.

$32^{32} \equiv 0 \mod 2$ and $32^{32} \equiv (-1)^{32} \equiv 1 \mod 3$ so by Chinese remained theorem $32^{32} \equiv 4 \mod 6$.

So $32^{32^{32}} \equiv 32^4 \equiv 5^4 \equiv 25^2 \equiv (-2)^2 \equiv 4 \mod 9$.

Answer 3

To answer your particular question: you can use the Chinese Remainder Theorem at the end. You've already found that $2^{31}\equiv 2\pmod 3$; this implies that $2^{32}\equiv 1\pmod 3$. (Even more quickly, you could note that $2^2\equiv 1\pmod 3$ and therefore $2^{32}=\left(2^2\right)^{16}\equiv1^{16}\equiv 1\pmod 3$.) Also, clearly, $2^{32}\equiv 0\pmod 2$. So you just need to find the residue class $\pmod 6$ that's $\equiv 1\pmod 3$ and $\equiv 0\pmod 2$. In this case, the quickest is to work 'by sight'; the two $\bmod 6$ residue classes that are $\equiv 1\pmod 3$ are $\langle1\rangle$ and $\langle4\rangle$, and clearly only one of these is even.

Answer 4

Notice that $32 \equiv 5 \pmod 9$

So now we have $5^{32^{32}}$

We also have $5^3 \equiv -1 \pmod 9$

We know that $32^{32} =3 \lfloor \frac {32^{32}}{3} \rfloor + r$ where r is the remainder of dividing $32^{32}$ by $3$

So now let's try to find r

$32^{32} \equiv 2^{32} \equiv (2^2)^{16} \equiv 4^{16} \equiv 1^{16} \equiv 1 \pmod 3$

So $r=1$. But we also know that $3 \lfloor \frac {32^{32}}{3} \rfloor + r$ must be even because it equals $32^{32}$

So now we can say that $3 \lfloor \frac {32^{32}}{3} \rfloor$ must be odd, since we get an even number when we add 1 to it.

A number of the type $3k$ can only be odd if k is odd, so $\lfloor \frac {32^{32}}{3} \rfloor$ must then also be odd. So we'll write $\lfloor \frac {32^{32}}{3} \rfloor = 2k+1$ for our final proof below

$5^{32^{32}} \equiv 5^{3 \lfloor \frac {32^{32}}{3} \rfloor + 1} \equiv 5^{3(2k+1) +1} \equiv (5^3)^{2k+1} \cdot 5 \equiv (-1)^{2k+1} \cdot 5 \equiv -5 \equiv 4 \pmod 9$