Thread: Reduced residue system modulo m

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.

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.

But, every is congruent to for some

You can show that all numbers x with gcd(x,12) = 1 is of the form , with

Or by contradiction: suppose this is not the case then gcd(x,12)

(hint:you can do this by showing that mod 3, or mod 2)

Originally Posted by Drexel28

But, every is congruent to for some

Then what is the point of having part (iii) in the definition?

Originally Posted by kingwinner

Then what is the point of having part (iii) in the definition?

You tell me.

I am guessing. I think (iii) is to avoid saying things like {7, 11} is a reduced residue system modulo 12. {7, 11} satisfies both (i) and (ii), but not (iii)

But still I think (iii) is a very hard criteria to check. To tell whether a very large natural number x is relatively prime to m or not is already very difficult (e.g. how can we tell whether 61 and 654236 are relatively prime or not? how about 61 and 5648796545?), let alone determining whether ALL such numbers is congruent modulo m to some member r_i of the set. I don't see how (iii) can serve as a useful criterion.