Why does $a \equiv b \mod \phi(m) \Longrightarrow n^{a} = n^{b}{\mod m}$, given $gcd(a, m) = 1$?
First of all, what is the relationship between $a$ and $\phi(m)$? I know that $a$ and $\phi(m)$ are coprime, but nothing more.
Second, $n^{b \mod \phi(m)} \Rightarrow n^b \mod m$ somehow. Any clues?
From http://www.math.northwestern.edu/~mlerma/problem_solving/results/modular_arith.pdf
A consequence of Euler’s Theorem is the following. If gcd(a, m) = 1 then x≡y (modφ(m)) ⇒ ax ≡ay (modm). Consequently, the following function is well defined: Z ∗m × Z φ ( m ) → Z ∗m ([a]m, [x]φ(m)) → [ax]m Hence, we can compute powers modulo m in the following way: an = an mod φ(m) (mod m)
If $x\equiv y \mod \phi (m)$, then $x=y+r\phi(m)$ for some integer $r$. Consequently $$ a^x\equiv a^{r\phi (m)}a^y\equiv 1\cdot a^y \equiv a^y\mod m, $$ because $a^{\phi(m)}\equiv 1 \mod m$, and $1^r=1$.