Reduced Residue System

Any subset R of the set of integers is called a reduced residue system modulo n if

  1. gcd(r, n) = 1 for each r contained in R;
  2. R contains φ(n) elements;
  3. no two elements of R are congruent modulo n.

Here denotes Euler's totient function.

A reduced residue system modulo n can be formed from a complete residue system modulo n by removing all integers not relatively prime to n. For example, a complete residue system modulo 12 is {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}. 1, 5, 7 and 11 are the only integers in this set which are relatively prime to 12, and so the corresponding reduced residue system modulo 12 is {1,5,7,11}. Note that the cardinality of this set is . Some other reduced residue systems modulo 12 are

  • {13,17,19,23}
  • {−11,−7,−5,−1}
  • {−7,−13,13,31}
  • {35,43,53,61}

Read more about Reduced Residue System:  Facts, See Also

Famous quotes containing the words reduced, residue and/or system:

    ““Write that down,” the King said to the jury, and the jury eagerly wrote down all three dates on their slates, and then added them up, and reduced the answer to shillings and pence.”
    —Lewis Carroll [Charles Lutwidge Dodgson] (1832–1898)

    “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.

    “If mothers are to be successful in achieving their child-rearing goals, they must have the inner freedom to find their own value system and within that system to find what is acceptable to them and what is not. This means leaving behind the anxiety, but also the security, of simplistic good-bad formulations and deciding for themselves what they want to teach their children.”
    —Elaine Heffner (20th century)