Study guide

7.3 Modular Arithmetic, Chinese Remainder Theorem, and Euler's Totient

GRE Subject Test: Mathematics Exam

Track your progress as you read

Finished sections get a check mark.

1 Chapter 1: Single-Variable Differential Calculus

1.1 Limits, Continuity, and Epsilon-Delta Definitions 1.2 Differentiation Rules, Implicit & Inverse Differentiation 1.3 Mean Value Theorem, Rolle's Theorem, and Function Extrema 1.4 L'Hôpital's Rule, Curve Sketching, and Optimization 1.5 Functions, Graphs, Transformations, and Inverses 1.6 Trigonometric Functions, Identities, and Equations 1.7 Coordinate Geometry, Lines, Circles, and Conics 1.8 Parametric and Polar Curves

2 Chapter 2: Single-Variable Integral Calculus

2.1 Riemann Sums and the Fundamental Theorem of Calculus 2.2 Advanced Integration Techniques 2.3 Geometric Applications: Areas, Volumes, and Arc Length 2.4 Improper Integrals and Convergence Criteria

3 Chapter 3: Sequences, Infinite Series & Power Series

3.1 Sequences, Monotonicity, and Limits 3.2 Infinite Series and Convergence Tests 3.3 Power Series, Radius and Interval of Convergence 3.4 Taylor and Maclaurin Series with Error Bounds

4 Chapter 4: Multivariable Differential Calculus

4.1 Multivariable Functions, Limits, and Partial Derivatives 4.2 Directional Derivatives, Gradients, and Tangent Planes 4.3 Multivariable Chain Rule and Implicit Differentiation 4.4 Multivariable Extrema, Hessian Matrix, and Lagrange Multipliers

5 Chapter 5: Multivariable Integration & Vector Calculus

5.1 Multiple Integrals in Cylindrical and Spherical Coordinates 5.2 Change of Variables and the Jacobian Determinant 5.3 Vector Fields, Line Integrals, and Green's Theorem 5.4 Surface Integrals, Stokes' Theorem, and the Divergence Theorem

6 Chapter 6: Ordinary Differential Equations

6.1 First-Order ODEs: Separable, Linear, and Exact Equations 6.2 Special First-Order ODEs: Homogeneous, Bernoulli, and Orthogonal Trajectories 6.3 Second-Order Linear Homogeneous ODEs with Constant Coefficients 6.4 Nonhomogeneous Linear ODEs: Undetermined Coefficients and Variation of Parameters

7 Chapter 7: Elementary Algebra & Number Theory

7.1 Elementary Algebra, Polynomials, Roots, and Factorization 7.2 Divisibility, Primes, and the Euclidean Algorithm 7.3 Modular Arithmetic, Chinese Remainder Theorem, and Euler's Totient

8 Chapter 8: Linear Algebra: Vector Spaces & Transformations

8.1 Vector Spaces, Subspaces, Span, and Linear Independence 8.2 Basis, Dimension, and Coordinate Representations 8.3 Linear Transformations, Kernel, Range, and the Rank-Nullity Theorem 8.4 Matrix Representations of Transformations and Change of Basis

9 Chapter 9: Linear Algebra: Matrices, Determinants & Spectral Theory

9.1 Systems of Linear Equations, Matrix Rank, and Row Reduction 9.2 Determinants, Matrix Inverses, and Cramer's Rule 9.3 Eigenvalues, Eigenvectors, and Diagonalization 9.4 Inner Product Spaces, Gram-Schmidt, and the Spectral Theorem

10 Chapter 10: Abstract Algebra: Groups, Rings & Fields

10.1 Groups, Subgroups, and Permutations 10.2 Cosets, Lagrange's Theorem, Normal Subgroups, and Homomorphisms 10.3 Rings, Ideals, Modules, Polynomial Rings, and Fields

11 Chapter 11: Introductory Real Analysis

11.1 The Real Field and Metric Space Topology 11.2 Compactness, Completeness, and Connectedness in R^n 11.3 Continuity, Uniform Continuity, and Value Theorems 11.4 Sequences and Series of Functions: Pointwise and Uniform Convergence

12 Chapter 12: Complex Analysis

12.1 Complex Numbers and Analytic Functions 12.2 Contour Integration and Cauchy's Theorems 12.3 Laurent Series, Singularities, and the Residue Theorem

13 Chapter 13: Topology, Geometry & Numerical Analysis

13.1 Topological Spaces, Open/Closed Sets, and Bases 13.2 Euclidean Geometry, Similarity, Circles, and Transformations 13.3 Numerical Analysis: Error, Root Finding, Interpolation, and Quadrature

14 Chapter 14: Probability, Statistics & Discrete Mathematics

14.1 Logic, Set Theory, Algorithms, and Combinatorics 14.2 Graph Theory: Trees, Cycles, Paths, and Planarity 14.3 Probability Spaces, Conditional Probability, and Bayes' Theorem 14.4 Random Variables, Expected Value, Variance, and Common Distributions

7.3 Modular Arithmetic, Chinese Remainder Theorem, and Euler's Totient

Key Takeaways Explain This Topic AI

A modular multiplicative inverse a^{-1} mod m exists if and only if gcd(a, m) = 1, making Z/mZ a field if and only if m is prime.

A linear congruence ax = b (mod m) has solutions if and only if d = gcd(a, m) divides b, producing exactly d incongruent solutions modulo m.

The Chinese Remainder Theorem guarantees a unique solution modulo the product of pairwise coprime moduli, establishing a fundamental ring isomorphism between modular systems.

Euler's Totient Theorem generalizes Fermat's Little Theorem to composite moduli via phi(n) = n * prod_{p|n} (1 - 1/p), enabling exponential reductions alongside Wilson's factorial theorem.

Last updated: September 2026

7.3 Modular Arithmetic, Chinese Remainder Theorem, and Euler's Totient

Modular arithmetic on the GRE tests congruences, inverses, Euler's and Fermat's theorems, and the Chinese Remainder Theorem. Rapid reduction of powers and modular inverses is critical.

Congruence Relations and Modular Fundamentals

For m ∈ Z + m \in \mathbb{Z}^+ m ∈ Z + , integers a , b a, b a , b are congruent modulo m m m , written a ≡ b ( m o d m ) a \equiv b \pmod m a ≡ b ( mod m ) , if m ∣ ( a − b ) m \mid (a - b) m ∣ ( a − b ) . This partitions Z \mathbb{Z} Z into residue classes { 0 , 1 , … , m − 1 } \{0, 1, \dots, m-1\} { 0 , 1 , … , m − 1 } .

Ring Operations: If a ≡ b ( m o d m ) a \equiv b \pmod m a ≡ b ( mod m ) and c ≡ d ( m o d m ) c \equiv d \pmod m c ≡ d ( mod m ) , then a ± c ≡ b ± d ( m o d m ) a \pm c \equiv b \pm d \pmod m a ± c ≡ b ± d ( mod m ) and a c ≡ b d ( m o d m ) ac \equiv bd \pmod m a c ≡ b d ( mod m ) .

Cancellation Rule: a c ≡ b c ( m o d m ) ⟺ a ≡ b ( m o d m gcd ⁡ ( c , m ) ) ac \equiv bc \pmod m \iff a \equiv b \pmod{\frac{m}{\gcd(c, m)}} a c ≡ b c ( mod m ) ⟺ a ≡ b ( mod g cd ( c , m ) m ​ ) If gcd ⁡ ( c , m ) = 1 \gcd(c, m) = 1 g cd ( c , m ) = 1 , a c ≡ b c ( m o d m ) ⟹ a ≡ b ( m o d m ) ac \equiv bc \pmod m \implies a \equiv b \pmod m a c ≡ b c ( mod m ) ⟹ a ≡ b ( mod m ) .

Modular Inverses and Linear Congruences

A multiplicative inverse a − 1 ( m o d m ) a^{-1} \pmod m a − 1 ( mod m ) satisfies a x ≡ 1 ( m o d m ) ax \equiv 1 \pmod m a x ≡ 1 ( mod m ) .

Existence: a − 1 ( m o d m ) a^{-1} \pmod m a − 1 ( mod m ) exists and is unique modulo m m m if and only if gcd ⁡ ( a , m ) = 1 \gcd(a, m) = 1 g cd ( a , m ) = 1 . The ring Z / m Z \mathbb{Z}/m\mathbb{Z} Z / m Z is a field F p \mathbb{F}_p F p ​ if and only if m m m is prime p p p .

Solving Linear Congruences

For a x ≡ b ( m o d m ) ax \equiv b \pmod m a x ≡ b ( mod m ) :

Let d = gcd ⁡ ( a , m ) d = \gcd(a, m) d = g cd ( a , m ) . Solutions exist if and only if d ∣ b d \mid b d ∣ b .

If d ∣ b d \mid b d ∣ b , there are exactly d d d incongruent solutions modulo m m m .

Divide through by d d d : a d x ≡ b d ( m o d m d ) \frac{a}{d}x \equiv \frac{b}{d} \pmod{\frac{m}{d}} d a ​ x ≡ d b ​ ( mod d m ​ ) and invert a d \frac{a}{d} d a ​ modulo m d \frac{m}{d} d m ​ to find base solution x 0 x_0 x 0 ​ .

The complete set of solutions is: x ≡ x 0 + k ( m d ) ( m o d m ) for k = 0 , 1 , … , d − 1 x \equiv x_0 + k\left(\frac{m}{d}\right) \pmod m \quad \text{for } k = 0, 1, \dots, d-1 x ≡ x 0 ​ + k ( d m ​ ) ( mod m ) for k = 0 , 1 , … , d − 1

The Chinese Remainder Theorem (CRT)

Let m 1 , … , m k m_1, \dots, m_k m 1 ​ , … , m k ​ be pairwise coprime positive integers ( gcd ⁡ ( m i , m j ) = 1 \gcd(m_i, m_j) = 1 g cd ( m i ​ , m j ​ ) = 1 for i ≠ j i \neq j i  = j ). The system x ≡ a i ( m o d m i ) x \equiv a_i \pmod{m_i} x ≡ a i ​ ( mod m i ​ ) ( i = 1 , … , k i = 1, \dots, k i = 1 , … , k ) has a unique solution modulo M = ∏ i = 1 k m i M = \prod_{i=1}^k m_i M = ∏ i = 1 k ​ m i ​ .

Algorithm

Compute M = ∏ m i M = \prod m_i M = ∏ m i ​ and M i = M / m i M_i = M/m_i M i ​ = M / m i ​ .

Invert: y i ≡ M i − 1 ( m o d m i ) y_i \equiv M_i^{-1} \pmod{m_i} y i ​ ≡ M i − 1 ​ ( mod m i ​ ) .

Solution: x ≡ ∑ i = 1 k a i M i y i ( m o d M ) x \equiv \sum_{i=1}^k a_i M_i y_i \pmod M x ≡ ∑ i = 1 k ​ a i ​ M i ​ y i ​ ( mod M ) .

CRT provides the ring isomorphism Z / M Z ≅ ∏ i = 1 k Z / m i Z \mathbb{Z}/M\mathbb{Z} \cong \prod_{i=1}^k \mathbb{Z}/m_i\mathbb{Z} Z / M Z ≅ ∏ i = 1 k ​ Z / m i ​ Z .

  • Fermat's Little Theorem and Euler's Totient Function
  • Fermat's Little Theorem (FLT)

If p p p is prime and p ∤ a p \nmid a p ∤ a , then: a p − 1 ≡ 1 ( m o d p ) and a p ≡ a ( m o d p ) for all a a^{p-1} \equiv 1 \pmod p \quad \text{and} \quad a^p \equiv a \pmod p \text{ for all } a a p − 1 ≡ 1 ( mod p ) and a p ≡ a ( mod p ) for all a

Euler's Totient Function ϕ ( n ) \phi(n) ϕ ( n )

ϕ ( n ) \phi(n) ϕ ( n ) counts integers 1 ≤ k ≤ n 1 \le k \le n 1 ≤ k ≤ n coprime to n n n . For n = ∏ p i a i n = \prod p_i^{a_i} n = ∏ p i a i ​ ​ : ϕ ( n ) = n ∏ p ∣ n ( 1 − 1 p ) = ∏ i = 1 k p i a i − 1 ( p i − 1 ) \phi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right) = \prod_{i=1}^k p_i^{a_i - 1}(p_i - 1) ϕ ( n ) = n p ∣ n ∏ ​ ( 1 − p 1 ​ ) = i = 1 ∏ k ​ p i a i ​ − 1 ​ ( p i ​ − 1 )

Multiplicativity: gcd ⁡ ( m , n ) = 1 ⟹ ϕ ( m n ) = ϕ ( m ) ϕ ( n ) \gcd(m, n) = 1 \implies \phi(mn) = \phi(m)\phi(n) g cd ( m , n ) = 1 ⟹ ϕ ( mn ) = ϕ ( m ) ϕ ( n ) .

Gauss Identity: ∑ d ∣ n ϕ ( d ) = n \sum_{d \mid n} \phi(d) = n ∑ d ∣ n ​ ϕ ( d ) = n .

Euler's Totient Theorem

If gcd ⁡ ( a , n ) = 1 \gcd(a, n) = 1 g cd ( a , n ) = 1 , then a ϕ ( n ) ≡ 1 ( m o d n ) a^{\phi(n)} \equiv 1 \pmod n a ϕ ( n ) ≡ 1 ( mod n ) .

  • Wilson's Theorem and Fast Exponentiation
  • Wilson's Theorem

An integer p > 1 p > 1 p > 1 is prime if and only if: ( p − 1 ) ! ≡ − 1 ( m o d p ) (p - 1)! \equiv -1 \pmod p ( p − 1 )! ≡ − 1 ( mod p )

For primes p > 2 p > 2 p > 2 , key corollaries include ( p − 2 ) ! ≡ 1 ( m o d p ) (p - 2)! \equiv 1 \pmod p ( p − 2 )! ≡ 1 ( mod p ) and ( p − 3 ) ! ≡ p − 1 2 ( m o d p ) (p - 3)! \equiv \frac{p-1}{2} \pmod p ( p − 3 )! ≡ 2 p − 1 ​ ( mod p ) .

Successive Squaring

Compute a b m o d m a^b \bmod m a b mod m in O ( log ⁡ b ) O(\log b) O ( lo g b ) operations by writing b = ∑ c j 2 j b = \sum c_j 2^j b = ∑ c j ​ 2 j in binary and multiplying powers a 2 j a^{2^j} a 2 j computed via repeated modular squaring.

Summary Table: Modular Arithmetic Theorems

Theorem Hypotheses Fundamental Identity Application

Fermat's Little p p p prime, p ∤ a p \nmid a p ∤ a a p − 1 ≡ 1 ( m o d p ) a^{p-1} \equiv 1 \pmod p a p − 1 ≡ 1 ( mod p ) Exponent reduction mod prime

Euler's Totient gcd ⁡ ( a , n ) = 1 \gcd(a, n) = 1 g cd ( a , n ) = 1 a ϕ ( n ) ≡ 1 ( m o d n ) a^{\phi(n)} \equiv 1 \pmod n a ϕ ( n ) ≡ 1 ( mod n ) Exponent reduction mod composite

Wilson's p p p prime ( p − 1 ) ! ≡ − 1 ( m o d p ) (p - 1)! \equiv -1 \pmod p ( p − 1 )! ≡ − 1 ( mod p ) Factorial evaluation mod prime

Chinese Remainder gcd ⁡ ( m i , m j ) = 1 \gcd(m_i, m_j) = 1 g cd ( m i ​ , m j ​ ) = 1 Unique solution mod ∏ m i \prod m_i ∏ m i ​ Simultaneous congruence systems

Step-by-Step Worked Problem

Problem: Find the remainder when 3 102 3^{102} 3 102 is divided by 70 70 70 .

Solution:

Factor modulus: 70 = 2 × 5 × 7 70 = 2 \times 5 \times 7 70 = 2 × 5 × 7 . Moduli are pairwise coprime.

Compute modulo each factor:

Modulo 2: 3 ≡ 1 ( m o d 2 ) ⟹ 3 102 ≡ 1 ( m o d 2 ) 3 \equiv 1 \pmod 2 \implies 3^{102} \equiv 1 \pmod 2 3 ≡ 1 ( mod 2 ) ⟹ 3 102 ≡ 1 ( mod 2 ) .

Modulo 5: By FLT, 3 4 ≡ 1 ( m o d 5 ) 3^4 \equiv 1 \pmod 5 3 4 ≡ 1 ( mod 5 ) . Since 102 = 4 ( 25 ) + 2 102 = 4(25) + 2 102 = 4 ( 25 ) + 2 : 3 102 ≡ ( 3 4 ) 25 ⋅ 3 2 ≡ 1 ⋅ 9 ≡ 4 ( m o d 5 ) 3^{102} \equiv (3^4)^{25} \cdot 3^2 \equiv 1 \cdot 9 \equiv 4 \pmod 5 3 102 ≡ ( 3 4 ) 25 ⋅ 3 2 ≡ 1 ⋅ 9 ≡ 4 ( mod 5 )

Modulo 7: By FLT, 3 6 ≡ 1 ( m o d 7 ) 3^6 \equiv 1 \pmod 7 3 6 ≡ 1 ( mod 7 ) . Since 102 = 6 ( 17 ) 102 = 6(17) 102 = 6 ( 17 ) : 3 102 ≡ ( 3 6 ) 17 ≡ 1 ( m o d 7 ) 3^{102} \equiv (3^6)^{17} \equiv 1 \pmod 7 3 102 ≡ ( 3 6 ) 17 ≡ 1 ( mod 7 )

Combine using CRT:

x ≡ 1 ( m o d 2 ) x \equiv 1 \pmod 2 x ≡ 1 ( mod 2 ) and x ≡ 1 ( m o d 7 ) ⟹ x ≡ 1 ( m o d 14 ) x \equiv 1 \pmod 7 \implies x \equiv 1 \pmod{14} x ≡ 1 ( mod 7 ) ⟹ x ≡ 1 ( mod 14 ) . Thus x = 14 k + 1 x = 14k + 1 x = 14 k + 1 .

Modulo 5: 14 k + 1 ≡ 4 ( m o d 5 ) ⟹ 4 k ≡ 3 ⟹ − k ≡ 3 ⟹ k ≡ 2 ( m o d 5 ) 14k + 1 \equiv 4 \pmod 5 \implies 4k \equiv 3 \implies -k \equiv 3 \implies k \equiv 2 \pmod 5 14 k + 1 ≡ 4 ( mod 5 ) ⟹ 4 k ≡ 3 ⟹ − k ≡ 3 ⟹ k ≡ 2 ( mod 5 ) .

Smallest positive value ( k = 2 k = 2 k = 2 ): x = 14 ( 2 ) + 1 = 29 x = 14(2) + 1 = 29 x = 14 ( 2 ) + 1 = 29 .

Check: 29 ≡ 1 ( m o d 2 ) 29 \equiv 1 \pmod 2 29 ≡ 1 ( mod 2 ) , 29 ≡ 4 ( m o d 5 ) 29 \equiv 4 \pmod 5 29 ≡ 4 ( mod 5 ) , 29 ≡ 1 ( m o d 7 ) 29 \equiv 1 \pmod 7 29 ≡ 1 ( mod 7 ) . Remainder is 29 29 29 .

GRE Exam Traps & Pitfalls

Trap 1: Cancelling Factors Without Modifying Modulus 4 x ≡ 4 y ( m o d 6 ) 4x \equiv 4y \pmod 6 4 x ≡ 4 y ( mod 6 ) implies x ≡ y ( m o d 3 ) x \equiv y \pmod 3 x ≡ y ( mod 3 ) , NOT modulo 6. Dividing requires dividing the modulus by gcd ⁡ ( c , m ) \gcd(c, m) g cd ( c , m ) .

Trap 2: Invoking Euler's Theorem When gcd ⁡ ( a , n ) > 1 \gcd(a, n) > 1 g cd ( a , n ) > 1 Euler's theorem requires gcd ⁡ ( a , n ) = 1 \gcd(a, n) = 1 g cd ( a , n ) = 1 . If non-coprime, factor into prime powers and apply CRT.

Trap 3: Applying Standard CRT to Non-Coprime Moduli Moduli must be pairwise coprime. For non-coprime moduli, decompose into prime-power congruences and verify consistency.

Trap 4: Missing Incongruent Solutions If d = gcd ⁡ ( a , m ) > 1 d = \gcd(a, m) > 1 d = g cd ( a , m ) > 1 divides b b b , a x ≡ b ( m o d m ) ax \equiv b \pmod m a x ≡ b ( mod m ) has exactly d d d distinct solutions modulo m m m , not just 1.

Loading diagram... Modular Exponentiation and Congruence Strategy