How to get remainder when $33^{111}$ is divided by $111$?

Question

How to get the remainder when $33^{111}$ is divided by $111$?

I tried Chinese Remainder Theorem, but that is not working. Probably due to $(33,111) \neq 1$, right?

Please guide.

Answer 1

Hint: It looks like you're misapplying the CRT (Chinese Remainder Theorem, I assume). Note that $111 = 3 \times 37$. It follows that if we know the value of $33^{111}$ modulo $3$ and we know the value of $33^{111}$ modulo $37$, then we can find the value of $33^{111}$ modulo $111$.

Answer 2

Hint:

$111=3\times37$ is square-free, and the Carmichael function of $111$ is $36$, so $a^{37}\equiv a\bmod111$

Answer 3

You might start with $11$. $11^2 = 121 \equiv 10 \pmod{111}$ so $11^3 \equiv 10\cdot 11 \equiv -1 \pmod{111}.$

So you have $11^{111} \equiv (11^3)^{37} \equiv (-1)^{37} \equiv -1 \pmod {111}.$

Next, by Fermat's Little Theorem, you have $3^{37} \equiv 3 \pmod{37}$, so $3^{111} \equiv 3^3 \equiv 27 \pmod{37}$. Also $3^{111} \equiv 0 \pmod{3}$ and since $27$ is a multiple of $3$, by CRT, $3^{111} \equiv 27 \pmod{111}.$

Then you have $33^{111} \equiv 3^{111}11^{111} \equiv 27\cdot(-1) \equiv 84 \pmod{111}.$