Number System I: Factors, Divisibility, HCF and LCM formulas
At a glance
prime test: divide by primes up to √n; primes > 3 are 6k ± 1 squares end in 0, 1, 4, 5, 6, 9; n consecutive integers → divisible by n! 8: last 3 digits; 11: alternate-digit difference; 7: tens + 5 × units N = pᵃ qᵇ rᶜ → (a + 1)(b + 1)(c + 1) factors sum of factors = (1 + … + pᵃ)(1 + … + qᵇ)(1 + … + rᶜ) φ(N) = N(1 − 1/p)(1 − 1/q)…; co-prime factor pairs = 2^(m − 1) HCF: lower powers of common primes LCM: higher powers of all HCF × LCM = A × B (two numbers) repeat and meet → LCM cut into equal pieces → HCF zeros of n! = ⌊n/5⌋ + ⌊n/25⌋ + ⌊n/125⌋ + …
Kinds of numbers
| Kind | What it means | Examples |
|---|---|---|
| Natural | counting numbers 1, 2, 3, … | 1, 7, 250 |
| Whole | natural numbers and 0 | 0, 1, 2, … |
| Integers | whole numbers and their negatives | −3, 0, 12 |
| Rational | can be written p/q with integers p, q and q ≠ 0; decimal ends or repeats | −2, 3/4, 0.1666… |
| Irrational | cannot be written as p/q; decimal never ends or repeats | √2, π, 2 + √3 |
| Prime | exactly two factors: 1 and itself | 2, 3, 5, 7, 11 |
| Composite | more than two factors | 4, 9, 91 |
| Co-prime | a pair with HCF 1 (neither needs to be prime) | 8 and 15 |
1 is neither prime nor composite. 0 is even, and an integer, but not natural.
n! = 1 × 2 × … × n, 0! = 1, 5! = 120 |x| = x if x ≥ 0, −x if x < 0 (distance from 0 on the number line) a perfect square ends only in 0, 1, 4, 5, 6 or 9 a perfect square is 3k or 3k + 1, and 4k or 4k + 1 every prime above 3 is 6k − 1 or 6k + 1 a product of n consecutive integers is divisible by n!
Shortcut: To test n, divide only by primes up to √n. If none divides it, n is prime. Also, every prime above 3 is of the form 6k ± 1 (but not every 6k ± 1 is prime: 25 = 6 × 4 + 1).
Shortcut: A number ending in 2, 3, 7 or 8 is never a square, and neither is one that leaves remainder 2 by 3 or remainder 2 or 3 by 4. So 5,555 is out at once: its last two digits, 55, leave 3 by 4.
Divisibility rules
| Divisor | Test | Example |
|---|---|---|
| 2 | last digit even | 3,758 |
| 3 | digit sum divisible by 3 | 4,812: 4 + 8 + 1 + 2 = 15 |
| 4 | last two digits divisible by 4 | 7,316: 16 |
| 5 | last digit 0 or 5 | 2,345 |
| 6 | passes the tests for 2 and 3 | 4,812 |
| 8 | last three digits divisible by 8 | 5,832: 832 = 8 × 104 |
| 9 | digit sum divisible by 9 | 5,832: 5 + 8 + 3 + 2 = 18 |
| 10 | last digit 0 | 4,560 |
| 11 | (sum of odd-place digits) − (sum of even-place digits) is 0 or a multiple of 11 | 8,712: (2 + 7) − (1 + 8) = 0 |
| 12, 72, … | split into co-prime parts and test each: 12 = 3 × 4, 72 = 8 × 9 | 2,736 passes 8 and 9, so 72 divides it |
| 7 | tens + 5 × units (or tens − 2 × units); repeat until small | 4,823 → 482 + 15 = 497 → 49 + 35 = 84 = 7 × 12 |
| 13 | tens + 4 × units; repeat | 3,211 → 321 + 4 = 325 → 32 + 20 = 52 = 13 × 4 |
| 19 | tens + 2 × units; repeat | 2,185 → 218 + 10 = 228 → 22 + 16 = 38 = 19 × 2 |
| 7, 11, 13 | alternating sum of 3-digit groups from the right (1001 = 7 × 11 × 13) | 123,123: 123 − 123 = 0, so all three divide it |
'tens' means the number with its last digit removed (497 → 49). These tests tell you whether the number divides, not what the remainder is.
Shortcut: Write N = 10t + u. For 7, multiply by 5: 50t + 5u, and 50 = 7 × 7 + 1, so N is a multiple of 7 exactly when t + 5u is. The same trick uses 40 = 3 × 13 + 1 for 13 and 20 = 19 + 1 for 19.
Prime factorisation: the factor tree
Shortcut: A number is a perfect square when every power in its factorisation is even, and a perfect cube when every power is a multiple of 3.
How many factors, and their sum
| Quantity | Formula | For 72 = 2³ × 3² |
|---|---|---|
| number of factors d(N) | (a + 1)(b + 1)(c + 1) | 4 × 3 = 12 |
| sum of factors | (1 + p + … + pᵃ)(1 + q + … + qᵇ)(1 + r + … + rᶜ) | 15 × 13 = 195 |
| odd factors (p = 2) | (b + 1)(c + 1) | 3 |
| even factors (p = 2) | a(b + 1)(c + 1) = total − odd | 12 − 3 = 9 |
| factors that are multiples of p | a(b + 1)(c + 1) | multiples of 3: 4 × 2 = 8 |
| product of all factors | N^(d(N)/2) | 72⁶ |
| ways to write N = x × y (order ignored) | d(N)/2, or (d(N) + 1)/2 if N is a perfect square | 6 |
| ways as a product of two co-prime factors | 2^(m − 1), m = number of different primes | 2: 1 × 72, 8 × 9 |
| Euler's totient φ(N): numbers 1 to N co-prime to N | N(1 − 1/p)(1 − 1/q)(1 − 1/r) | 72 × ½ × ⅔ = 24 |
| sum of numbers below N co-prime to N | N × φ(N) / 2 | 72 × 24 / 2 = 864 |
Shortcut: Odd factors ignore the 2 entirely. Even factors = total − odd. For 72: odd factors are 1 × 3 = 3, so even factors are 12 − 3 = 9.
HCF and LCM from prime powers
72 = 2³ × 3² 120 = 2³ × 3 × 5 HCF = 2³ × 3 = 24 LCM = 2³ × 3² × 5 = 360 HCF × LCM = A × B (two numbers only) HCF of fractions = HCF of numerators / LCM of denominators LCM of fractions = LCM of numerators / HCF of denominators
Bells, tiles and remainders
largest number dividing a, b, c exactly → HCF(a, b, c) largest number leaving remainders r₁, r₂ → HCF(a − r₁, b − r₂) largest number leaving the same remainder → HCF(b − a, c − b) smallest number divisible by a, b, c → LCM(a, b, c) smallest leaving remainder r with each → LCM + r
Trailing zeros of n!
zeros at the end of n! = ⌊n/5⌋ + ⌊n/25⌋ + ⌊n/125⌋ + … 100!: 20 + 4 = 24
Shortcut: Keep dividing by 5 and adding the whole-number parts: 250 → 50 → 10 → 2, so 250! ends in 50 + 10 + 2 = 62 zeros.
Highest power of a prime in n!
power of p in n! = ⌊n/p⌋ + ⌊n/p²⌋ + ⌊n/p³⌋ + … 3 in 50!: 16 + 5 + 1 = 22
Shortcut: For a composite like 12 = 2² × 3, count each prime, divide by its power in 12, and take the smaller result. Usually the largest prime is the scarce one, but check when it carries a power.
Formulas stick when you use them
The Number System I: Factors, Divisibility, HCF and LCM lesson has worked problems and quick checks for every formula here. Free to start.
Start free