Study guide
3.3 Number Theory: Prime Factorization, GCF, LCM & Divisibility Rules
TExES Mathematics 4-8 115
Track your progress as you read
Finished sections get a check mark.
1 Chapter 1: Exam Overview & Foundation
1.1 TExES 115 Exam Format, Scoring, Testing Tools & Certification Path 1.2 The Texas Essential Knowledge and Skills (TEKS) Framework & Mathematical Process Standards
2 Chapter 2: Number Systems & Quantity (Domain I)
2.1 Real and Complex Number Systems: Subsets, Closures & Representations 2.2 Place Value, Scientific Notation, Magnitude & Density Property 2.3 Properties of Real Numbers, Field Axioms & Inverse Operations
3 Chapter 3: Operations, Algorithms & Number Theory (Domain I)
3.1 Standard and Non-Standard Computational Algorithms for Rational Numbers 3.2 Laws of Exponents, Radicals, Rational Exponents & Mental Estimation 3.3 Number Theory: Prime Factorization, GCF, LCM & Divisibility Rules
4 Chapter 4: Patterns, Expressions & Algebraic Reasoning (Domain II)
4.1 Inductive Reasoning, Sequences, Arithmetic & Geometric Patterns 4.2 Algebraic Expressions, Polynomial Operations & Translating Verbal Statements 4.3 Solving Multi-Step Equations, Inequalities & Absolute Value Relations
5 Chapter 5: Linear Functions & Modeling (Domain II)
5.1 Slope, Rate of Change & Multiple Representations of Linear Functions 5.2 Linear Equation Forms (Slope-Intercept, Point-Slope, Standard) & Parallel/Perpendicular Lines 5.3 Systems of Linear Equations, Inequalities & Direct Variation Modeling
6 Chapter 6: Nonlinear Functions & Calculus Foundations (Domain II)
6.1 Quadratic Functions: Factoring, Vertex Form, Quadratic Formula & Parabolas 6.2 Exponential Growth/Decay, Inverse Variation & Rational Functions 6.3 Conceptual Foundations of Calculus: Limits, Rates of Change & Area Under Curves 6.4 Function Families & Transformations: Radical, Absolute Value, Piecewise, Logarithmic Functions and Quadratic Systems
7 Chapter 7: Measurement Systems & Trigonometric Ratios (Domain III)
7.1 Customary and Metric Systems, Conversion & Dimensional Analysis 7.2 Precision, Accuracy, Significant Figures & Measurement Error 7.3 The Pythagorean Theorem, Special Right Triangles & Right-Triangle Trigonometric Ratios
8 Chapter 8: Euclidean Geometry & Axiomatic Reasoning (Domain III)
8.1 Axiomatic Foundations: Points, Lines, Angles & Parallel Lines Cut by Transversals 8.2 Triangle Congruence Criteria (SSS, SAS, ASA, AAS, HL) & Deductive Proofs 8.3 Triangle Similarity (AA, SAS, SSS), Indirect Measurement & Scale Factors 8.4 Geometric Constructions with Compass, Straightedge & Reflection Devices
9 Chapter 9: Two- and Three-Dimensional Figures (Domain III)
9.1 Properties and Formulas for Polygons & Circles 9.2 Three-Dimensional Figures: Prisms, Pyramids, Cylinders, Cones & Spheres 9.3 Surface Area, Volume & Scale Factor Effects on Length, Area (k²), and Volume (k³)
10 Chapter 10: Transformational & Coordinate Geometry (Domain III)
10.1 Rigid Transformations: Translations, Reflections, Rotations & Symmetry 10.2 Non-Rigid Dilations, Scale Factors & Tessellations 10.3 Coordinate Geometry: Distance Formula, Midpoint Formula & Analytic Proofs 10.4 The Unit Circle, Radian Measure & Trigonometric Functions
11 Chapter 11: Data Exploration & Numerical Techniques (Domain IV)
11.1 Data Representations: Frequency Tables, Histograms, Stem-and-Leaf, Dot Plots & Box Plots 11.2 Measures of Central Tendency (Mean, Median, Mode) & Spread (Range, IQR, Standard Deviation) 11.3 Skewed Distributions, Outlier Effects & Bivariate Scatter Plots (Trend Lines & Correlation)
12 Chapter 12: Probability Theory & Statistical Inference (Domain IV)
12.1 Theoretical vs. Experimental Probability, Sample Spaces & Counting Principles (Permutations/Combinations) 12.2 Compound Events, Independent/Dependent Events & Conditional Probability 12.3 Random Sampling, Bias, Simulations, Expected Value & Population Predictions 12.4 Binomial, Geometric & Normal Distributions, Experiments and Confidence Intervals
13 Chapter 13: Mathematical Processes & Financial Literacy (Domain V)
13.1 Polya's Problem-Solving Model & Mathematical Heuristics (Visualizing, Tables, Working Backward) 13.2 Deductive Logic, Inductive Reasoning, Counterexamples & Proof by Contradiction 13.3 Multiple Representations, Cross-Disciplinary Connections & Personal Financial Literacy in TEKS
14 Chapter 14: Mathematical Learning & Student Cognition (Domain VI)
14.1 Cognitive Development in Middle School: Piaget, Vygotsky & Bruner's CPA Framework 14.2 Vertical TEKS Mathematics Progression Across Grades 4 through 8 14.3 Diagnosing and Remediating Persistent Student Mathematical Misconceptions
15 Chapter 15: Instruction, Assessment & Technology in Mathematics (Domain VI)
15.1 Planning Inquiry-Centered Math Lessons & Productive Discourse/Questioning 15.2 Effective Use of Concrete Manipulatives, Graphing Technology & Digital Tools 15.3 Formative vs. Summative Assessment, Rubrics, STAAR Context & Data-Driven Differentiation
3.3 Number Theory: Prime Factorization, GCF, LCM & Divisibility Rules
Key Takeaways Explain This Topic AI
The Fundamental Theorem of Arithmetic guarantees that every integer greater than 1 has a unique prime factorization up to the order of factors.
Divisibility tests for 3 and 9 depend on base-10 modular arithmetic, whereas rules for 2, 4, and 8 depend on place-value powers of 10.
For any two positive integers a and b, their Greatest Common Factor and Least Common Multiple satisfy the universal relationship GCF(a,b) * LCM(a,b) = a * b.
In a Venn diagram of prime factors, the intersection yields the GCF, while the union of all factors yields the LCM.
GCF models equal partitioning, cutting, or tiling without leftovers, whereas LCM models periodic synchronization and recurring cycles.
Last updated: September 2026
Prime and Composite Numbers: Structural Foundations
Number theory explores the properties of the integers ( Z \mathbb{Z} Z ), with prime numbers serving as the foundational building blocks of multiplicative arithmetic.
Definitions and Special Status of 0 and 1
A prime number is an integer p > 1 p > 1 p > 1 that has exactly two distinct positive divisors: 1 and p p p itself.
A composite number is an integer n > 1 n > 1 n > 1 that has more than two distinct positive divisors (i.e., it can be factored into n = a × b n = a \times b n = a × b where 1 < a , b < n 1 < a, b < n 1 < a , b < n ).
The Number 1: By mathematical convention, the number 1 is neither prime nor composite. It is designated as a unit (it has a multiplicative inverse in the integers, namely itself). Defining 1 as prime would break the uniqueness clause of the Fundamental Theorem of Arithmetic, because any integer could then have infinitely many prime factorizations (e.g., 12 = 2 2 × 3 = 1 × 2 2 × 3 = 1 2 × 2 2 × 3 12 = 2^2 \times 3 = 1 \times 2^2 \times 3 = 1^2 \times 2^2 \times 3 12 = 2 2 × 3 = 1 × 2 2 × 3 = 1 2 × 2 2 × 3 ).
The Number 0: The integer 0 is neither prime nor composite. Every non-zero integer divides 0 (since 0 = k × 0 0 = k \times 0 0 = k × 0 ), giving 0 infinitely many divisors.
Prime Identification and the Sieve of Eratosthenes
The Sieve of Eratosthenes is an ancient, systematic algorithm for finding all primes up to a given bound N N N :
List all natural numbers from 2 to N N N .
Identify the first unmarked number as prime (2) and cross out all its proper multiples ( 4 , 6 , 8 , … 4, 6, 8, \dots 4 , 6 , 8 , … ).
Advance to the next unmarked number (3), declare it prime, and cross out all its multiples ( 6 , 9 , 12 , … 6, 9, 12, \dots 6 , 9 , 12 , … ).
Repeat this procedure for each successive prime p p p .
The process terminates when p > N p > \sqrt{N} p > N , as all remaining unmarked numbers are guaranteed to be prime.
There are exactly 25 prime numbers less than 100 : { 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 , 43 , 47 , 53 , 59 , 61 , 67 , 71 , 73 , 79 , 83 , 89 , 97 } \{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97\} { 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 , 43 , 47 , 53 , 59 , 61 , 67 , 71 , 73 , 79 , 83 , 89 , 97 }
Note that 2 is the only even prime number; all other even integers are multiples of 2 and therefore composite.
The Primality Testing Boundary
To determine whether a specific integer N N N is prime, one only needs to test for divisibility by prime numbers p ≤ N p \le \sqrt{N} p ≤ N . Proof: If N N N is composite, it can be written as N = a × b N = a \times b N = a × b where 1 < a ≤ b < N 1 < a \le b < N 1 < a ≤ b < N . If both a > N a > \sqrt{N} a > N and b > N b > \sqrt{N} b > N , then a × b > N × N = N a \times b > \sqrt{N} \times \sqrt{N} = N a × b > N × N = N , which is a contradiction. Thus, at least one factor must satisfy a ≤ N a \le \sqrt{N} a ≤ N . If no prime less than or equal to N \sqrt{N} N divides N N N , then N N N must be prime.
For example, to test whether 173 is prime, note that 13 2 = 169 < 173 < 14 2 = 196 13^2 = 169 < 173 < 14^2 = 196 1 3 2 = 169 < 173 < 1 4 2 = 196 , so 173 ≈ 13.15 \sqrt{173} \approx 13.15 173 ≈ 13.15 . We only test primes { 2 , 3 , 5 , 7 , 11 , 13 } \{2, 3, 5, 7, 11, 13\} { 2 , 3 , 5 , 7 , 11 , 13 } :
173 173 173 is odd (not divisible by 2).
Sum of digits 1 + 7 + 3 = 11 1 + 7 + 3 = 11 1 + 7 + 3 = 11 (not divisible by 3).
Ends in 3 (not divisible by 5).
173 ÷ 7 = 24.71 173 \div 7 = 24.71 173 ÷ 7 = 24.71 (not divisible by 7).
173 ÷ 11 = 15.72 173 \div 11 = 15.72 173 ÷ 11 = 15.72 (not divisible by 11).
173 ÷ 13 = 13.30 173 \div 13 = 13.30 173 ÷ 13 = 13.30 (not divisible by 13).
Because none of these primes divide 173, 173 is prime.
The Fundamental Theorem of Arithmetic
The Fundamental Theorem of Arithmetic (Unique Factorization Theorem) states that:
Every integer n > 1 n > 1 n > 1 can be expressed uniquely as a product of prime numbers, up to the order of the factors: n = p 1 a 1 p 2 a 2 p 3 a 3 ⋯ p k a k n = p_1^{a_1} p_2^{a_2} p_3^{a_3} \cdots p_k^{a_k} n = p 1 a 1 p 2 a 2 p 3 a 3 ⋯ p k a k where each p i p_i p i is a prime number such that p 1 < p 2 < ⋯ < p k p_1 < p_2 < \dots < p_k p 1 < p 2 < ⋯ < p k , and each a i a_i a i is a positive integer.
This expression is the canonical prime factorization of n n n .
Determining the Total Number of Positive Divisors
The canonical prime factorization allows one to directly compute the total number of positive divisors d ( n ) d(n) d ( n ) without enumerating each factor. Any divisor d d d of n n n must take the form: d = p 1 b 1 p 2 b 2 ⋯ p k b k where 0 ≤ b i ≤ a i d = p_1^{b_1} p_2^{b_2} \cdots p_k^{b_k} \quad \text{where } 0 \le b_i \le a_i d = p 1 b 1 p 2 b 2 ⋯ p k b k where 0 ≤ b i ≤ a i
Because there are ( a i + 1 ) (a_i + 1) ( a i + 1 ) independent choices for each exponent b i b_i b i (ranging from 0 to a i a_i a i ), the Multiplication Principle of counting gives: d ( n ) = ( a 1 + 1 ) ( a 2 + 1 ) ( a 3 + 1 ) ⋯ ( a k + 1 ) d(n) = (a_1 + 1)(a_2 + 1)(a_3 + 1) \cdots (a_k + 1) d ( n ) = ( a 1 + 1 ) ( a 2 + 1 ) ( a 3 + 1 ) ⋯ ( a k + 1 )
For example, consider n = 360 n = 360 n = 360 : 360 = 2 3 × 3 2 × 5 1 360 = 2^3 \times 3^2 \times 5^1 360 = 2 3 × 3 2 × 5 1
The total number of positive divisors is: d ( 360 ) = ( 3 + 1 ) ( 2 + 1 ) ( 1 + 1 ) = 4 × 3 × 2 = 24 divisors d(360) = (3 + 1)(2 + 1)(1 + 1) = 4 \times 3 \times 2 = 24\text{ divisors} d ( 360 ) = ( 3 + 1 ) ( 2 + 1 ) ( 1 + 1 ) = 4 × 3 × 2 = 24 divisors
Divisibility Rules and Modular Algebraic Proofs
Divisibility tests are mental shortcuts based on our base-10 positional notation. Any integer N N N with digits d k d k − 1 … d 1 d 0 d_k d_{k-1} \dots d_1 d_0 d k d k − 1 … d 1 d 0 can be represented as a polynomial in powers of 10: N = d k 10 k + d k − 1 10 k − 1 + ⋯ + d 2 10 2 + d 1 10 + d 0 N = d_k 10^k + d_{k-1} 10^{k-1} + \dots + d_2 10^2 + d_1 10 + d_0 N = d k 1 0 k + d k − 1 1 0 k − 1 + ⋯ + d 2 1 0 2 + d 1 10 + d 0
1. Rules for 2, 5, and 10 (Last Digit Tests)
Because the base 10 = 2 × 5 10 = 2 \times 5 10 = 2 × 5 , 10 is divisible by 2, 5, and 10. Consequently, every term d j 10 j d_j 10^j d j 1 0 j for j ≥ 1 j \ge 1 j ≥ 1 is a multiple of 10 and contributes zero to the remainder modulo 2, 5, or 10: N = 10 ( d k 10 k − 1 + ⋯ + d 1 ) + d 0 ≡ d 0 ( m o d 2 , 5 , 10 ) N = 10(d_k 10^{k-1} + \dots + d_1) + d_0 \equiv d_0 \pmod{2, 5, 10} N = 10 ( d k 1 0 k − 1 + ⋯ + d 1 ) + d 0 ≡ d 0 ( mod 2 , 5 , 10 )
Divisibility by 2: The units digit d 0 d_0 d 0 must be even ( 0 , 2 , 4 , 6 , 8 0, 2, 4, 6, 8 0 , 2 , 4 , 6 , 8 ).
Divisibility by 5: The units digit d 0 d_0 d 0 must be 0 0 0 or 5 5 5 .
Divisibility by 10: The units digit d 0 d_0 d 0 must be 0 0 0 .
2. Rules for 4 and 8 (Sub-Block Tests)
Divisibility by 4: Since 10 2 = 100 = 4 × 25 10^2 = 100 = 4 \times 25 1 0 2 = 100 = 4 × 25 , all terms for j ≥ 2 j \ge 2 j ≥ 2 are divisible by 4. Thus: N = 100 ( d k 10 k − 2 + ⋯ + d 2 ) + ( 10 d 1 + d 0 ) ≡ ( 10 d 1 + d 0 ) ( m o d 4 ) N = 100(d_k 10^{k-2} + \dots + d_2) + (10 d_1 + d_0) \equiv (10 d_1 + d_0) \pmod 4 N = 100 ( d k 1 0 k − 2 + ⋯ + d 2 ) + ( 10 d 1 + d 0 ) ≡ ( 10 d 1 + d 0 ) ( mod 4 ) An integer is divisible by 4 if and only if its last two digits form a number divisible by 4 (e.g., in 73,528, 28 = 4 × 7 28 = 4 \times 7 28 = 4 × 7 , so 73,528 is divisible by 4).
Divisibility by 8: Since 10 3 = 1000 = 8 × 125 10^3 = 1000 = 8 \times 125 1 0 3 = 1000 = 8 × 125 , all terms for j ≥ 3 j \ge 3 j ≥ 3 are divisible by 8. An integer is divisible by 8 if and only if its last three digits form a number divisible by 8 (e.g., in 54,832, 832 ÷ 8 = 104 832 \div 8 = 104 832 ÷ 8 = 104 , so 54,832 is divisible by 8).
3. Rules for 3 and 9 (Sum of Digits Tests)
Notice that 10 = 9 + 1 10 = 9 + 1 10 = 9 + 1 , 100 = 99 + 1 100 = 99 + 1 100 = 99 + 1 , and generally 10 j = ( 10 j − 1 ) + 1 10^j = (10^j - 1) + 1 1 0 j = ( 1 0 j − 1 ) + 1 , where ( 10 j − 1 ) = 999 … 9 (10^j - 1) = 999\dots9 ( 1 0 j − 1 ) = 999 … 9 is divisible by 9 (and thus by 3): 10 j ≡ 1 ( m o d 9 ) and 10 j ≡ 1 ( m o d 3 ) 10^j \equiv 1 \pmod 9 \quad \text{and} \quad 10^j \equiv 1 \pmod 3 1 0 j ≡ 1 ( mod 9 ) and 1 0 j ≡ 1 ( mod 3 )
Substituting this into the base-10 polynomial expansion: N = ∑ j = 0 k d j 10 j = ∑ j = 0 k d j ( 99 … 9 + 1 ) = ∑ j = 0 k d j ( 99 … 9 ) + ∑ j = 0 k d j N = \sum_{j=0}^k d_j 10^j = \sum_{j=0}^k d_j (99\dots9 + 1) = \sum_{j=0}^k d_j (99\dots9) + \sum_{j=0}^k d_j N = j = 0 ∑ k d j 1 0 j = j = 0 ∑ k d j ( 99 … 9 + 1 ) = j = 0 ∑ k d j ( 99 … 9 ) + j = 0 ∑ k d j
Because the first sum is a multiple of 9, N N N leaves the exact same remainder as the sum of its digits: N ≡ ∑ j = 0 k d j ( m o d 9 ) and N ≡ ∑ j = 0 k d j ( m o d 3 ) N \equiv \sum_{j=0}^k d_j \pmod 9 \quad \text{and} \quad N \equiv \sum_{j=0}^k d_j \pmod 3 N ≡ j = 0 ∑ k d j ( mod 9 ) and N ≡ j = 0 ∑ k d j ( mod 3 )
Rule for 3: An integer is divisible by 3 if the sum of its digits is divisible by 3.
Rule for 9: An integer is divisible by 9 if the sum of its digits is divisible by 9.
4. Rule for 6 (Composite Divisibility)
Because 6 = 2 × 3 6 = 2 \times 3 6 = 2 × 3 and gcd ( 2 , 3 ) = 1 \gcd(2, 3) = 1 g cd ( 2 , 3 ) = 1 , an integer is divisible by 6 if and only if it is divisible by both 2 and 3 simultaneously. Thus, the number must be even and the sum of its digits must be a multiple of 3 .
5. Rule for 11 (Alternating Sum of Digits)
Notice that 10 = 11 − 1 ≡ − 1 ( m o d 11 ) 10 = 11 - 1 \equiv -1 \pmod{11} 10 = 11 − 1 ≡ − 1 ( mod 11 ) . Therefore, powers of 10 alternate signs modulo 11: 10 0 ≡ 1 , 10 1 ≡ − 1 , 10 2 ≡ 1 , 10 3 ≡ − 1 , … , 10 j ≡ ( − 1 ) j ( m o d 11 ) 10^0 \equiv 1, \quad 10^1 \equiv -1, \quad 10^2 \equiv 1, \quad 10^3 \equiv -1, \quad \dots, \quad 10^j \equiv (-1)^j \pmod{11} 1 0 0 ≡ 1 , 1 0 1 ≡ − 1 , 1 0 2 ≡ 1 , 1 0 3 ≡ − 1 , … , 1 0 j ≡ ( − 1 ) j ( mod 11 )
Substituting into the expansion yields: N ≡ d 0 − d 1 + d 2 − d 3 + d 4 − … ( m o d 11 ) N \equiv d_0 - d_1 + d_2 - d_3 + d_4 - \dots \pmod{11} N ≡ d 0 − d 1 + d 2 − d 3 + d 4 − … ( mod 11 )
An integer is divisible by 11 if and only if the alternating sum of its digits (starting with the units digit as positive) is a multiple of 11 (including 0). For example, test 85 , 976 85,976 85 , 976 : 6 − 7 + 9 − 5 + 8 = 11 6 - 7 + 9 - 5 + 8 = 11 6 − 7 + 9 − 5 + 8 = 11
Since 11 is divisible by 11, 85 , 976 85,976 85 , 976 is divisible by 11 ( 85 , 976 = 11 × 7 , 816 85,976 = 11 \times 7,816 85 , 976 = 11 × 7 , 816 ).
6. Rule for 7 (Truncation and Doubling)
To test an integer N = 10 a + b N = 10a + b N = 10 a + b (where b b b is the last digit and a a a is the truncated prefix), subtract twice the last digit from the prefix: a − 2 b a - 2b a − 2 b . Proof: Consider the linear combination: 10 ( a − 2 b ) = 10 a − 20 b = ( 10 a + b ) − 21 b = N − 21 b 10(a - 2b) = 10a - 20b = (10a + b) - 21b = N - 21b 10 ( a − 2 b ) = 10 a − 20 b = ( 10 a + b ) − 21 b = N − 21 b
Because 21 b 21b 21 b is a multiple of 7, 10 ( a − 2 b ) ≡ N ( m o d 7 ) 10(a - 2b) \equiv N \pmod 7 10 ( a − 2 b ) ≡ N ( mod 7 ) . Because gcd ( 10 , 7 ) = 1 \gcd(10, 7) = 1 g cd ( 10 , 7 ) = 1 , N N N is divisible by 7 if and only if a − 2 b a - 2b a − 2 b is divisible by 7.
For example, test 2,464:
Prefix 246, last digit 4: 246 − 2 ( 4 ) = 246 − 8 = 238 246 - 2(4) = 246 - 8 = 238 246 − 2 ( 4 ) = 246 − 8 = 238 .
Repeat for 238: Prefix 23, last digit 8: 23 − 2 ( 8 ) = 23 − 16 = 7 23 - 2(8) = 23 - 16 = 7 23 − 2 ( 8 ) = 23 − 16 = 7 .
Since 7 is divisible by 7, 2,464 is divisible by 7 ( 2 , 464 = 7 × 352 2,464 = 7 \times 352 2 , 464 = 7 × 352 ).
Reference Table: Divisibility Rules
Divisor Test Criterion Mathematical Justification Application Example
2 Last digit is 0 , 2 , 4 , 6 , 0, 2, 4, 6, 0 , 2 , 4 , 6 , or 8 8 8 10 ≡ 0 ( m o d 2 ) 10 \equiv 0 \pmod 2 10 ≡ 0 ( mod 2 ) ; only units digit affects parity 4 , 836 4,836 4 , 836 : ends in 6 (divisible)
3 Sum of digits is divisible by 3 10 k ≡ 1 ( m o d 3 ) 10^k \equiv 1 \pmod 3 1 0 k ≡ 1 ( mod 3 ) ; each place value contributes face value 1 , 572 1,572 1 , 572 : 1 + 5 + 7 + 2 = 15 = 3 × 5 1+5+7+2 = 15 = 3 \times 5 1 + 5 + 7 + 2 = 15 = 3 × 5 (divisible)
4 Last two digits form a number divisible by 4 100 ≡ 0 ( m o d 4 ) 100 \equiv 0 \pmod 4 100 ≡ 0 ( mod 4 ) ; powers of 10 above tens are multiples of 4 9 , 236 9,236 9 , 236 : 36 = 4 × 9 36 = 4 \times 9 36 = 4 × 9 (divisible)
5 Last digit is 0 or 5 10 ≡ 0 ( m o d 5 ) 10 \equiv 0 \pmod 5 10 ≡ 0 ( mod 5 ) ; only units digit affects remainder 3 , 845 3,845 3 , 845 : ends in 5 (divisible)
6 Satisfies both rule for 2 and rule for 3 gcd ( 2 , 3 ) = 1 \gcd(2, 3) = 1 g cd ( 2 , 3 ) = 1 ; composite divisor property 7 , 422 7,422 7 , 422 : even and 7 + 4 + 2 + 2 = 15 7+4+2+2 = 15 7 + 4 + 2 + 2 = 15 (divisible)
7 Truncated number minus twice the last digit is divisible by 7 10 ( a − 2 b ) = ( 10 a + b ) − 21 b ≡ N ( m o d 7 ) 10(a - 2b) = (10a + b) - 21b \equiv N \pmod 7 10 ( a − 2 b ) = ( 10 a + b ) − 21 b ≡ N ( mod 7 ) 672 672 672 : 67 − 2 ( 2 ) = 63 = 7 × 9 67 - 2(2) = 63 = 7 \times 9 67 − 2 ( 2 ) = 63 = 7 × 9 (divisible)
8 Last three digits form a number divisible by 8 1 , 000 ≡ 0 ( m o d 8 ) 1,000 \equiv 0 \pmod 8 1 , 000 ≡ 0 ( mod 8 ) ; thousands and higher are multiples of 8 15 , 128 15,128 15 , 128 : 128 = 8 × 16 128 = 8 \times 16 128 = 8 × 16 (divisible)
9 Sum of digits is divisible by 9 10 k ≡ 1 ( m o d 9 ) 10^k \equiv 1 \pmod 9 1 0 k ≡ 1 ( mod 9 ) ; sum of digits equals remainder mod 9 28 , 431 28,431 28 , 431 : 2 + 8 + 4 + 3 + 1 = 18 = 9 × 2 2+8+4+3+1 = 18 = 9 \times 2 2 + 8 + 4 + 3 + 1 = 18 = 9 × 2 (divisible)
10 Last digit is 0 10 ≡ 0 ( m o d 10 ) 10 \equiv 0 \pmod{10} 10 ≡ 0 ( mod 10 ) 4 , 290 4,290 4 , 290 : ends in 0 (divisible)
11 Alternating sum of digits is divisible by 11 10 k ≡ ( − 1 ) k ( m o d 11 ) 10^k \equiv (-1)^k \pmod{11} 1 0 k ≡ ( − 1 ) k ( mod 11 ) 91 , 828 91,828 91 , 828 : 8 − 2 + 8 − 1 + 9 = 22 = 11 × 2 8 - 2 + 8 - 1 + 9 = 22 = 11 \times 2 8 − 2 + 8 − 1 + 9 = 22 = 11 × 2 (divisible)
Algorithmic Methods for GCF and LCM
The Greatest Common Factor (GCF) , or Greatest Common Divisor (GCD), of two positive integers a a a and b b b is the largest positive integer that divides both a a a and b b b without remainder. Note that GCF ( a , b ) ≤ min ( a , b ) \text{GCF}(a, b) \le \min(a, b) GCF ( a , b ) ≤ min ( a , b ) .
The Least Common Multiple (LCM) of two positive integers a a a and b b b is the smallest positive integer that is a multiple of both a a a and b b b . Note that LCM ( a , b ) ≥ max ( a , b ) \text{LCM}(a, b) \ge \max(a, b) LCM ( a , b ) ≥ max ( a , b ) .
Method 1: Prime Factorization and Min/Max Exponent Rules
Express a a a and b b b in their canonical prime factorizations using all prime factors present in either number (assigning exponent 0 if a prime does not divide a number): a = p 1 a 1 p 2 a 2 ⋯ p k a k and b = p 1 b 1 p 2 b 2 ⋯ p k b k a = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k} \quad \text{and} \quad b = p_1^{b_1} p_2^{b_2} \cdots p_k^{b_k} a = p 1 a 1 p 2 a 2 ⋯ p k a k and b = p 1 b 1 p 2 b 2 ⋯ p k b k
GCF Formula: Take the minimum exponent for each shared prime factor: GCF ( a , b ) = p 1 min ( a 1 , b 1 ) p 2 min ( a 2 , b 2 ) ⋯ p k min ( a k , b k ) \text{GCF}(a, b) = p_1^{\min(a_1, b_1)} p_2^{\min(a_2, b_2)} \cdots p_k^{\min(a_k, b_k)} GCF ( a , b ) = p 1 m i n ( a 1 , b 1 ) p 2 m i n ( a 2 , b 2 ) ⋯ p k m i n ( a k , b k )
LCM Formula: Take the maximum exponent across all prime factors: LCM ( a , b ) = p 1 max ( a 1 , b 1 ) p 2 max ( a 2 , b 2 ) ⋯ p k max ( a k , b k ) \text{LCM}(a, b) = p_1^{\max(a_1, b_1)} p_2^{\max(a_2, b_2)} \cdots p_k^{\max(a_k, b_k)} LCM ( a , b ) = p 1 m a x ( a 1 , b 1 ) p 2 m a x ( a 2 , b 2 ) ⋯ p k m a x ( a k , b k )
For example, to find the GCF and LCM of 72 72 72 and 120 120 120 : 72 = 2 3 × 3 2 × 5 0 72 = 2^3 \times 3^2 \times 5^0 72 = 2 3 × 3 2 × 5 0 120 = 2 3 × 3 1 × 5 1 120 = 2^3 \times 3^1 \times 5^1 120 = 2 3 × 3 1 × 5 1
GCF ( 72 , 120 ) = 2 min ( 3 , 3 ) × 3 min ( 2 , 1 ) × 5 min ( 0 , 1 ) = 2 3 × 3 1 × 5 0 = 8 × 3 = 24 \text{GCF}(72, 120) = 2^{\min(3,3)} \times 3^{\min(2,1)} \times 5^{\min(0,1)} = 2^3 \times 3^1 \times 5^0 = 8 \times 3 = 24 GCF ( 72 , 120 ) = 2 m i n ( 3 , 3 ) × 3 m i n ( 2 , 1 ) × 5 m i n ( 0 , 1 ) = 2 3 × 3 1 × 5 0 = 8 × 3 = 24 .
LCM ( 72 , 120 ) = 2 max ( 3 , 3 ) × 3 max ( 2 , 1 ) × 5 max ( 0 , 1 ) = 2 3 × 3 2 × 5 1 = 8 × 9 × 5 = 360 \text{LCM}(72, 120) = 2^{\max(3,3)} \times 3^{\max(2,1)} \times 5^{\max(0,1)} = 2^3 \times 3^2 \times 5^1 = 8 \times 9 \times 5 = 360 LCM ( 72 , 120 ) = 2 m a x ( 3 , 3 ) × 3 m a x ( 2 , 1 ) × 5 m a x ( 0 , 1 ) = 2 3 × 3 2 × 5 1 = 8 × 9 × 5 = 360 .
Method 2: The Venn Diagram Representation
Draw two overlapping circles representing numbers a a a and b b b :
Place each instance of a common prime factor in the intersection ( A ∩ B A \cap B A ∩ B ).
Place remaining prime factors unique to a a a in the left region, and those unique to b b b in the right region.
GCF is the product of all prime factors in the intersection .
LCM is the product of all prime factors in the entire union ( A ∪ B A \cup B A ∪ B ).
Method 3: The Ladder (Cake / Upside-Down Division) Method
Write a a a and b b b side by side and divide both concurrently by a common prime factor. Repeat until the resulting quotients are coprime (share no common factor other than 1): 2 72 120 2 36 60 2 18 30 3 9 15 3 5 \begin{array}{r|rr}
- 2 & 72 & 120 \\
- \hline
- 2 & 36 & 60 \\
- \hline
- 2 & 18 & 30 \\
- \hline
- 3 & 9 & 15 \\
- \hline
- & 3 & 5
- \end{array} 2 2 2 3 72 36 18 9 3 120 60 30 15 5
The GCF is the product of the divisors along the left vertical column: 2 × 2 × 2 × 3 = 24 2 \times 2 \times 2 \times 3 = 24 2 × 2 × 2 × 3 = 24 .
The LCM is the product of the left vertical column and the bottom quotient row (forming an "L" shape): 24 × ( 3 × 5 ) = 24 × 15 = 360 24 \times (3 \times 5) = 24 \times 15 = 360 24 × ( 3 × 5 ) = 24 × 15 = 360 .
Method 4: The Euclidean Algorithm
For large integers where prime factorization is computationally difficult, the Euclidean Algorithm computes the GCF in a few steps. It relies on the principle that the greatest common divisor of two integers divides their difference and remainder: 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 )
Applying successive division with remainder: a = b q + r a = bq + r a = b q + r , then gcd ( a , b ) = gcd ( b , r ) \gcd(a, b) = \gcd(b, r) g cd ( a , b ) = g cd ( b , r ) . The process terminates when the remainder reaches 0; the last non-zero remainder is the GCF.
The Fundamental Product Identity
For any two positive integers a a a and b b b : GCF ( a , b ) × LCM ( a , b ) = a × b \text{GCF}(a, b) \times \text{LCM}(a, b) = a \times b GCF ( a , b ) × LCM ( a , b ) = a × b
Proof: In the prime factorization formulas, each prime p i p_i p i contributes p i min ( a i , b i ) p_i^{\min(a_i, b_i)} p i m i n ( a i , b i ) to the GCF and p i max ( a i , b i ) p_i^{\max(a_i, b_i)} p i m a x ( a i , b i ) to the LCM. Because for any two real numbers min ( x , y ) + max ( x , y ) = x + y \min(x, y) + \max(x, y) = x + y min ( x , y ) + max ( x , y ) = x + y , multiplying the two yields: p i min ( a i , b i ) ⋅ p i max ( a i , b i ) = p i min ( a i , b i ) + max ( a i , b i ) = p i a i + b i = p i a i ⋅ p i b i p_i^{\min(a_i, b_i)} \cdot p_i^{\max(a_i, b_i)} = p_i^{\min(a_i, b_i) + \max(a_i, b_i)} = p_i^{a_i + b_i} = p_i^{a_i} \cdot p_i^{b_i} p i m i n ( a i , b i ) ⋅ p i m a x ( a i , b i ) = p i m i n ( a i , b i ) + m a x ( a i , b i ) = p i a i + b i = p i a i ⋅ p i b i
Taking the product across all primes reproduces a × b a \times b a × b . Note: this product identity holds strictly for two numbers and does not generalize directly to three or more numbers without inclusion-exclusion adjustments.
Real-World Applications and Problem Solving
A critical competency on educator certification exams is distinguishing between word problems that require finding the GCF versus those that require finding the LCM.
Contexts Requiring GCF (Partitioning and Tiling)
GCF problems typically involve breaking down quantities into smaller, equal subsets without leftovers:
Equal Partitioning: Creating identical gift bags, medical kits, or care packages from different quantities of items (e.g., distributing 48 pens and 64 notebooks into identical kits).
Cutting Materials: Cutting boards, fabrics, or wires of lengths L 1 L_1 L 1 and L 2 L_2 L 2 into pieces of the greatest possible equal length without any waste.
Geometric Tiling: Paving a rectangular floor of dimensions L × W L \times W L × W with the largest possible congruent square tiles without cutting any tiles.
Contexts Requiring LCM (Synchronization and Cycles)
LCM problems typically involve periodic events that repeat at fixed time or distance intervals and ask when the events will synchronize again:
Periodic Synchronization: Two or more blinking lighthouses, bell chimes, or traffic signals that flash or chime at intervals of t 1 , t 2 , t_1, t_2, t 1 , t 2 , and t 3 t_3 t 3 seconds, asking when they will flash simultaneously next.
Track Laps: Runners running around a circular track who complete one lap in m 1 m_1 m 1 and m 2 m_2 m 2 minutes, asking when they will meet again at the starting line.
Packaging Discrepancies: Hot dogs packaged in packs of 10 and hot dog buns in packs of 8, asking for the minimum number of each package to buy so that no hot dogs or buns remain unmatched.
- Worked Number Theory Examples
- Worked Example 1: Divisor Count and Factor Analysis
Problem: Find the canonical prime factorization and total number of positive divisors for 720.
Solution: Step 1: Factor 720 using a factor tree or successive division: 720 = 72 × 10 = ( 8 × 9 ) × ( 2 × 5 ) = ( 2 3 × 3 2 ) × ( 2 1 × 5 1 ) = 2 4 × 3 2 × 5 1 720 = 72 \times 10 = (8 \times 9) \times (2 \times 5) = (2^3 \times 3^2) \times (2^1 \times 5^1) = 2^4 \times 3^2 \times 5^1 720 = 72 × 10 = ( 8 × 9 ) × ( 2 × 5 ) = ( 2 3 × 3 2 ) × ( 2 1 × 5 1 ) = 2 4 × 3 2 × 5 1
Step 2: Apply the divisor formula d ( n ) = ( a 1 + 1 ) ( a 2 + 1 ) ( a 3 + 1 ) d(n) = (a_1 + 1)(a_2 + 1)(a_3 + 1) d ( n ) = ( a 1 + 1 ) ( a 2 + 1 ) ( a 3 + 1 ) : d ( 720 ) = ( 4 + 1 ) ( 2 + 1 ) ( 1 + 1 ) = 5 × 3 × 2 = 30 d(720) = (4 + 1)(2 + 1)(1 + 1) = 5 \times 3 \times 2 = 30 d ( 720 ) = ( 4 + 1 ) ( 2 + 1 ) ( 1 + 1 ) = 5 × 3 × 2 = 30
Therefore, 720 has exactly 30 positive divisors.
Worked Example 2: The Euclidean Algorithm for Large Integers
Problem: Find the GCF of 546 and 126 using the Euclidean algorithm, and then compute their LCM using the product identity.
Solution: Step 1: Execute successive divisions with remainder: 546 = 126 × 4 + 42 126 = 42 × 3 + 0 \begin{aligned}
- 546 &= 126 \times 4 + 42 \\
- 126 &= 42 \times 3 + 0
- \end{aligned} 546 126 = 126 × 4 + 42 = 42 × 3 + 0
Because the remainder is 0, the last non-zero remainder is 42. Thus: GCF ( 546 , 126 ) = 42 \text{GCF}(546, 126) = 42 GCF ( 546 , 126 ) = 42
Step 2: Use the identity GCF ( a , b ) × LCM ( a , b ) = a × b \text{GCF}(a, b) \times \text{LCM}(a, b) = a \times b GCF ( a , b ) × LCM ( a , b ) = a × b : 42 × LCM ( 546 , 126 ) = 546 × 126 42 \times \text{LCM}(546, 126) = 546 \times 126 42 × LCM ( 546 , 126 ) = 546 × 126 LCM ( 546 , 126 ) = 546 × 126 42 = 546 × 3 = 1638 \text{LCM}(546, 126) = \frac{546 \times 126}{42} = 546 \times 3 = 1638 LCM ( 546 , 126 ) = 42 546 × 126 = 546 × 3 = 1638
Worked Example 3: Floor Tiling Application (GCF)
Problem: A rectangular craft table measures 140 cm by 84 cm. A teacher wishes to cover the entire tabletop completely with congruent square tiles of the largest possible whole-number side length, without cutting any tiles. What is the side length of the tile, and how many tiles are required?
Solution: Step 1: Identify that tiling without cutting requires a common divisor of both length and width. The largest tile requires the GCF of 140 and 84.
Factor both numbers: 140 = 14 × 10 = 2 2 × 5 × 7 140 = 14 \times 10 = 2^2 \times 5 \times 7 140 = 14 × 10 = 2 2 × 5 × 7 84 = 12 × 7 = 2 2 × 3 × 7 84 = 12 \times 7 = 2^2 \times 3 \times 7 84 = 12 × 7 = 2 2 × 3 × 7 GCF ( 140 , 84 ) = 2 2 × 7 = 4 × 7 = 28 cm \text{GCF}(140, 84) = 2^2 \times 7 = 4 \times 7 = 28\text{ cm} GCF ( 140 , 84 ) = 2 2 × 7 = 4 × 7 = 28 cm
The side length of the largest square tile is 28 cm.
Step 2: Determine total tile count:
Number of tiles along length: 140 ÷ 28 = 5 140 \div 28 = 5 140 ÷ 28 = 5 .
Number of tiles along width: 84 ÷ 28 = 3 84 \div 28 = 3 84 ÷ 28 = 3 .
Total tiles needed: 5 × 3 = 15 tiles 5 \times 3 = 15\text{ tiles} 5 × 3 = 15 tiles .
Worked Example 4: Cyclic Synchronization Application (LCM)
Problem: Three city transit buses depart a central terminal at 6:00 AM. Route A bus departs every 12 minutes, Route B bus departs every 18 minutes, and Route C bus departs every 30 minutes. At what time will all three buses depart the central terminal together again?
Solution: Step 1: Identify that finding the next simultaneous departure requires finding the Least Common Multiple of the three cycle periods: LCM ( 12 , 18 , 30 ) \text{LCM}(12, 18, 30) LCM ( 12 , 18 , 30 ) .
Step 2: Prime factorize each time interval: 12 = 2 2 × 3 1 12 = 2^2 \times 3^1 12 = 2 2 × 3 1 18 = 2 1 × 3 2 18 = 2^1 \times 3^2 18 = 2 1 × 3 2 30 = 2 1 × 3 1 × 5 1 30 = 2^1 \times 3^1 \times 5^1 30 = 2 1 × 3 1 × 5 1
Step 3: Apply the maximum exponent formula across all three prime factorizations: LCM ( 12 , 18 , 30 ) = 2 max ( 2 , 1 , 1 ) × 3 max ( 1 , 2 , 1 ) × 5 max ( 0 , 0 , 1 ) = 2 2 × 3 2 × 5 1 = 4 × 9 × 5 = 180 minutes \text{LCM}(12, 18, 30) = 2^{\max(2,1,1)} \times 3^{\max(1,2,1)} \times 5^{\max(0,0,1)} = 2^2 \times 3^2 \times 5^1 = 4 \times 9 \times 5 = 180\text{ minutes} LCM ( 12 , 18 , 30 ) = 2 m a x ( 2 , 1 , 1 ) × 3 m a x ( 1 , 2 , 1 ) × 5 m a x ( 0 , 0 , 1 ) = 2 2 × 3 2 × 5 1 = 4 × 9 × 5 = 180 minutes
Step 4: Convert minutes to hours: 180 minutes = 3 hours 180\text{ minutes} = 3\text{ hours} 180 minutes = 3 hours
Adding 3 hours to 6:00 AM gives 9:00 AM as the next simultaneous departure.