Factors and Multiples
Every integer greater than 1 can be described by the numbers that divide it evenly and the numbers it can produce by multiplication. These two ideas — factors and multiples — form the foundation of number theory, the branch of mathematics concerned with the properties of integers. Understanding factors and multiples allows us to simplify fractions, solve problems involving shared quantities, and unlock deeper structures hidden inside ordinary numbers. A factor (or divisor) of an integer n is any integer d such that d divides n without leaving a remainder, written d | n. A multiple of n is any integer of the form kn where k is itself an integer. For example, 4 is a factor of 28 because 28 ÷ 4 = 7 exactly, while 28 is a multiple of 4 because 4 × 7 = 28. Factors and multiples are mirror images of the same relationship: if d is a factor of n, then n is a multiple of d. Two of the most practically important ideas built from factors and multiples are the Highest Common Factor (HCF) — also called the Greatest Common Divisor (GCD) — and the Lowest Common Multiple (LCM). The HCF of two numbers is the largest factor they share; the LCM is the smallest positive multiple they share. These tools appear everywhere from reducing fractions to scheduling repeating events, and they connect deeply to the unique factorisation of integers into prime numbers.
- Factors and Divisibility
- Prime and Composite Numbers
- Prime Factorisation Using a Factor Tree
- Highest Common Factor (HCF)
- Lowest Common Multiple (LCM)
- The Euclidean Algorithm
Factors and Divisibility
An integer d is a factor of integer n if there exists an integer q such that n = d × q. Equivalently, n mod d = 0. Every positive integer n has at least two factors: 1 and itself. To list all factors of n, test every integer from 1 up to √n; if d divides n, then both d and n/d are factors. For example, to find all factors of 36: test 1 (36/1=36 ✓), 2 (36/2=18 ✓), 3 (36/3=12 ✓), 4 (36/4=9 ✓), 6 (36/6=6 ✓), then stop since √36 = 6. Factors of 36: {1, 2, 3, 4, 6, 9, 12, 18, 36}.
Prime and Composite Numbers
A prime number is an integer p ≥ 2 whose only positive factors are 1 and p itself. Examples: 2, 3, 5, 7, 11, 13, 17, 19, 23, ... Note that 2 is the only even prime. A composite number is an integer n ≥ 2 that has at least one factor other than 1 and n. Examples: 4, 6, 8, 9, 10, 12, ... The number 1 is neither prime nor composite by convention. The Fundamental Theorem of Arithmetic states that every integer n ≥ 2 has a unique prime factorisation (up to ordering): n = p₁^a₁ × p₂^a₂ × ... × pₖ^aₖ. For instance, 360 = 2³ × 3² × 5.
Prime Factorisation Using a Factor Tree
To find the prime factorisation of a number, repeatedly divide by the smallest prime possible. Example: 84 → 84 = 2 × 42 = 2 × 2 × 21 = 2 × 2 × 3 × 7 = 2² × 3 × 7. This tree-like process always terminates and always yields the same set of primes, confirming the uniqueness guaranteed by the Fundamental Theorem.
Highest Common Factor (HCF)
The HCF of two integers a and b is the largest integer that divides both. Method 1 — list all factors of each number and pick the greatest common one. Method 2 — use prime factorisations: write each number as a product of primes and take the product of primes appearing in BOTH, using the LOWER power each time. For HCF(72, 90): 72 = 2³ × 3², 90 = 2 × 3² × 5. Common primes with lower powers: 2¹ × 3² = 2 × 9 = 18. So HCF(72, 90) = 18. Method 3 — the Euclidean Algorithm: repeatedly replace (a, b) with (b, a mod b) until the remainder is 0; the last non-zero remainder is the HCF.
Lowest Common Multiple (LCM)
The LCM of two integers a and b is the smallest positive integer divisible by both. Method — use prime factorisations and take the product of all primes appearing in EITHER number, using the HIGHER power each time. For LCM(72, 90): 72 = 2³ × 3², 90 = 2 × 3² × 5. Take 2³ × 3² × 5 = 8 × 9 × 5 = 360. So LCM(72, 90) = 360. A crucial relationship connects HCF and LCM: for any two positive integers a and b, HCF(a, b) × LCM(a, b) = a × b. Here: 18 × 360 = 6480 = 72 × 90. ✓
The Euclidean Algorithm
For large numbers, listing factors is slow. The Euclidean Algorithm finds HCF(a, b) efficiently. Repeatedly apply: HCF(a, b) = HCF(b, a mod b). Example — HCF(252, 198): HCF(252, 198) → HCF(198, 54) since 252 = 1×198 + 54 → HCF(54, 36) since 198 = 3×54 + 36 → HCF(36, 18) since 54 = 1×36 + 18 → HCF(18, 0) since 36 = 2×18 + 0. Answer: HCF = 18. The algorithm terminates because remainders strictly decrease and are non-negative.
The Key Equation
- a,\, b — The two positive integers (dimensionless): Any two positive integers whose HCF and LCM are being computed.
- \text{HCF}(a,b) — Highest Common Factor (dimensionless): The largest positive integer that divides both a and b without remainder.
- \text{LCM}(a,b) — Lowest Common Multiple (dimensionless): The smallest positive integer that is a multiple of both a and b.
Worked Example
Problem. Two lighthouse beams rotate so that the first completes a full rotation every 12 minutes and the second every 18 minutes. They are both pointing due north at time t = 0. (a) After how many minutes will they next both point due north simultaneously? (b) The harbour master also knows that LCM(12, 18) × HCF(12, 18) should equal 12 × 18. Verify this.
Answer. The beams next align after 36 minutes. The verification confirms HCF × LCM = a × b = 216.
Origins · 1 minEuclid of Alexandria and how this was discovered
Euclid systematised Greek mathematics in his landmark work Elements (~300 BCE), which includes Book VII dedicated entirely to number theory. In Propositions 1 and 2 of Book VII he describes what is now called the Euclidean Algorithm — the oldest known algorithm still in common use — for finding the greatest common measure (HCF) of two numbers. He also proved that there are infinitely many prime numbers, a result that remains one of the most elegant proofs in all of mathematics. Euclid's Elements was used as the primary mathematics textbook in schools for over 2000 years and has been translated into more languages than any book other than the Bible.
Related Concepts
- Prime Factorisation — Prime factorisation is the direct application of prime numbers to express any integer as a unique product of primes, forming the core technique for computing HCF and LCM.
- Divisibility Rules — Divisibility rules provide quick shortcuts for determining whether one number is a factor of another without performing full division.
- Modular Arithmetic — Modular arithmetic formalises the idea of remainders, making the divisibility condition d | n (remainder = 0) the cornerstone of a rich algebraic system.
- Simplifying Fractions — Reducing a fraction to its lowest terms requires dividing numerator and denominator by their HCF — a direct and essential application of factor theory.