Divisibility, primes and the gcd

Number theory studies the whole numbers. It once looked like the most useless part of mathematics; today it keeps every online payment and message safe.

Divisibility

a divides b, written a | b, if b = a × k for some integer k: 3 | 12, but 3 ∤ 13.

The division algorithm: for any integer a and positive integer d, there are unique q and r with

a = d × q + r,   0 ≤ r < d

q is the quotient and r the remainder: 17 = 5 × 3 + 2. In Python, a // d is q and a % d is r, and r is never negative when d > 0: −17 // 5 is −4 and −17 % 5 is 3. (C rounds toward zero instead, so −17 % 5 is −2 there.)

Primes

A prime is a whole number greater than 1 whose only positive divisors are 1 and itself: 2, 3, 5, 7, 11, ... A number greater than 1 that is not prime is composite.

• Fundamental theorem of arithmetic: every integer greater than 1 is a product of primes in exactly one way, apart from order: 360 = 2³ × 3² × 5.
• There are infinitely many primes (Euclid): if p₁, ..., pₙ were all of them, then p₁ × ... × pₙ + 1 leaves remainder 1 when divided by each one, so its prime factors are new primes.
• To test n, try divisors only up to √n: if n = a × b, one of a and b is at most √n.

The sieve of Eratosthenes finds every prime up to n: list 2 to n; the first unmarked number is prime, so cross out its multiples; repeat.

n = 30
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False

p = 2
while p * p <= n:
    if is_prime[p]:
        for multiple in range(p * p, n + 1, p):   # cross out p², p² + p, ...
            is_prime[multiple] = False
    p += 1

primes = [k for k in range(n + 1) if is_prime[k]]
print(primes)

Crossing out starts at p × p, because smaller multiples of p have a smaller prime factor and are already crossed out.

The greatest common divisor

The gcd of a and b is the largest number dividing both: gcd(24, 36) = 12. If gcd(a, b) = 1, a and b are coprime.

Euclid's algorithm rests on one fact: gcd(a, b) = gcd(b, a mod b), because any number dividing a and b also divides a − qb, and the other way round. Repeat until the remainder is 0:

def gcd(a, b):
    while b != 0:
        print(f"gcd({a}, {b}): {a} = {b} × {a // b} + {a % b}")
        a, b = b, a % b
    return a

g = gcd(252, 105)
print("gcd =", g)
print("lcm =", 252 * 105 // g)

It is extremely fast: the numbers at least halve every two steps, so even 600-digit numbers need only a few thousand steps. Python has it as math.gcd.

The least common multiple, the smallest number both divide, follows from the gcd: lcm(a, b) = a × b / gcd(a, b). lcm(4, 6) = 24 / 2 = 12.

Mark lesson complete