Loading [MathJax]/jax/output/HTML-CSS/jax.js
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

1.20: Zm and Complete Residue Systems

( \newcommand{\kernel}{\mathrm{null}\,}\)

Throughout this section we assume a fixed modulus m>0.

Definition 1.20.1

We define Zm={[a]aZ}, that is, Zm is the set of all residue classes modulo m. We call Zm the ring of integers modulo m. In the next chapter we shall show how to add and multiply residue classes. This makes Zm into a ring. See Appendix A for the definition of ring. Often we drop the ring and just call Zm the integers modulo m. From Theorem 19.4 Zm={[0],[1],,[m1]} and since no two of the residue classes [0],[1],,[m1] are equal we see that Zm has exactly m elements. By Exercise 19.4 if we choose a0[0],a1[1],,am1[m1] then [a0]=[0],[a1]=[1],,[am1]=[m1]. So we also have Zm={[a0],[a1],,[am1]}.

Example 1.20.1

If m=4 we have, for example, 8[0],5[1],6[2],11[3]. And hence: Z4={[8],[5],[6],[11]}.

Definition 1.20.2

A set of m integers {a0,a1,,am1} is called a complete residue system modulo m if Zm={[a0],[a1],,[am1]}.

Remark 1.20.1

A complete residue system modulo m is sometimes called a complete set of representatives for Zm.

Example 1.20.2

By Theorem 19.4, for m>0 {0,1,2,,m1} is a complete residue system modulo m.

Example 1.20.3

From the above discussion it is clear that for each m>0 there are infinitely many distinct complete residue systems modulo m. For example, here are some examples of complete residue systems modulo 5:

  1. {0,1,2,3,4}
  2. {0,1,2,2,1}
  3. {10,9,12,8,14}
  4. {0+5n1,1+5n2,2+5n3,3+5n4,4+5n4} where n1,n2,n3,n4,n5 may be any integers.

Definition 1.20.3

The set {0,1,,m1} is called the set of least nonnegative residues modulo m.

Theorem 1.20.1

Let m>0 be given.

  1. If m=2k, then {0,1,2,,k1,k,(k1),,2,1} is a complete residue system modulo m.
  2. If m=2k+1, then {0,1,2,,k,k,,2,1} is a complete residue system modulo m.
Proof

Proof of (1). Since if m=2k Zm={[0],[1],,[k],[k+1],,[k+i],[k+k1]}, it suffices to note that by Exercise 19.3 we have [k+i]=[k+i2k]=[k+i]=[(ki)]. So [k+1]=[(k1)],[k+2]=[(k2)],,[k+k1]=[1], as desired.

Proof of (2). In this case [k+i]=[(2k+1)+k+i]=[k+i+1]=[(ki+1)] so [k+1]=[k],[k+2]=[(k1)],,[2k]=[1], as desired.

Definition 1.20.4

The complete residue system modulo m given in Theorem 1.20.1 is called the least absolute residue system modulo m.

Remark 1.20.2

If one chooses in each residue class [a] the smallest nonnegative integer one obtains the least nonnegative residue system. If one chooses in each residue class [a] an element of smallest possible absolute value one obtains the least absolute residue system.

Exercise 1.20.1

Find both the least nonnegative residue system and the least absolute residues for each of the moduli given below. Also, in each case find a third complete residue system different from these two. m=3,m=4,m=5,m=6,m=7,m=8.


1.20: Zm and Complete Residue Systems is shared under a All Rights Reserved (used with permission) license and was authored, remixed, and/or curated by LibreTexts.

Support Center

How can we help?