Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

2bornot2b

  • 4 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 ]

  • This Question is Closed
  1. UnkleRhaukus
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    say wat/.?

  2. jasonchutko
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    @jasonchutko, thanks a lot!

  4. jasonchutko
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Sorry my LaTeX is off a little bit :P

  5. 2bornot2b
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    @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
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    @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
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    is n an integer?

  8. 2bornot2b
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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

  9. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy