I've been trying to figure this out all night with no luck.
Here is what I've noticed: $\varphi(n)$ is the number of units or generators of a set. I'm trying to connect this to $n^p$ being congruent to $n \pmod p$ where $\gcd(n,p) = 1$. But I don't see it. Why would this tell me that the number of numbers relatively prime to $n$ is $n^p - n^{p-1} $?