Question

WHAT IS THE REMAINDER WHEN
`32^{37^(32) }` 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`