HOME

TheInfoList




In
mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and their changes (cal ...
, a
subset In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities a ...

subset
''R'' of the
integers An integer (from the Latin Latin (, or , ) is a classical language belonging to the Italic languages, Italic branch of the Indo-European languages. Latin was originally spoken in the area around Rome, known as Latium. Through the power ...

integers
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 Congruence may refer to: Mathematics * Congruence (geometry), being the same size and shape * Congruence or congruence relation, in abstract algebra, an equivalence relation on an algebraic structure that is compatible with the structure * In modu ...

congruent
modulo ''n''. Here φ denotes
Euler's totient function In number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of devoted primarily to the study of the s and . German mathematician (1777–1855) said, "Mathematics is the queen of the sciences—and numbe ...
. A reduced residue system modulo ''n'' can be formed from a complete residue system modulo ''n'' by removing all integers not
relatively prime In number theory, two integer An integer (from the Latin wikt:integer#Latin, ''integer'' meaning "whole") is colloquially defined as a number that can be written without a Fraction (mathematics), fractional component. For example, 21, 4, 0, ...
to ''n''. For example, a complete residue system modulo 12 is . The so-called
totative In number theory, a totative of a given positive integer is an integer such that and is coprime to . Euler's totient function φ(''n'') counts the number of totatives of ''n''. The totatives under multiplication modulo ''n'' form the Mult ...
s 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 Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
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 A number is a mathematical object used to counting, count, measurement, measure, and nominal number, label. The original examples are the natural numbers 1, 2, 3, 4, and so forth. Numbers can be represented in language with ...
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 *
Congruence relation In abstract algebra, a congruence relation (or simply congruence) is an equivalence relation on an algebraic structure (such as a group (mathematics), group, ring (mathematics), ring, or vector space) that is compatible with the structure in the ...
*
Euler's totient function In number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of devoted primarily to the study of the s and . German mathematician (1777–1855) said, "Mathematics is the queen of the sciences—and numbe ...
*
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 ...

Greatest common divisor
* Least residue system modulo m *
Modular arithmetic #REDIRECT Modular arithmetic #REDIRECT Modular arithmetic#REDIRECT Modular arithmetic In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure ( ...
*
Number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of devoted primarily to the study of the s and . German mathematician (1777–1855) said, "Mathematics is the queen of the sciences—and number theory is the queen ...

Number theory
* 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 is 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. Prentice Hall distributes its technical titles through th ...
, location=Englewood Cliffs , lccn=71081766


External links


Residue systems
at PlanetMath

at MathWorld Modular arithmetic Elementary number theory