Using Fermat's little theorem to find $9^{45} \mod 23$

Question

I used Fermat's Little Theorem to find:

$$9^{45} \mod 23$$ What I have done so far: $$9^{45} = (9^2)^{22}9$$

$$9^{22} \equiv 1 \pmod{23}$$ According to Fermat's Little Theorem.

So, now I have: $$9^{45} \equiv (9^2)^{22}9 \equiv 1^2 9 \pmod{23}$$

So: $$9^{45} \mod 23 = 9$$

I am a bit uncertain about my notation etc. For example, in the last line, should it be a $\equiv$ or a $=$? Can someone please verify my method?

Answer 1

Your solution is correct, but in the last line one should have a $\equiv$, because the numbers are not equal. Furthermore the equivalence sign should be before the mod 23, i.e. $9^{45} \equiv 9 \mod 23$.

In general:

• If the numbers are really equal, both $=$ and $\equiv$ are correct.
• If the numbers are not equal, you should use $\equiv$.