Question

If \(a_1, a_2,...a_n\) is a complete set of residues modulo \(n\) and \(gcd(a, n)=1\), then prove that \(aa_1, aa_2,...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 ]

Answer 1

say wat/.?

Answer 2

We have to show that any pair of them is incongruent. We will try to prove the contrapostive by using the fact that: \[a_i \not\equiv a_j (\mod n) \text{ for } i \neq j\]
We suppose \[aa_i \equiv aa_j (\mod n)\] and will show that \[i = j\]
Because \[aa_i \equiv aa_j (\mod n)\]
that means that \[aa_i - aa_j\] must be a multiple of n, say
\[a(a_i - a_j) = nk |k\epsilon \mathbb{Z}\]
By the definition of divides, \[n | a(a_i - a_j)\]
By the hypothesis, we know that \[a \text{ and } n\] are coprime, so we know that \[n | (a_i - a_j)\]Thus we have shown that
\[a_i \equiv a_j (\mod n)\]
and then
\[a_i = a_j \text{ and } i = j \]
since we need \[a_i\]
to form the complete set for \[n\]
We have thus proven that any pair of
\[aa_i \text{ and } aa_j\]
will be incongruent when
\[i \ne j \] and finally that the set of
\[aa_i\] will form the complete set of residues modulo n.

Answer 3

@jasonchutko, thanks a lot!

Answer 4

Sorry my LaTeX is off a little bit :P

Answer 5

@jasonchutko How many members of the set S={\(x:1\le x\le 100\)} are of the form 4n-1. I guess the answer is 25, but is there a way to prove it or show it?

Answer 6

@UnkleRhaukus How many members of the set S={x:1≤x≤100} are of the form 4n-1.
I guess the answer is 25, but is there a way to prove it or show it?

Answer 7

is n an integer?

Answer 8

Yes, n is an integer, sorry, I should have mentioned that @UnkleRhaukus
If you want you can answer it here http://openstudy.com/updates/4f7fe5e1e4b0505bf0829928