You use the Pigeonhole principle.

We assume that

aa_i=aa_j (mod n)

Since gcd(a,n)=1 we can cancel preserving the modulos,

a_i=a_j (mod n)

Thus the only way these can be congruence to each other if they are only equal to each other.

Meaning aa_1,aa_2,...,aa_n are all distint.

And there are "n" of them.

By Dirichlet's Pigeonhole principle it is some premutation of the set {a_1,...,a_n} (not necessarily in that order).

(This is exciting for you, is it not, you are about to prove Euler's theorem on Fermat's theorem).