Divisibility, Primes, GCD and LCM

Divisors and multiples

Some divisions come out even: 96 meter readings split into 4 equal groups of 24. Others leave something over: 96 into groups of 5 gives 19 groups with 1 reading left. When the remainder is 0, we say that 4 divides 96.

More precisely, a whole number a is a divisor of b when b is a whole number of times a: b = k \cdot a for some integer k. Then b is a multiple of a. The notation is a vertical bar:

Do not confuse 4 \mid 96, a statement that is true or false, with 4/96, a number. In code, "a divides b" is a remainder test with the modulo operator %:

def divisors(n):
    return [d for d in range(1, n + 1) if n % d == 0]

print(divisors(60))
print(96 % 4 == 0, 96 % 5 == 0)   # does 4 divide 96? does 5?
print(divmod(96, 5))              # quotient and remainder

[1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60]
True False
(19, 1)

divmod(96, 5) returns both answers of a division with remainder: 96 = 19 × 5 + 1.

Quick divisibility tests

For small divisors you can often see the answer without dividing:

Why divisors matter in IT

Whenever something must be split into equal parts, divisors decide what works. 60 has many divisors (1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60), which is one reason an hour has 60 minutes: it splits evenly in many ways. A job in cron's minute field with */15 runs at minutes 0, 15, 30 and 45, evenly spaced. A job with */7 runs at 0, 7, 14, … , 56, and then again at minute 0 of the next hour: only 4 minutes later, because 7 does not divide 60. Similar reasoning applies to splitting 96 quarter-hour readings per day into equal batches, or a disk array into equal stripes.

Prime numbers

A prime number is a whole number greater than 1 whose only positive divisors are 1 and the number itself. The first primes are:

A number greater than 1 that is not prime, such as 12 = 3 × 4, is called composite. Primes are the building blocks of all whole numbers, the way atoms are the building blocks of molecules, and there are infinitely many of them (a fact proved by Euclid more than 2,000 years ago).

Testing whether a number is prime

The direct way is trial division: try to divide by 2, 3, 4, … and see whether any of them goes in evenly. You only have to go up to the square root of the number. Worked example, is 91 prime?

1. \sqrt{91} \approx 9.5, so only the divisors 2 to 9 need testing.
2. 2: 91 is odd. 3: digit sum 10, no. 5: last digit 1, no.
3. 7: 91 / 7 = 13 exactly. So 91 = 7 × 13 is not prime.

Why is the square root enough? If n = a × b and both a and b were larger than \sqrt{n}, their product would be larger than n. So one of the two factors is always at most \sqrt{n}, and you would already have found it. In code, the test d * d <= n expresses the same thing without computing a square root:

def is_prime(n):
    if n < 2:
        return False
    d = 2
    while d * d <= n:          # only test divisors up to the square root
        if n % d == 0:
            return False
        d += 1
    return True

print([n for n in range(1, 40) if is_prime(n)])
print(is_prime(97), is_prime(91), is_prime(1))

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
True False False

Trial division is fine for numbers up to a few billion. The primes used in cryptography have hundreds of digits; testing those needs cleverer methods, covered on the math behind cryptography.

Prime factorization

Any whole number greater than 1 can be broken down into primes that multiply to it. This is its prime factorization. A factor tree is an easy way to find it by hand. Worked example, 360:

1. 360 is even, so split off a 2: 360 = 2 × 180.
2. 180 is even: 180 = 2 × 90.
3. 90 is even: 90 = 2 × 45.
4. 45 is odd; its digit sum is 9, so try 3: 45 = 3 × 15.
5. 15 = 3 × 5, and 3 and 5 are both prime. Stop.

Repeated factors are written as powers, smallest prime first:

The fundamental theorem of arithmetic says that this factorization is unique: whichever split you start with (say 360 = 10 × 36), you always end up with the same primes. In code, the same method divides by 2 as often as possible, then by 3, and so on:

def prime_factors(n):
    factors, d = [], 2
    while d * d <= n:
        while n % d == 0:
            factors.append(d)
            n //= d
        d += 1
    if n > 1:
        factors.append(n)
    return factors

print(prime_factors(360))
print(prime_factors(97))
print(prime_factors(1080), prime_factors(1920))

[2, 2, 2, 3, 3, 5]
[97]
[2, 2, 2, 3, 3, 3, 5] [2, 2, 2, 2, 2, 2, 2, 3, 5]

If nothing divides n up to its square root, whatever is left is itself prime, which is why 97 comes back as [97]. Multiplying two primes is instant, but finding them back from a large product is extremely slow: that one-way street is the basis of RSA encryption (see below).

Greatest common divisor

The greatest common divisor (gcd) of two whole numbers is the largest number that divides both. Worked example with small numbers, \gcd(12, 18):

1. Divisors of 12: 1, 2, 3, 4, 6, 12.
2. Divisors of 18: 1, 2, 3, 6, 9, 18.
3. Common divisors: 1, 2, 3, 6. The greatest is 6.

Listing divisors gets slow for larger numbers. With prime factorizations it is quicker: take every prime the two numbers have in common, with the lowest power that appears. A screen of 1920 × 1080 pixels:

Dividing both numbers by 120 gives 16 and 9: the screen has an aspect ratio of 16:9. Simplifying a fraction works the same way: divide the top and bottom by their gcd, and the fraction is in its simplest form in one step.

Two numbers whose gcd is 1, such as 8 and 15, are called coprime: they share no prime factor. Neither needs to be prime itself.

Euclid's algorithm

Factorizing is hard for large numbers, so computers find the gcd another way. The Euclidean algorithm, over 2,000 years old, rests on one observation: a number that divides both a and b also divides the remainder of a divided by b, and a number that divides b and that remainder also divides a. So both pairs have exactly the same common divisors, and the gcd does not change if you replace the larger number by that remainder:

Worked example, \gcd(1071, 462):

1. Divide 1071 by 462: 1071 = 2 × 462 + 147. Continue with 462 and 147.
2. Divide 462 by 147: 462 = 3 × 147 + 21. Continue with 147 and 21.
3. Divide 147 by 21: 147 = 7 × 21 + 0. The remainder is 0.
4. The last non-zero remainder, 21, is the gcd.

Check: 1071 = 21 × 51 and 462 = 21 × 22, and 51 and 22 share no factor. The same steps in Python:

def gcd_steps(a, b):
    while b:
        print(f"gcd({a}, {b}): {a} = {a // b} x {b} + {a % b}")
        a, b = b, a % b
    return a

print("Result:", gcd_steps(1071, 462))

gcd(1071, 462): 1071 = 2 x 462 + 147
gcd(462, 147): 462 = 3 x 147 + 21
gcd(147, 21): 147 = 7 x 21 + 0
Result: 21

The rule "gcd(a, b) is gcd(b, a mod b), and gcd(a, 0) is a" is also a perfect example of recursion: a function that calls itself on a smaller problem until it reaches a case it can answer directly.

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

print(gcd(1920, 1080), gcd(17, 3120), gcd(65537, 3120))

120 1 1

The algorithm is fast because the remainders shrink quickly: the number of steps grows only with the number of digits, not with the size of the numbers. That is why it is still used in cryptography on numbers with hundreds of digits. Python has it built in as math.gcd.

Least common multiple

The least common multiple (lcm) of two whole numbers is the smallest positive number that is a multiple of both. Kestrel Energy imports meter data every 15 minutes and builds a report every 20 minutes. When do both jobs start at the same moment?

1. Multiples of 15: 15, 30, 45, 60, 75, 90, …
2. Multiples of 20: 20, 40, 60, 80, 100, …
3. The first number in both lists is 60: every 60 minutes.

With prime factorizations, take every prime that appears in either number, with the highest power: 15 = 3 \cdot 5 and 20 = 2^2 \cdot 5, so \operatorname{lcm}(15, 20) = 2^2 \cdot 3 \cdot 5 = 60. The quickest way uses the gcd you already know how to compute. For positive whole numbers:

import math

print(math.gcd(1920, 1080))
w, h = 1920, 1080
g = math.gcd(w, h)
print(f"Aspect ratio {w // g}:{h // g}")
# Two jobs: meter import every 15 minutes, report every 20 minutes
print(f"Both run together every {math.lcm(15, 20)} minutes")
print(15 * 20 // math.gcd(15, 20))

120
Aspect ratio 16:9
Both run together every 60 minutes
60

The lcm is also the smallest common denominator when you add fractions: to add 1/15 and 1/20, rewrite both with denominator 60.

Where primes matter in IT

The best-known use of primes in IT is public-key cryptography. RSA, one of the classic asymmetric encryption methods, builds a key from two large secret primes p and q. Their product n = p \cdot q is public. Anyone can multiply the primes, but recovering them from n, if n has hundreds of digits, is far beyond any known method on ordinary computers. The private key depends on p and q, so it stays secret.

The gcd plays a part too. In a textbook-sized RSA example with p = 61 and q = 53, the key setup uses the number (p - 1)(q - 1) = 60 \cdot 52 = 3120, and the public exponent e must be coprime to it. Both common choices pass: \gcd(17, 3120) = 1 and \gcd(65537, 3120) = 1, as the recursive example above printed. Real keys work the same way with numbers of more than 600 digits. The full story, with the remainder arithmetic it needs, is on modular arithmetic and the math behind cryptography.

Other places where this page's ideas appear:

• Ratios: screen formats, image scaling and video resolutions are simplified with the gcd.
• Scheduling: the lcm says when periodic jobs, backups or maintenance windows collide.
• Checking identifiers: check digits in bank account numbers (IBAN) and card numbers rely on remainders, see modular arithmetic.