How to compute $21^{4600} \mod 47$

Question

I am struggling to get this problem started. I have looked at similar problems in the book I am using for class (Discrete Mathematics with Applications, 7E) but none of them are seeming to help. Any help on how to solve these types of questions? I understand that I may need to use Fermat's Little Theorem but I am not seeing how to apply it completely.

Answer 1

As you already mentioned, the first thing to do is use Fermat's Little Theorem, which says that for all primes $p$ and any $a$ that's relatively prime to $p$, $$ a^{p - 1} \equiv 1 \mod{p}$$ Notice in your example that $a = 21$ and $p = 47$ are indeed relatively prime, so $$21^{46} \equiv 1 \mod{47}$$ The next thing you want to do is notice that $4600 = 46(100)$. Recall that for any congruence $a \equiv b \mod{n}$, we also have that $a^k \equiv b^k \mod{n}$ for any $k \in \mathbb{N}$. In other words, we can "exponentiate" the congruence to the power of 100 to get $${21^{46}}^{100} \equiv 1^{100} \mod{47}$$ Or simply, $$21^{4600} \equiv 1 \mod{47}$$

Answer 2

Hint: $${4600}=46\cdot100$$ and Fermat's Little Theorem.

Answer 3

I may need to use Fermat's Little Theorem

Indeed. It gives you $21^{46}\equiv 1\pmod{47}$, hence $21^{4600}\equiv 1^{100}=1\pmod{47}$ and you're done.