Prove that the set 0n, 1n, 2n, ... , (m-1)n is a complete residue system modulo m?

Given that m and n are relatively prime integers greater than 1.

2 Answers

  • 9 years ago
    Favorite Answer

    You have the set S = {0n, 1n, 2n, ... , (m-1)n}. Suppose there is a duplicate in S mod m; without loss of generality take a < b such that an congruent to bn (mod m), and we know 0 < b - a < m. So n(b - a) is congruent to 0 (mod m). Because gcd(m,n) = 1, we must have b - a congruent to 0 (mod m), but this is impossible because 0 < b - a < m. So there are no duplicates in S mod m. Therefore every equivalence class mod m is represented, and we are done.

    • Log in to reply to the answers
  • 4 years ago

    n =41/ 3

    • Log in to reply to the answers
Still have questions? Get answers by asking now.