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.