Why can't I fit certain numbers back into the formula from Fermat's little theorem?

72 Views Asked by At

I'm given that the formula for Fermat's little theorem: $$ a^{-1} \equiv a^{p-2} \ (mod \ p) $$

I presume I would then be able to get an inverse mod directly from this formula. Let's say $p=7$ and $a=2$, I would naively think that I could do this: $$ 2^{-1} \equiv a^{7-2} \ (mod 7) \\ \Rightarrow 2^{-1} \equiv 32 \ (mod 7) \\ \Rightarrow 2 \cdot 32 \equiv 1 \ (mod 7) \\ \Rightarrow 64 \equiv 1 \ (mod 7) $$

The flow seems good so far.

But when I try to do it backwards with a different number, suddenly the formula doesn't seem to hold anymore. For example:

$$ 8 \equiv 1 \ (mod \ 7) \\ 2\cdot 4 \equiv 1 \ (mod \ 7) \\ \Rightarrow 2^{-1} \equiv 4 \ (mod \ 7) $$

However, this doesn't fit back into the formula: $$ a^{-1} \equiv a^{p-2} \ (mod \ p) \\ 2^{-1} \equiv 4 \ (mod \ 7) \\ 2^{-1} \equiv 2^{7-2} = 2^5 \neq 4 $$

As you can see from the last line, when I put it back into the formula, apparently, I am getting $2^{-1} \equiv 32 (mod7)$ instead of $2^{-1} \equiv 4 (mod 7)$!

But I'm quite sure that $2^{-1} \equiv 4 (mod 7)$ is correct because $2 \cdot 4 = 8 \equiv 1 (mod7)$ looks correct to me. The remainder is indeed $1$ when $8 \div 7$.

Is there something I'm not doing right here? Why does the formula only work for certain numbers only?