# Fermat Little Theorem Problem

By Fermat's Little theorem, because $31$ is prime, we have $a^{30}\equiv 1 \pmod {31}$, for all $0 < a < p$.

Then $$5^{30,000}\equiv (5^{1,000})^{30}\equiv 1 \pmod{31}$$ and $$6^{123,456}\equiv 6^{123,450}\cdot 6^6\equiv 1\cdot 6^6\equiv (6^2)^3\equiv 5^3\equiv 125\equiv 1\pmod{31}$$

In above solution, I'm not sure how it gets from $(6^2)^3$ to $≡5^3$ . Is it because they both result in 1 mod 31?

$6^2 ≡ 36 ≡ 5 \mod 31$. so $(6^2)^3 ≡ 5^3 \mod 31$