Thread: Help with modulo and congruences

If a1,a2,...,an is a complete set of residues modulo n and gcd(a,n)=1.
prove that aa1,aa2,...,aan is also a complete set of residues modulo n

[Hint: It suffices to show that the number in question are incongruent modulo n.]

Any ideas?

Originally Posted by lyla

If a1,a2,...,an is a complete set of residues modulo n and gcd(a,n)=1.
prove that aa1,aa2,...,aan is also a complete set of residues modulo n

[Hint: It suffices to show that the number in question are incongruent modulo n.]

Any ideas?

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).