# 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

Relevance

- siamese_scytheLv 710 years agoFavourite 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

Still have questions? Get answers by asking now.