Reduced residue system
   HOME

TheInfoList



Click Here for Items Related To - Reduced residue system
OR:
Reduced residue system on:   [Wikipedia]   [Google]   [Amazon]

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, a
subset In mathematics, set ''A'' is a subset of a set ''B'' if all elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are unequal, then ''A'' is a proper subset of ...
''R'' of the
integers An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
is called a reduced residue system modulo ''n'' if: #gcd(''r'', ''n'') = 1 for each ''r'' in ''R'', #''R'' contains φ(''n'') elements, #no two elements of ''R'' are congruent modulo ''n''. Here φ denotes
Euler's totient function In number theory, Euler's totient function counts the positive integers up to a given integer that are relatively prime to . It is written using the Greek letter phi as \varphi(n) or \phi(n), and may also be called Euler's phi function. In ...
. A reduced residue system modulo ''n'' can be formed from a complete residue system modulo ''n'' by removing all integers not
relatively prime In mathematics, two integers and are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides does not divide , and vice versa. This is equivale ...
to ''n''. For example, a complete residue system modulo 12 is . The so-called totatives 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 . The
cardinality In mathematics, the cardinality of a set is a measure of the number of elements of the set. For example, the set A = \ contains 3 elements, and therefore A has a cardinality of 3. Beginning in the late 19th century, this concept was generalized ...
of this set can be calculated with the totient function: φ(12) = 4. Some other reduced residue systems modulo 12 are: * * * *


Facts

*If is a reduced residue system modulo ''n'' with ''n'' > 2, then \sum r_i \equiv 0\!\!\!\!\mod n. *Every number in a reduced residue system modulo ''n'' is a generator for the additive
group A group is a number of persons or things that are located, gathered, or classed together. Groups of people * Cultural group, a group whose members share the same cultural identity * Ethnic group, a group whose members share the same ethnic ide ...
of integers modulo ''n''. *If is a reduced residue system modulo ''n'', and ''a'' is an integer such that gcd(''a'', ''n'') = 1, then is also a reduced residue system modulo ''n''.


See also

* Complete residue system modulo m * Multiplicative group of integers modulo n *
Congruence relation In abstract algebra, a congruence relation (or simply congruence) is an equivalence relation on an algebraic structure (such as a group, ring, or vector space) that is compatible with the structure in the sense that algebraic operations done ...
*
Euler's totient function In number theory, Euler's totient function counts the positive integers up to a given integer that are relatively prime to . It is written using the Greek letter phi as \varphi(n) or \phi(n), and may also be called Euler's phi function. In ...
*
Greatest common divisor In mathematics, the greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers ''x'', ''y'', the greatest common divisor of ''x'' and ''y'' is ...
*
Least residue system modulo m In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his bo ...
*
Modular arithmetic In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his boo ...
*
Number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and integer-valued functions. German mathematician Carl Friedrich Gauss (1777–1855) said, "Ma ...
* Residue number system


Notes


References

* * {{citation , last1=Pettofrezzo , first1=Anthony J. , last2=Byrkit , first2=Donald R. , year=1970 , title=Elements of Number Theory , publisher=
Prentice Hall Prentice Hall was an American major educational publisher owned by Savvas Learning Company. Prentice Hall publishes print and digital content for the 6–12 and higher-education market, and distributes its technical titles through the Safari ...
, location=Englewood Cliffs , lccn=71081766


External links


Residue systems
at PlanetMath

at MathWorld Modular arithmetic Elementary number theory