Number Theory: Complete set of residues modulo $n$

Question

I have this problem assigned for homework and I'm struggling with the proof of it:

If $a_1,a_2,\dotsc,a_n$ is a complete set of residues modulo $n$ and $\gcd(a,n)=1$, prove that $aa_1,aa_2,\dotsc,aa_n$ is also a complete set of residues modulo $n$.

(Hint: It suffices to show that the numbers in question are incongruent modulo $n$.)

I'm in elementary number theory so I'm not allowed to use an high-level theorems to prove this, I pretty much have to use the basics of modulo.

Thanks!

Answer 1

Suppose to get a contradiction that $aa_i-aa_j=a(a_i-a_j)\equiv0\pmod n$ for some $i,j\in\{1,2\ldots,n\},$ $i\neq j.$ Then, since $\gcd(a,n)=1,$ $a_i-a_j\equiv0\pmod n$ (note that this is a consequence of the elementary Euclid's lemma, which states that if $\gcd(x,y)=1$ and $x\mid yz$ then $x\mid z$), which is clearly false.

Answer 2

since $(a,n)=1$ hence there exist b such that $ab=_n 1$ so $aa_i=_n aa_j \implies a_i=_n a_j$