## 2bornot2b 3 years ago 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 ]

1. UnkleRhaukus

say wat/.?

2. jasonchutko

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.

3. 2bornot2b

@jasonchutko, thanks a lot!

4. jasonchutko

Sorry my LaTeX is off a little bit :P

5. 2bornot2b

@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?

6. 2bornot2b

@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?

7. UnkleRhaukus

is n an integer?

8. 2bornot2b

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