Study guide
7.2 Divisibility, Primes, and the Euclidean Algorithm
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.2 Divisibility, Primes, and the Euclidean Algorithm
Key Takeaways Explain This Topic AI
The Division Algorithm guarantees unique quotient and remainder integers a = bq + r with 0 <= r < b, establishing the Euclidean structure of the integers.
The Euclidean algorithm efficiently computes gcd(a, b), while the Extended Euclidean algorithm determines Bézout coefficients satisfying ax + by = gcd(a, b).
A linear Diophantine equation ax + by = c has integer solutions if and only if gcd(a, b) divides c, generating an infinite family of solutions stepped by b/gcd(a,b) and -a/gcd(a,b).
The Fundamental Theorem of Arithmetic guarantees unique prime factorization, yielding the duality identity gcd(a, b) * lcm(a, b) = |ab|, while the Prime Number Theorem establishes that the prime-counting function satisfies pi(x) ~ x / ln(x).
Last updated: September 2026
7.2 Divisibility, Primes, and the Euclidean Algorithm
Divisibility on the GRE Mathematics Subject Test focuses on the Euclidean algorithm, Bézout's identity, linear Diophantine equations, and prime distribution. Mastery of greatest common divisors and Diophantine solutions is vital for speed.
Divisibility and the Division Algorithm in Z \mathbb{Z} Z
For integers a , b ∈ Z a, b \in \mathbb{Z} a , b ∈ Z ( a ≠ 0 a \neq 0 a = 0 ), a a a divides b b b ( a ∣ b a \mid b a ∣ b ) if b = a k b = ak b = ak for some k ∈ Z k \in \mathbb{Z} k ∈ Z .
Linearity: d ∣ a d \mid a d ∣ a and d ∣ b ⟹ d ∣ ( a x + b y ) d \mid b \implies d \mid (ax + by) d ∣ b ⟹ d ∣ ( a x + b y ) for all x , y ∈ Z x, y \in \mathbb{Z} x , y ∈ Z .
Transitivity: a ∣ b a \mid b a ∣ b and b ∣ c ⟹ a ∣ c b \mid c \implies a \mid c b ∣ c ⟹ a ∣ c .
Cancellation: a ∣ b ⟺ a c ∣ b c a \mid b \iff ac \mid bc a ∣ b ⟺ a c ∣ b c for c ≠ 0 c \neq 0 c = 0 .
Division Algorithm
For a , b ∈ Z a, b \in \mathbb{Z} a , b ∈ Z with b > 0 b > 0 b > 0 , there exist unique integers q , r q, r q , r such that: a = b q + r with 0 ≤ r < b a = bq + r \quad \text{with} \quad 0 \le r < b a = b q + r with 0 ≤ r < b
where r = a m o d b r = a \bmod b r = a mod b .
Primes and the Fundamental Theorem of Arithmetic
An integer p > 1 p > 1 p > 1 is prime if its only positive divisors are 1 1 1 and p p p ; otherwise it is composite .
Euclid's Lemma: If prime p ∣ a b p \mid ab p ∣ ab , then p ∣ a p \mid a p ∣ a or p ∣ b p \mid b p ∣ b .
Fundamental Theorem of Arithmetic: Every integer n > 1 n > 1 n > 1 factors uniquely into prime powers: n = ∏ i = 1 k p i a i ( a i ≥ 1 ) n = \prod_{i=1}^k p_i^{a_i} \quad (a_i \ge 1) n = i = 1 ∏ k p i a i ( a i ≥ 1 )
GCD, LCM, and Duality
The greatest common divisor gcd ( a , b ) \gcd(a, b) g cd ( a , b ) is the largest integer dividing both a a a and b b b . If gcd ( a , b ) = 1 \gcd(a, b) = 1 g cd ( a , b ) = 1 , they are coprime . The least common multiple lcm ( a , b ) \operatorname{lcm}(a, b) lcm ( a , b ) is the smallest positive integer divisible by both. gcd ( a , b ) = ∏ i p i min ( α i , β i ) , lcm ( a , b ) = ∏ i p i max ( α i , β i ) \gcd(a, b) = \prod_i p_i^{\min(\alpha_i, \beta_i)}, \qquad \operatorname{lcm}(a, b) = \prod_i p_i^{\max(\alpha_i, \beta_i)} g cd ( a , b ) = i ∏ p i m i n ( α i , β i ) , lcm ( a , b ) = i ∏ p i m a x ( α i , β i )
Because min ( α , β ) + max ( α , β ) = α + β \min(\alpha, \beta) + \max(\alpha, \beta) = \alpha + \beta min ( α , β ) + max ( α , β ) = α + β : gcd ( a , b ) ⋅ lcm ( a , b ) = ∣ a ⋅ b ∣ \gcd(a, b) \cdot \operatorname{lcm}(a, b) = |a \cdot b| g cd ( a , b ) ⋅ lcm ( a , b ) = ∣ a ⋅ b ∣
The Euclidean Algorithm and Bézout's Identity
The Euclidean algorithm computes gcd ( a , b ) \gcd(a, b) g cd ( a , b ) using gcd ( a , b ) = gcd ( b , a m o d b ) \gcd(a, b) = \gcd(b, a \bmod b) g cd ( a , b ) = g cd ( b , a mod b ) . For a > b > 0 a > b > 0 a > b > 0 , the last non-zero remainder is gcd ( a , b ) \gcd(a, b) g cd ( a , b ) .
Bézout's Identity
Non-zero a , b ∈ Z a, b \in \mathbb{Z} a , b ∈ Z have integers x , y x, y x , y satisfying: a x + b y = gcd ( a , b ) ax + by = \gcd(a, b) a x + b y = g cd ( a , b )
gcd ( a , b ) \gcd(a, b) g cd ( a , b ) is the minimal positive integral combination of a a a and b b b . Reversing division steps gives Bézout coefficients x , y x, y x , y .
Linear Diophantine Equations
For a x + b y = c ax + by = c a x + b y = c with a , b , c ∈ Z a, b, c \in \mathbb{Z} a , b , c ∈ Z :
Solvability: Integer solutions exist if and only if d = gcd ( a , b ) ∣ c d = \gcd(a, b) \mid c d = g cd ( a , b ) ∣ c .
Particular Solution: Scale Bézout coefficients a x 0 ′ + b y 0 ′ = d ax_0' + by_0' = d a x 0 ′ + b y 0 ′ = d by c / d c/d c / d : x 0 = x 0 ′ ( c / d ) , y 0 = y 0 ′ ( c / d ) x_0 = x_0'(c/d), \qquad y_0 = y_0'(c/d) x 0 = x 0 ′ ( c / d ) , y 0 = y 0 ′ ( c / d )
General Solution: For any integer k ∈ Z k \in \mathbb{Z} k ∈ Z : x = x 0 + ( b / d ) k , y = y 0 − ( a / d ) k x = x_0 + (b/d)k, \qquad y = y_0 - (a/d)k x = x 0 + ( b / d ) k , y = y 0 − ( a / d ) k
Distribution of Primes and the Prime Number Theorem
Let π ( x ) \pi(x) π ( x ) count primes p ≤ x p \le x p ≤ x .
Prime Number Theorem: lim x → ∞ π ( x ) x / ln x = 1 \lim_{x \to \infty} \frac{\pi(x)}{x / \ln x} = 1 lim x → ∞ x / l n x π ( x ) = 1 , written π ( x ) ∼ x ln x \pi(x) \sim \frac{x}{\ln x} π ( x ) ∼ l n x x .
Asymptotics for p n p_n p n : p n ∼ n ln n p_n \sim n \ln n p n ∼ n ln n as n → ∞ n \to \infty n → ∞ .
Bertrand's Postulate: For n > 1 n > 1 n > 1 , there exists a prime p p p with n < p < 2 n n < p < 2n n < p < 2 n .
Dirichlet's Theorem: If gcd ( a , m ) = 1 \gcd(a, m) = 1 g cd ( a , m ) = 1 , the sequence a + k m a + km a + km contains infinitely many primes.
Summary Table: Divisibility and Equations
- Concept Condition Formula / Rule
- Division Algorithm b > 0 b > 0 b > 0 a = b q + r a = bq + r a = b q + r with 0 ≤ r < b 0 \le r < b 0 ≤ r < b
GCD-LCM Duality a , b ≠ 0 a, b \neq 0 a , b = 0 gcd ( a , b ) ⋅ lcm ( a , b ) = ∣ a b ∣ \gcd(a, b) \cdot \operatorname{lcm}(a, b) = \vert ab\vert g cd ( a , b ) ⋅ lcm ( a , b ) = ∣ ab ∣
Bézout's Identity d = gcd ( a , b ) d = \gcd(a, b) d = g cd ( a , b ) a x + b y = d ax + by = d a x + b y = d solvable in Z \mathbb{Z} Z
Linear Diophantine a x + b y = c ax + by = c a x + b y = c Solvable iff d ∣ c d \mid c d ∣ c ; steps: b / d b/d b / d and − a / d -a/d − a / d
Prime Distribution x → ∞ x \to \infty x → ∞ π ( x ) ∼ x ln x \pi(x) \sim \frac{x}{\ln x} π ( x ) ∼ l n x x ; p n ∼ n ln n p_n \sim n \ln n p n ∼ n ln n
Step-by-Step Worked Problem
Problem: Find all positive integer pairs ( x , y ) (x, y) ( x , y ) satisfying 35 x + 55 y = 1000 35x + 55y = 1000 35 x + 55 y = 1000 .
Solution:
gcd ( 55 , 35 ) \gcd(55, 35) g cd ( 55 , 35 ) : 55 = 1 ( 35 ) + 20 , 35 = 1 ( 20 ) + 15 , 20 = 1 ( 15 ) + 5 , 15 = 3 ( 5 ) + 0 ⟹ d = 5 55 = 1(35) + 20, 35 = 1(20) + 15, 20 = 1(15) + 5, 15 = 3(5) + 0 \implies d = 5 55 = 1 ( 35 ) + 20 , 35 = 1 ( 20 ) + 15 , 20 = 1 ( 15 ) + 5 , 15 = 3 ( 5 ) + 0 ⟹ d = 5 .
Check solvability: 5 ∣ 1000 5 \mid 1000 5 ∣ 1000 . Divide by 5 to obtain 7 x + 11 y = 200 7x + 11y = 200 7 x + 11 y = 200 .
Bézout coefficients for 7 x + 11 y = 1 7x + 11y = 1 7 x + 11 y = 1 : 1 = 4 − 3 = 2 ( 4 ) − 7 = 2 ( 11 − 7 ) − 7 = 2 ( 11 ) − 3 ( 7 ) ⟹ 7 ( − 3 ) + 11 ( 2 ) = 1 1 = 4 - 3 = 2(4) - 7 = 2(11 - 7) - 7 = 2(11) - 3(7) \implies 7(-3) + 11(2) = 1 1 = 4 − 3 = 2 ( 4 ) − 7 = 2 ( 11 − 7 ) − 7 = 2 ( 11 ) − 3 ( 7 ) ⟹ 7 ( − 3 ) + 11 ( 2 ) = 1 .
Multiply by 200: x 0 = − 600 , y 0 = 400 x_0 = -600, y_0 = 400 x 0 = − 600 , y 0 = 400 .
General solution ( k ∈ Z k \in \mathbb{Z} k ∈ Z ): x = − 600 + 11 k x = -600 + 11k x = − 600 + 11 k , y = 400 − 7 k y = 400 - 7k y = 400 − 7 k .
Require x > 0 x > 0 x > 0 and y > 0 y > 0 y > 0 : 11 k > 600 ⟹ k ≥ 55 11k > 600 \implies k \ge 55 11 k > 600 ⟹ k ≥ 55 , and 7 k < 400 ⟹ k ≤ 57 7k < 400 \implies k \le 57 7 k < 400 ⟹ k ≤ 57 .
Values k ∈ { 55 , 56 , 57 } k \in \{55, 56, 57\} k ∈ { 55 , 56 , 57 } give pairs ( 5 , 15 ) (5, 15) ( 5 , 15 ) , ( 16 , 8 ) (16, 8) ( 16 , 8 ) , and ( 27 , 1 ) (27, 1) ( 27 , 1 ) .
GRE Exam Traps & Pitfalls
Trap 1: Applying GCD-LCM Duality to Three Integers gcd ( a , b ) ⋅ lcm ( a , b ) = ∣ a b ∣ \gcd(a, b) \cdot \operatorname{lcm}(a, b) = |ab| g cd ( a , b ) ⋅ lcm ( a , b ) = ∣ ab ∣ holds strictly for two integers. For three integers, gcd ( 2 , 2 , 2 ) ⋅ lcm ( 2 , 2 , 2 ) = 4 ≠ 8 \gcd(2, 2, 2) \cdot \operatorname{lcm}(2, 2, 2) = 4 \neq 8 g cd ( 2 , 2 , 2 ) ⋅ lcm ( 2 , 2 , 2 ) = 4 = 8 .
Trap 2: Sign Mismatch in Diophantine General Solutions In x = x 0 + ( b / d ) k x = x_0 + (b/d)k x = x 0 + ( b / d ) k and y = y 0 − ( a / d ) k y = y_0 - (a/d)k y = y 0 − ( a / d ) k , signs of k k k must be opposite to keep a x + b y ax + by a x + b y constant.
Trap 3: Forgetting to Divide Modulus by d d d The parameter step size in general Diophantine solutions is b / gcd ( a , b ) b/\gcd(a, b) b / g cd ( a , b ) , not b b b .
Trap 4: Conflating π ( x ) \pi(x) π ( x ) and p n p_n p n π ( x ) ∼ x / ln x \pi(x) \sim x / \ln x π ( x ) ∼ x / ln x counts primes up to x x x , whereas p n ∼ n ln n p_n \sim n \ln n p n ∼ n ln n estimates the value of the n n n -th prime.