Remainder of $7^{7^{7}}$ divided by $32$

Question

The problem is to find remainder of $7^{7^{7}}$ divided by $32$ the quickest way.

My attempt:
$32 = 8.4$
Mod 8: $7^{7^{7}}\equiv(-1)^{7^{7}}\equiv-1$
Mod 4: $7^{7^{7}}\equiv(-1)^{7^{7}}\equiv-1$
Hence in mod $32$: $7^{7^{7}}\equiv(-1)$ mod $8.(-1)$mod$ 4 (?) \equiv 7.3\equiv21 $

I am quite worried about the last step. I can't justify it. Is there a theorem related to (?) or
Is there a better and correct way to do this ?

Answer 1

You are correct that $7^{4}-1 = 48 \times 50 \equiv 0$ (mod $32$). Now $7^{7} \equiv (-1)^{7} \equiv -1$ (mod $4$). Hence $7^{7^{7}} \equiv 7^{-1}$ (mod $32$). Now we have seen that $7^{4} \equiv 1$ (mod $32$), so that $7^{-1} \equiv 7^{3}$ (mod $32$). But $7^{2} = 49 \equiv 17$ (mod $32$), and $7^{3} \equiv 7 \times 17 \equiv 119 \equiv 23 \equiv -9$ (mod $32$).

Answer 2

Fact: $a^{2^{k-2}}\equiv 1\pmod{2^k}$ for all $k\ge 3$, odd $a$.

Proof: We use induction. $a^2\equiv 1\pmod{8}$ for all odd $a$.

If $a^{2^{m-2}}\equiv 1\pmod{2^m}$, we want to prove $a^{2^{m-1}}\equiv 1\pmod{2^{m+1}}$.

I.e. if $a^{2^{m-2}}=2^mk+1$, we want to prove $\left(2^mk+1\right)^2\equiv 1\pmod{2^{m+1}}$.

$$\left(2^mk+1\right)^2\equiv 2^{2m}k+2^{m+1}k+1\equiv 1\pmod{2^{m+1}}$$

So $7^{8}\equiv 1\pmod{32}$. Then $$7^{7^7}\equiv 7^{7^7\pmod{8}}\equiv 7^{(-1)^7}\equiv 7^{-1}\pmod{32}$$

$$\equiv \frac{1}{7}\equiv \frac{5}{7\cdot 5}\equiv \frac{5}{3}\equiv \frac{-27}{3}\equiv -9\equiv 23\pmod{32}$$

Answer 3

Let $a$ be $a=8=2^3$ so $a^n\equiv 0 (mod\space 32)$ for all $n>1$.

Now $7^7=(a-1)^7=32M+7a-1\equiv 55\equiv 23 (mod\space 32)$.

Hence $$7^{7^7}\equiv 7^{23}\equiv 32N+7a-1\equiv 23(mod\space 32)$$ Thus the asked remainder is 23.