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?

Printable View

- February 19th 2007, 05:27 AMlylaHelp 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? - February 19th 2007, 08:39 AMThePerfectHacker
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).