How can I conclude that the integers $a r_1, a r_2 ... ar_{\phi(m)}$ modulo $m$ are a permutation of the integers $r_1,r_2,...,r_{\phi(m)}$? How can I conclude that the integers $a r_1, a r_2 ... ar_{\phi(m)}$ modulo $m$ are a permutation of the integers $r_1,r_2,...,r_{\phi(m)}$ given the proofs that $(ar_i,m) = 1$ ($\gcd$) for every $i$ and $ar_i$, $a r_j$ are incongruent for $i \neq j$ ?
I know $ar_i$, $a r_j$ are incongruent implies their least residues are different, so we have $\phi(m)$ least residues (all different).
How can I see that these least residues satisfy $(a r_j \mod m, m) = 1$ ? 
I have a theorem saying that $(a,b) = (a, a \mod b)$ where $a,b$ are positive integers, but in this case $a r_j$ might well be negative ?

 A: $(ar, m) = 1 \implies (a,m) = 1$ and $(r, m) = 1$.  Proof:  if not for either, then there's $d \neq 1$ dividing both $ar$ and $m$.
You already have that $r_i \neq r_j \pmod m$ since if they're equal then $a$ times them are equal, but you say that's not true.  Thus the $r_i$ make up $\phi(m)$ representatives of the multiplicatve group of units $\pmod m$.  
And since $a$ is also a unit (first paragraph), the map $U \to U, x \mapsto ax$ is a permutation of the units $U$.  Choose representatives equal to the original set, and you have that $a$ permutes those representatives.

Note: For any group $G$, and $g \in G$, the map $x \mapsto gx$ is a permutation of $G$.  Prove that.
Note:  $a \in \Bbb{Z}$ is congruent/equal to a unit $\pmod m$ iff $(a,m) = 1$.
Note: a unit element in a ring is an element with a multiplicative inverse in that ring.
Note: $\phi(m) = $ the number of elements in the multiplicative group of units $\pmod m$, or $|U|$ from above.

Note: some of these notes are immediate implications of the others.
