Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In my elementary number theory class, we have the following definition which i'm just having trouble understanding what they mean:

Definition: A complete system of residues modulo m is a set of integers such that every integer is congruent modulo m to exactly one integer in the set.

The example they have following is confusing. I cant really imagine what this looks like and why its important that an integer in the set is congruent to exactly on other integer in the set. Can someone help me understand, perhaps with a simple example?

edit:

The example given is {0,1,2, ... , m-1} is a complete system of residues modulo m.

How do you show that say 1 is congruent to exactly one of the integers in the set?

share|improve this question
3  
The definition says every integer is congruent modulo m to exactly one integer in the set. Not that every integer in the set is congruent modulo m to exactly one other integer in the set. –  antirealist Jul 30 at 0:46

2 Answers 2

up vote 5 down vote accepted

Example. Let $$ S=\{27,32,37,42\} $$ and note that \begin{align*} 27\equiv 3\pmod4 && 32\equiv 0\pmod4 && 37\equiv1\pmod4 && 42\equiv2\pmod4 \end{align*} Since every integer $n$ is equivalent to $0$, $1$, $2$, or $3$ modulo $4$, this tells us that $S$ is a complete system of residues modulo $4$.

Non-Example. Let $$ T=\{17,101,122,132\} $$ and note that \begin{align*} 17\equiv 1\pmod4 && 101\equiv 1\pmod4 && 122\equiv2\pmod4 && 132\equiv0\pmod4 \end{align*} Since $11\equiv 3\pmod4$, this tells us that $T$ is not a complete system of residues modulo $4$.

Exercise. Determine if $$ U=\{28,65,189,243,1001\} $$ is a complete system of residues modulo $5$. If you post your solution in the comments, I can critique it!

share|improve this answer
    
** take '~' to mean 'congruent to' ** 28 ~ 3 (mod 5) 65 ~ 0 (mod 5) 189 ~ 4 (mod 5) 243 ~ 3 (mod 5) 1001 ~ (1 mod 5) But since 17 ~ 2 (mod 5), U is not a complete system of residues. Can we still have a complete system of residues even if theres a redundancy? For example, suppose H = {17 , 28, 65, 189, 243, 1001}. Is H a now a complete system of residues modulo 5, even though both 28 and 243 are congruent to 3 modulo 5? –  David D. Aug 3 at 3:38

Let $m \geq 1$.

A set,of which the elements are $m$ consecutive integers,is a complete system of residues $\mod m$.

Actually,the numbers $a,a+1, \dots , a+(m-1)$ are inequivalent $\mod m$.

Because,two such numbers differ by a number $k$,with $0<k<m$ and so,the difference $k$ is not divided by $m$.

share|improve this answer

Your Answer

 
discard

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.