Fact-checked by Grok 2 weeks ago

Reduced residue system

In number theory, a reduced residue system modulo n (where n > 1 is a positive integer) is a set of exactly \phi(n) integers that are pairwise incongruent modulo n and each relatively prime to n, with \phi denoting Euler's totient function; this set comprises one representative from each residue class modulo n that is coprime to n.^[1]^[2] Such systems are derived from complete residue systems modulo n (sets like \{0, 1, \dots, n-1\}) by excluding all elements not coprime to n, ensuring the remaining \phi(n) elements form the reduced set.^[2] For example, modulo 5, the complete residue system \{0, 1, 2, 3, 4\} yields the reduced system \{1, 2, 3, 4\}, since \phi(5) = 4 and all these are coprime to 5.^[2] A key property is that if S is a reduced residue system modulo n and k is coprime to n, then \{ k \cdot s \pmod{n} \mid s \in S \} is also a reduced residue system, preserving the structure under multiplication by units modulo n.^[2]^[3] Reduced residue systems underpin several foundational results in elementary number theory, notably Euler's theorem, which states that if \gcd(a, n) = 1, then a^{\phi(n)} \equiv 1 \pmod{n}; the proof relies on showing that multiplication by a permutes the elements of a reduced residue system, leading to the product of the elements equaling a^{\phi(n)} times the original product modulo n.^[3] They also facilitate solutions to linear congruences of the form ax \equiv b \pmod{n} when \gcd(a, n) = 1, via x \equiv b a^{\phi(n)-1} \pmod{n}, and play a role in analytic number theory for studying multiplicative functions and Dirichlet characters.^[3] The concept extends to more advanced structures, such as the multiplicative group of integers modulo n, where the reduced residue system provides a set of generators for the units.^[4]

Definition and Basics

Formal Definition

A reduced residue system modulo n, where n > 1 is a positive integer, is a set R consisting of \phi(n) integers such that each r \in R satisfies \gcd(r, n) = 1, and no two elements of R are congruent modulo n.^[4] Two integers are coprime if their greatest common divisor is 1, a condition that presupposes familiarity with the greatest common divisor function and basic modular arithmetic.^[5] The set R thereby represents precisely the residue classes modulo n that are coprime to n, ensuring one representative from each such class.^[2] Euler's totient function \phi(n) counts the number of integers from 1 to n that are coprime to n, which determines the cardinality of R.^[6]

Relation to Complete Residue Systems

A complete residue system modulo n consists of n integers, each congruent to a distinct value from 0 to n-1 modulo n, thereby providing exactly one representative for each of the n residue classes modulo n.^[2] The set \{0, 1, 2, \dots, n-1\} serves as the standard complete residue system modulo n.^[2] To derive a reduced residue system modulo n from a complete residue system, one removes all elements that are not coprime to n, retaining only those integers k where \gcd(k, n) = 1.^[2] This filtering process yields precisely \phi(n) elements, with \phi denoting Euler's totient function, which counts the integers up to n that are coprime to n.^[2] The resulting set forms a reduced residue system, as it represents all residue classes coprime to n.^[7] For example, with n = 12, the complete residue system \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11\} is reduced by excluding elements that are multiples of 2 or 3 (such as 0, 2, 3, 4, 6, 8, 9, and 10), leaving the set \{1, 5, 7, 11\}.^[7] This example illustrates the subset relationship, where the reduced system is a proper subset of the complete one when n > 1.^[2]

Key Properties

Cardinality and Euler's Totient Function

A reduced residue system modulo n consists of exactly \phi(n) elements, where \phi denotes Euler's totient function, corresponding to the count of integers k with $1 \leq k \leq n-1 that are coprime to n.^[8]^[1] Euler's totient function \phi(n) is defined as the number of positive integers up to n that are relatively prime to n./04%3A_Number_Theoretic_Functions/4.04%3A_New_Page) Its explicit formula is

\phi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right),

where the product runs over the distinct prime factors p of n.^[9]/01%3A_Chapters/1.02%3A_Arithmetic_Functions) To derive this formula, consider the principle of inclusion-exclusion applied to the integers from 1 to n. The total count is n, but subtract those divisible by each prime p dividing n (giving n/p for each such p), add back those divisible by products of two such primes (to correct over-subtraction), and continue alternating signs up to the full product of primes. This yields the proportion of integers not divisible by any prime factor of n, hence coprime to n, establishing a bijection between these integers and the residue classes in a reduced residue system modulo n.^[10]^[11] For prime p, \phi(p) = p - 1, as all integers from 1 to p-1 are coprime to p./04%3A_Multiplicative_Number_Theoretic_Functions/4.02%3A_Multiplicative_Number_Theoretic_Functions) For a prime power p^k, \phi(p^k) = p^k - p^{k-1}, since exactly p^{k-1} multiples of p up to p^k are excluded.^[12] Moreover, \phi is multiplicative: if \gcd(m, n) = 1, then \phi(mn) = \phi(m) \phi(n), allowing computation for general n via its prime factorization.^[12]^[13]

Multiplicative Group Isomorphism

A reduced residue system modulo n consists of integers that are coprime to n, and under the operation of multiplication modulo n, this set forms a group known as the multiplicative group of units modulo n, denoted (\mathbb{Z}/n\mathbb{Z})^\times. The closure property holds because the product of two integers coprime to n remains coprime to n, ensuring the result is also coprime to n and thus belongs to the reduced residue system.^[14] Associativity follows from the associativity of integer multiplication, and the identity element is $1 \mod n, as multiplying by 1 leaves any element unchanged modulo n.^[14] Each element r in the system has a multiplicative inverse modulo n, since \gcd(r, n) = 1 implies the existence of an integer x such that rx \equiv 1 \mod n by Bézout's identity.^[15] Any reduced residue system R modulo n is isomorphic to (\mathbb{Z}/n\mathbb{Z})^\times as groups, via the natural map that sends each representative r \in R to its congruence class r \mod n in (\mathbb{Z}/n\mathbb{Z})^\times. This map is a bijection because R contains exactly one representative from each residue class coprime to n, and it preserves the group operation since multiplication in R corresponds to multiplication in the quotient ring modulo n.^[14] The group (\mathbb{Z}/n\mathbb{Z})^\times is abelian, as multiplication modulo n is commutative.^[15] Its order equals Euler's totient function \phi(n), which counts the number of integers up to n coprime to n.^[14] When n = p is prime, (\mathbb{Z}/p\mathbb{Z})^\times is a cyclic group of order p-1, generated by a primitive root modulo p.^[16] This cyclic structure arises because the group consists of the nonzero residues modulo p, and there exists an element of order p-1 that generates the entire group under multiplication.^[14]

Constructions and Examples

Canonical Construction

The canonical reduced residue system modulo a positive integer n > 1 is the set \{ k \mid 1 \leq k < n, \gcd(k, n) = 1 \}, consisting of all positive integers less than n that are coprime to n.^[17] This set, often called the standard or principal reduced residue system, has exactly \phi(n) elements, where \phi denotes Euler's totient function.^[1] To construct this system, enumerate the integers from 1 to n-1 and retain only those k satisfying \gcd(k, n) = 1, with coprimality determined via the Euclidean algorithm applied to k and n.^[18] For instance, when n = 12, the elements coprime to 12 are 1, 5, 7, and 11, yielding the set \{1, 5, 7, 11\}.^[17] Similarly, for the prime n = 7, all integers from 1 to 6 are coprime to 7, so the set is \{1, 2, 3, 4, 5, 6\}.^[19] This construction yields the unique reduced residue system comprising the minimal positive representatives of the residue classes modulo n that are coprime to n.^[20] It arises from the complete residue system \{0, 1, \dots, n-1\} by excluding 0 and all non-coprime elements.^[17]

Alternative Systems and Permutations

While the canonical reduced residue system modulo n typically consists of the positive integers less than n that are coprime to n, alternative reduced residue systems can be obtained by multiplying each element of the canonical system by an integer a coprime to n, and then reducing modulo n. Specifically, if \{r_1, r_2, \dots, r_{\phi(n)}\} is a reduced residue system modulo n and \gcd(a, n) = 1, then \{a r_1 \mod n, a r_2 \mod n, \dots, a r_{\phi(n)} \mod n\} forms another reduced residue system modulo n.^[7] This transformation preserves both coprimality—since \gcd(a r_i, n) = 1 if \gcd(r_i, n) = 1 and \gcd(a, n) = 1—and pairwise incongruence modulo n, ensuring the set remains a complete set of representatives for the residue classes coprime to n.^[21] For example, consider n = 12, where the canonical reduced residue system is \{1, 5, 7, 11\}. Multiplying by a = 5 (coprime to 12) yields $5 \cdot 1 = 5 \mod 12, $5 \cdot 5 = 25 \equiv 1 \mod 12, $5 \cdot 7 = 35 \equiv 11 \mod 12, and $5 \cdot 11 = 55 \equiv 7 \mod 12, resulting in the set \{1, 5, 7, 11\}, which is a permutation of the original. Similarly, multiplying by a = 7 gives $7 \cdot 1 = 7 \mod 12, $7 \cdot 5 = 35 \equiv 11 \mod 12, $7 \cdot 7 = 49 \equiv 1 \mod 12, and $7 \cdot 11 = 77 \equiv 5 \mod 12, again yielding \{1, 5, 7, 11\} in permuted order.^[7] Alternative systems may also employ non-positive representatives or values exceeding n, which are congruent to the canonical elements modulo n. For instance, \{-1, -5, -7, -11\} modulo 12 is equivalent to \{11, 7, 5, 1\}, a permutation of the canonical system, since -1 \equiv 11 \mod 12, -5 \equiv 7 \mod 12, and so on. Likewise, the shifted set \{13, 17, 19, 23\} reduces to \{1, 5, 7, 11\} \mod 12. Another example is the system \{17, -5, 11, -11\} modulo 12, which simplifies to \{5, 7, 11, 1\}.^[21] These variations maintain the defining properties of a reduced residue system while illustrating the flexibility in choosing representatives.

Theoretical Implications

Sum and Product Formulas

For n > 1, the sum of the elements in the canonical reduced residue system modulo n (i.e., the positive integers up to n that are coprime to n) is given by

\sum_{\substack{1 \le k \le n \\ \gcd(k,n)=1}} k = \frac{1}{2} n \phi(n),

where \phi denotes Euler's totient function.^[22] This formula arises from the symmetry in the set: if k is coprime to n, then so is n - k, and k + (n - k) = n. For n > 2, \phi(n) is even, so the elements pair into \phi(n)/2 pairs each summing to n, yielding the total sum as \frac{\phi(n)}{2} \cdot n. Consequently, the sum is congruent to 0 modulo n for n > 2. For example, modulo 12 the reduced residues are 1, 5, 7, 11, and their sum is $1 + 5 + 7 + 11 = 24 \equiv 0 \pmod{12}, matching \frac{1}{2} \cdot 12 \cdot \phi(12) = \frac{1}{2} \cdot 12 \cdot 4 = 24.^[22] The product of the elements in the canonical reduced residue system modulo n is governed by the Gauss-Wilson theorem, a generalization of Wilson's theorem. For n \ge 2, let P(n) = \prod_{\substack{1 \le k \le n-1 \\ \gcd(k,n)=1}} k. Then

P(n) \equiv -1 \pmod{n}

if n = 2, 4, p^\alpha, or $2p^\alpha for an odd prime p and positive integer \alpha (i.e., when (\mathbb{Z}/n\mathbb{Z})^\times is cyclic), and

P(n) \equiv 1 \pmod{n}

otherwise. Wilson's theorem is the special case for prime p, where P(p) = (p-1)! \equiv -1 \pmod{p}. For example, modulo 12 (where (\mathbb{Z}/12\mathbb{Z})^\times is not cyclic), the product is $1 \cdot 5 \cdot 7 \cdot 11 = 385 \equiv 1 \pmod{12}.

Applications in Analytic Number Theory

Reduced residue systems play a fundamental role in Dirichlet's theorem on arithmetic progressions, which asserts that if a and n are positive integers with \gcd(a, n) = 1, then there are infinitely many primes in the arithmetic progression a + kn for k = 0, 1, 2, \dots. The coprime residue classes modulo n, which form a reduced residue system, precisely index these progressions where primes can occur infinitely often, as each such class a \mod n with \gcd(a, n) = 1 corresponds to a progression containing infinitely many primes. This indexing ensures that the theorem covers all viable arithmetic progressions without redundancy from non-coprime cases. In the theory of L-functions, Dirichlet characters are defined as homomorphisms from the multiplicative group (\mathbb{Z}/n\mathbb{Z})^* to the complex numbers \mathbb{C}, and these characters are evaluated on the reduced residue classes modulo n. The group structure of the reduced residue system allows for the construction of these characters, which are completely multiplicative and periodic with period n, vanishing on integers not coprime to n. For example, modulo 4, the reduced residue system is \{1, 3\}, and the non-principal Dirichlet character \chi satisfies \chi(1) = 1 and \chi(3) = -1, extended multiplicatively to all integers. The prime number theorem for arithmetic progressions extends the classical prime number theorem by showing that the primes are asymptotically equally distributed among the \phi(n) reduced residue classes modulo n, with density $1/\phi(n) in each coprime class. This result relies on the orthogonality relations of Dirichlet characters over the reduced residue system, which enable the summation over characters to isolate contributions from specific progressions and establish the asymptotic behavior via non-vanishing properties of L-functions at s=1. ^[23] ^[24] ^[25] ^[26] ^[23]

References

[1]
Reduced Residue System -- from Wolfram MathWorld
Any system of phi(n) integers, where phi(n) is the totient function, representing all the residue classes relatively prime to n is called a reduced residue ...Missing: definition | Show results with:definition
[2]
3.2: Residue Systems and Euler's φ-Function - Mathematics LibreTexts
Jul 7, 2021 · Notice that, a reduced residue system modulo m can be obtained by deleting all the elements of the complete residue system set that are not ...
[3]
[PDF] Introduction to Analytic Number Theory
Definition. By a reduced residue system modulo m we mean any set of ϕ(m) integers, incongruent modulo m, each of which is relatively prime to m. Theorem. If {a1 ...<|control11|><|separator|>
[4]
Definition: Reduced Residue System - BookOfProofs
Let m > 0 be a positive integer and let C=\{a_1,\ldots,a_m\} a complete residue system modulo m. We call R a reduced residue system modulo m, if R is a subset R ...
[5]
https://bookofproofs.github.io/branches/number-theory/coprime-numbers.html
[6]
https://bookofproofs.github.io/branches/number-theory/euler-function.html
[7]
[PDF] 3.4 Reduced Residue Systems and Euler's φ Function
Definition 3.4.4. For each integer n. 1 let (n) denote the number of elements in a reduced residue system (mod n).
[8]
residue systems - PlanetMath
Mar 22, 2013 · One may speak also of a reduced residue system modulo m m , which contains only one representant from each prime residue class modulo m m . Such ...Missing: theory | Show results with:theory
[9]
Cardinality of Reduced Residue System - ProofWiki
Feb 9, 2024 · Theorem. Let n≥2. Let Z′n be the reduced residue system modulo n. Then: |Z′n|=ϕ(n). where ϕ(n) is the Euler phi function.
[10]
Euler phi function - PlanetMath
Mar 22, 2013 · φ φ for all positive integers: φ(n) φ ⁢ ( n ), =n∏p|n(1−1p). = n ⁢ ∏ p | n ( 1 - 1 p ) . (1). For example,. φ(2000) φ ⁢ ( 2000 ), =2000∏p|2000(1 ...Missing: formula | Show results with:formula
[11]
[PDF] Class 17 Principle of Inclusion-Exclusion Euler's Function
Euler's Function φ(n). Let φ(n) be the number of positive integers x ≤ n which are mutually prime to n i.e. have no common factors with n, other than 1. φ(12) ...
[12]
[PDF] 6.6. The Inclusion-Exclusion Principle and Euler's Function
Feb 27, 2022 · That is, the first term includes all elements (but includes some multiple times), the second term then excludes the elements that were counted ...
[13]
[PDF] 4 Euler's Totient Function
Euler's function φ is multiplicative: gcd(m, n) = 1 =⇒ φ(mn) = φ(m)φ(n). There are many simpler examples of multiplicative functions, for instance f(x) = 1 ...
[14]
3.8 The Euler Phi Function
1 ϕ(n) is the number of non-negative integers less than n that are relatively prime to n. · 2 You can verify readily that ϕ(2)=1, ϕ(4)=2, ϕ(12)=4 and ϕ(15)=8. · 3 ...
[15]
None
### Summary of Multiplicative Group Modulo n from the Document
[16]
[PDF] MULTIPLICATIVE GROUPS IN Zm 1. Abstract Our goal will be to find ...
Every finite. Abelian group is isomorphic to a direct product of cyclic groups of prime-power order. Moreover, the factorization is unique except for ...Missing: residue system
[17]
Modulo Multiplication Group -- from Wolfram MathWorld
A modulo multiplication group is a finite group M_m of residue classes prime to m under multiplication mod m. M_m is Abelian of group order phi(m), where phi(m ...Missing: system | Show results with:system
[18]
https://personal.science.psu.edu/rcv4/CENT.pdf
[19]
[PDF] A Course of Elementary Number Theory - Penn State
If n = pk, then the number of reduced residue classes modulo pk is ... for any reduced system of residues modulo m. 8. The numbers Fn = 22n. + 1 for ...
[20]
[PDF] number theory, 2025 - trevor d. wooley - Purdue Math
We have just shown that the congruence classes of a reduced residue system modulo m form a group under multiplication modulo m. Theorem 4.14 (Wilson's Theorem; ...
[21]
Longest arithmetic progressions in reduced residue systems
In this article, we completely determine the length of longest arithmetic progressions in the least positive reduced residue system and in all reduced residue ...
[22]
Congruences
Clearly, 𝜑(𝑛) is also the number of reduced residue classes modulo 𝑛. We can easily compute 𝜑(𝑛) from the standard form of 𝑛; we shall discuss this.
[23]
Formulæ for Sums Involving a Reduced Set of Residues Modulo n
Jan 20, 2009 · Formulæ for Sums Involving a Reduced Set of Residues Modulo n. Published online by Cambridge University Press: 20 January 2009. E. Spence ...
[24]
Chapter 5 Primes in arithmetic progressions - Kiran S. Kedlaya
We then prove the prime number theorem in arithmetic progressions, modulo some details left as exercises. ... Proof. Summing over all Dirichlet characters χ of ...
[25]
[PDF] 17 Dirichlet characters and primes in arithmetic progres- sions
Nov 10, 2015 · ... Dirichlet character of modulus 4 (and every power of 2). Theorem 17.23. Every Dirichlet character χ is induced by a primitive Dirichlet charac-.
[26]
[PDF] 1. The multiplicative structure of residue classes In elementary ...
the reduced residue classes and having period q. These are the Dirichlet characters. In the fancy language of abstract algebra we are examining the ...
[27]
[PDF] 11. Dirichlet characters
(1) q = 4. Then there are ϕ(q) = ϕ(4) = 2 Dirichlet characters mod 4. These are χ0 and χ1, where χ1(n) =... +1 if n ≡ 1 mod 4,. −1 if n ≡ 3 mod 4,.