Factors, Prime Numbers, GCD and LCM

What a factor is

A factor of a number divides into it exactly, with no remainder left over. Because every factor pairs with another factor — whatever multiplies with it to reach the number — factors are usually listed as pairs. The factors of 36 are 1, 2, 3, 4, 6, 9, 12, 18 and 36, arranged as five pairs.

The last row is unlike the others: 6 × 6 = 36, so 6 is a factor that pairs with itself. That is a square root, and it explains why perfect squares behave differently from every other number.

Finding all factors without missing any

Test each whole number in turn and stop at the square root. The square root of 36 is 6, so test 1, 2, 3, 4, 5 and 6: all of them divide into 36 except 5, giving the pairs above. Nothing below the square root needs rechecking, because any factor above the square root must be paired with one below it.

That shortcut also makes the answer easy to sanity-check. A perfect square has an odd number of factors, because its square root pairs with itself; every other number has an even number. If your factor list for 36 has eight or ten entries rather than nine, something has been dropped or added. The NumberUtils factors calculator returns every factor in ascending order, including 1 and the number itself, for any positive whole number up to 1,000,000,000,000.

Prime numbers

A prime number has exactly two factors: 1 and itself. 7 is prime, because its only factors are 1 and 7. 9 is not, because 1, 3 and 9 all divide into it. Every number greater than 1 is either prime or built up entirely from primes.

Two facts settle most edge cases. 1 is not prime, because it has only one factor rather than two. And 2 is the only even prime, because every larger even number is divisible by 2 as well as by 1 and itself. The primes below 50 are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43 and 47.

To test a number, trial division up to its square root is enough. The square root of 97 is just under 10, so the only candidates worth checking are 2, 3, 5 and 7: 97 is odd, its digits add to 16 so it is not a multiple of 3, and it leaves remainders of 2 and 6 when divided by 5 and 7. Nothing divides it, so 97 is prime. The NumberUtils prime number checker applies this same test and treats 0, 1 and negative numbers as not prime rather than as errors.

Prime factorisation

Prime factorisation breaks a number into primes multiplied together. Divide by 2 repeatedly, then by 3, then 5, 7, 11 and onwards, until nothing but 1 is left. For 360: dividing by 2 leaves 180, then 90, then 45; 45 divides by 3 to leave 15, and by 3 again to leave 5; 5 is prime. So 360 = 2 × 2 × 2 × 3 × 3 × 5, written compactly as 2³ × 3² × 5.

Apart from the order of the factors, every whole number greater than 1 has exactly one prime factorisation, which makes it a reliable way to compare two numbers. It also gives the number of factors directly: adding one to each exponent and multiplying the results gives 4 × 3 × 2 = 24, so 360 has 24 factors. Reducing fractions uses the same idea, as the guide to fractions, decimals and percentages explains.

The greatest common divisor

The greatest common divisor (GCD) of two numbers is the largest number that divides into both of them. 12 divides into both 24 and 36, and nothing larger does, so the GCD of 24 and 36 is 12. Both inputs must be positive whole numbers — the GCD and LCM calculator rejects decimals, zero and negative values rather than rounding them into a misleading answer.

Euclid's algorithm finds the GCD using repeated remainders. Divide the larger number by the smaller, then the smaller by the remainder, and stop when the remainder is zero.

1. 36 ÷ 24 leaves a remainder of 12.
2. 24 ÷ 12 leaves a remainder of 0.
3. The last non-zero remainder, 12, is the GCD.

The zero remainder means that division was exact, so 12 divides into both numbers and nothing larger can. This is what makes ratios reducible: 24:36 shares a common factor of 12, so it simplifies to 2:3 — the same working that reduces 12:18 to 2:3 in the guide to ratios and proportions.

The least common multiple

The least common multiple (LCM) of two numbers is the smallest number divisible by both. It is derived from the GCD rather than searched for: multiply the two numbers together, then divide by their GCD.

LCM of a and b = (a × b) ÷ GCD of a and b

For 24 and 36 the GCD is 12, so the LCM is (24 × 36) ÷ 12 = 864 ÷ 12 = 72. Dividing one number by the GCD before multiplying, (24 ÷ 12) × 36 = 72, gives the same answer with a smaller intermediate value, which is how the calculator does it. For 4 and 6 the GCD is 2, so the LCM is (4 × 6) ÷ 2 = 12.

Where the GCD and LCM get used

Simplifying fractions and ratios

Dividing a numerator and denominator by their GCD reduces a fraction to lowest terms without changing its value. 3/12 has a GCD of 3 and 9/36 has a GCD of 9, and both reduce to 1/4. The GCD does the same job on a ratio: 18:24 shares 6, so it becomes 3:4.

Common denominators

To add or subtract fractions, convert both to a common denominator. The LCM of the denominators is the smallest one that works, and keeps the numbers as small as possible. Adding 1/4 and 1/6 needs a denominator of 12, so 1/4 becomes 3/12 and 1/6 becomes 2/12, giving 5/12.

Intervals that coincide

When two events repeat on a fixed cycle, the LCM of the two cycle lengths is the gap before they coincide again. A bus every 12 minutes and another every 18 minutes, both leaving at 8:00, share a multiple of 36 minutes, so they next leave together at 8:36.

What each tool accepts

These bounds and rounding rules come from the number tools methodology. Input outside these limits is rejected with a message rather than adjusted.