Question

WHAT IS THE REMAINDER WHEN alt="32^{37^{32} }" align="absmiddle" class="latex-formula"> IS DIVIDED BY 9?

Answer 1

Recall Euler's theorem: if $\gcd(a,n) = 1$, then

$a^{\phi(n)} \equiv 1 \pmod n$

where $\phi$ is Euler's totient function.

We have $\gcd(9,32) = 1$ - in fact, $\gcd(9,32^k)=1$ for any $k\in\Bbb N$ since $9=3^2$ and $32=2^5$ share no common divisors - as well as $\phi(9) = 6$.

Now,

$37^{32} = (1 + 36)^{32} \\\\ ~~~~~~~~ = 1 + 36c_1 + 36^2c_2 + 36^3c_3+\cdots+36^{32}c_{32} \\\\ ~~~~~~~~ = 1 + 6 \left(6c_1 + 6^3c_2 + 6^5c_3 + \cdots + 6^{63}c_{32}\right) \\\\ \implies 32^{37^{32}} = 32^{1 + 6(\cdots)} = 32\cdot\left(32^{(\cdots)}\right)^6$

where the $c_i$ are positive integer coefficients from the binomial expansion. By Euler's theorem,

$\left(32^{(\cdots)\right)^6 \equiv 1 \pmod9$

so that

$32^{37^{32}} \equiv 32\cdot1 \equiv \boxed{5} \pmod9$