# Reduced residue system modulo m

• January 19th 2010, 09:50 PM
kingwinner
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.
• January 19th 2010, 09:59 PM
Drexel28
Quote:

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 $x$ is congruent to $\ell$ for some $\ell\in\{0,\cdots,m-1\}$
• January 20th 2010, 09:05 AM
Dinkydoe
You can show that all numbers x with gcd(x,12) = 1 is of the form $x=12q+r_i$, with $r_i \in \left\{1,5,7,11\right\}$

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

(hint:you can do this by showing that $x\equiv 0$ mod 3, or $x\equiv 0$mod 2)
• January 20th 2010, 07:25 PM
kingwinner
Quote:

Originally Posted by Drexel28
But, every $x$ is congruent to $\ell$ for some $\ell\in\{0,\cdots,m-1\}$

Then what is the point of having part (iii) in the definition?
• January 20th 2010, 07:25 PM
Drexel28
Quote:

Originally Posted by kingwinner
Then what is the point of having part (iii) in the definition?

You tell me.
• January 20th 2010, 08:12 PM
kingwinner
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.