# Help with modulo and congruences

• Feb 19th 2007, 05:27 AM
lyla
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?
• Feb 19th 2007, 08:39 AM
ThePerfectHacker
Quote:

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