Originally Posted by

**kingwinner** __Definition:__

A **reduced residue system modulo m** is a set of integers such that

(i) gcd(r_i, m) = 1,

(ii) r_i ≡/≡ r_j (mod m) if i≠j,

(iii) AND such that EVERY x relatively prime to m is congruent modulo m to some member r_i of the set.

==================================

I am concerned about the last part of the definition. So according to this definition, is it even possible to tell whether a set is a reduced residue system modulo m? (because we have to check that EVERY x relatively prime to m is congruent modulo m to some member r_i of the set, which doesn't seem possible? How can we check every single x?)

For example, how do we know whether {1, 5, 7, 11} is a reduced residue system modulo 12 or not? Look at part (iii) of the definition, we need to check that EVERY x relatively prime to 12 is congruent modulo 12 to some member r_i of the set. But I think there are many many such numbers, how can we possibly check them all?

Thank you.