Modular Arithmetic - Residue Systems

Residue Systems

Each residue class modulo n may be represented by any one of its members, although we usually represent each residue class by the smallest nonnegative integer which belongs to that class (since this is the proper remainder which results from division). Note that any two members of different residue classes modulo n are incongruent modulo n. Furthermore, every integer belongs to one and only one residue class modulo n.

The set of integers {0, 1, 2, ..., n - 1} is called the least residue system modulo n. Any set of n integers, no two of which are congruent modulo n, is called a complete residue system modulo n.

It is clear that the least residue system is a complete residue system, and that a complete residue system is simply a set containing precisely one representative of each residue class modulo n. The least residue system modulo 4 is {0, 1, 2, 3}. Some other complete residue systems modulo 4 are:

  • {1,2,3,4}
  • {13,14,15,16}
  • {-2,-1,0,1}
  • {-13,4,17,18}
  • {-5,0,6,21}
  • {27,32,37,42}

Some sets which are not complete residue systems modulo 4 are:

  • {-5,0,6,22} since 6 is congruent to 22 modulo 4.
  • {5,15} since a complete residue system modulo 4 must have exactly 4 incongruent residue classes.

Read more about this topic:  Modular Arithmetic

Famous quotes containing the words residue and/or systems:

    Every poem of value must have a residue [of language].... It cannot be exhausted because our lives are not long enough to do so. Indeed, in the greatest poetry, the residue may seem to increase as our experience increases—that is, as we become more sensitive to the particular ignitions in its language. We return to a poem not because of its symbolic [or sociological] value, but because of the waste, or subversion, or difficulty, or consolation of its provision.
    William Logan, U.S. educator. “Condition of the Individual Talent,” The Sewanee Review, p. 93, Winter 1994.

    The skylines lit up at dead of night, the air- conditioning systems cooling empty hotels in the desert and artificial light in the middle of the day all have something both demented and admirable about them. The mindless luxury of a rich civilization, and yet of a civilization perhaps as scared to see the lights go out as was the hunter in his primitive night.
    Jean Baudrillard (b. 1929)