Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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"?


share|cite|improve this question
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
Exactly. the first part gives the solution while the second part tell when to stop. – Guest Mar 27 '14 at 7:53
up vote 4 down vote accepted

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,

share|cite|improve this answer
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)\:$.

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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.