Why does $\{1\cdot a\! \! \pmod p, 2\cdot a\! \!  \pmod p,\ldots, (p-1)\cdot a\! \!  \pmod p\}$ $= \{1, 2,\ldots, p-1\}$ when $a$ and $p$ are coprime? Why is it that $\{1\cdot a \pmod p, 2\cdot a \pmod p,\ldots, (p-1)\cdot a \pmod p\} = \{1, 2,\ldots, p-1\}$ (albeit in a different order) when a and p are coprimes?
I can't figure this out and I've been beating my head for the whole weekend.
Googling around I've found mention of Fermat's Little Theorem (e.g. here), but I can't see how it helps me.
I've verified it by hand, it seems perfectly believable to me (mostly because I find myself thinking of the way the circle of fifths works), but I can't come up with a good proof.
Any help, pretty please?
Thanks a lot.
P.S.: Pardon my English. I'm from the land of pizza and mandolins.
 A: Suppose $ra$ and $sa$ are the same, modulo $p$. Then $sa-ra$ is a multiple of $p$. So $(s-r)a$ is a multiple of $p$. But by hypothesis $a$ and $p$ are coprime, so $s-r$ is a multiple of $p$. But if $r$ and $s$ are between 1 and $p-1$, inclusive, then $s-r$ can't be a multiple of $p$ unless $r=s$. 
This shows that all the numbers in the first set in your question are different. Since zero doesn't appear in that set, and since there are $p-1$ numbers in that set, they must be the same as the numbers in the second set in your question. 
A: If it weren't the case, that would mean that you can get back to the same place in $n\lt p$ steps of $a$; that is, we would have $na=kp$ for some integer $k$. But $a$ and $p$ are coprime, so all the factors of $p$ have to come from $n$, which contradicts $n\lt p$.
A: This can be interpreted as a group-theoretic result: the set of numbers coprime to $n$ form a group under multiplication modulo $n$. The hardest part of this is showing that inverses exist. This follows from Bézout's theorem, which states that for any $a$ and $n$ there exist $x$ and $y$ coprime such that $ax + yn = \gcd(a,n)$. From this we can see that if $a$ and $n$ are coprime, i.e. $\gcd(a,n)=1$, then $ax$ is $1$ mod $n$, and $x$ must be coprime to $n$ too (because $\gcd(r,s)$ divides any combination of $r$ and $s$, and here we have a combination of $x$ and $n$ that gives 1), so $a$ has a multiplicative inverse modulo $n$.
Anyway, once you've got that the set of numbers coprime to $n$ form a group under multiplication modulo $n$, that's essentially equivalent to saying the map "multiply by $a$" is a bijection modulo $n$. That's essentially the same as your original statement.
(Technicality: we showed that multiply-by-$a$ is invertible in the group of numbers coprime to $n$ modulo $n$, when really what we wanted was for it to be invertible in the set of numbers modulo $n$, but it's not hard to see that the argument above extends to that case. I suppose what I'm really doing is showing that $a$ is a unit in the ring of numbers modulo $n$, and the group I mentioned is the group of units in that ring).
This answer uses some more heavyweight machinery than necessary, but I think it's a neat way of looking at the result.
