# How to find a reduced residue system modulo of a number?

The reduced residue system modulo $10$ is: $1, 3, 7, 9$
But how could we find these numbers?
The only thing I know is they're relatively prime to $10$. What does it mean by "no two different elements of the set are congruent to modulo m"?

Thanks,
Chan

-
If you know that they are relatively prime to 10, isn't that your answer? – PEV Feb 26 '11 at 23:26
@PEV: Thanks, I understand it now. How about the second part "no two different elements of the set are congruent to modulo m". Could you help me explain this as well? – Chan Feb 26 '11 at 23:29

The line "no two different elements of the set are congruent modulo $m$" just means that all of your elements are distinct modulo $m$. For example, $1,3,7,9,11,111,1111$ are all relatively prime to $10$, but they do not form a reduced residue system since $1,11,111,1111$ are all the same modulo $10$

Another way to specify the condition is: The reduced residue system modulo $N$ is the set of all integers $m$ with $\gcd(m,N)=1$ and $0\leq m\leq N$.

Hope that helps,

-
 Thanks, I got it ;) – Chan Feb 26 '11 at 23:39

Presumably you refer to the Wikipedia definition of reduced residue system. The point of the definition is to specify a system of representatives for the $\rm\:phi(n)\:$ congruence classes that are units (invertible) $\rm\ (mod\ n)\:.\:$ This amounts to choosing a set of $\rm\:\phi(n)\:$ integers coprime to $\rm\:n\:$ such they they are all distinct $\rm\ (mod\ m)\:$.

-
 How on earth do you think this answer is better. This is unclear at best unless you already understand the material. – Eric Feb 28 '11 at 16:06