Substitution with Modular Exponents

Question

Why does $3^{-1} \text{mod} \ 10 = 7$ and $3^9 \ \text{mod} \ 10 = 3$? Since -1 and 9 are the same mod 10, shouldn't I be able to replace one with the other?

Answer 1

Similar to the freshman's dream that $(x+y)^n=x^n+y^n$, it's beguiling to think that, if $m\equiv n$ mod $N$, then $a^m\equiv a^n$ mod $N$. What's true, instead, is a bit more complicated to state:

If $m\equiv n$ mod $\phi(N)$, and if $\gcd(a,N)=1$, then $a^m\equiv a^n$ mod $N$.

This is an elaboration of Euler's totient theorem:

If $\gcd(a,N)=1$, then $a^{\phi(N)}\equiv1$ mod $N$.

which is a generalization of Fermat's little theorem:

If $p$ is a prime and $p\not\mid a$, then $a^{p-1}\equiv a$ mod $p$.

It's worth noting that Fermat's little theorem has an equivalent restatement that doesn't put any restriction on $a$:

If $p$ is a prime, then $a^p\equiv a$ mod $p$ for any integer $a$.

It follows that the freshman's dream is true in the limited context, $(x+y)^p\equiv x+y\equiv x^p+y^p$ mod $p$. But there is no equivalent restatement for Euler's generalization. For example, no power of $2$ higher than the first is ever again congruent to $2$ mod $4$.

Answer 2

$3^{-1}\equiv 7\mod 10$ because $7\cdot 3\equiv 1\mod 10$.

As to $^9\bmod 10$, it results from Euler's theorem: $\varphi(10)=\varphi(2) \varphi(5) = 4$, so, as $3$ is coprime to $10$, $3^4\equiv1\mod10$, hence $$3^9\equiv 3^{9\bmod\varphi(10)}=3^1\mod10.$$