Number theory I

Some problems are really about what two numbers have in common, or about how a value cycles as it grows. Does something sync up? How many times? When does a pattern repeat? Number theory gives you a small set of tools for exactly these questions.

The most useful of those tools is the greatest common divisor, or GCD: the largest number that divides two given numbers with no remainder. Every pair of numbers shares at least the divisor 1, so a GCD always exists.

Finding GCD with Euclid's algorithm

Take 48 and 18. You could list every divisor of each and pick the largest one they share, but there is a much faster way.

Divide 48 by 18: the quotient is 2 and the remainder is 12, since 48 = 18 × 2 + 12. Any number that divides both 48 and 18 also divides 12, so the pair (48, 18) has the same GCD as the pair (18, 12).

Repeat the same step on the smaller pair. Divide 18 by 12: quotient 1, remainder 6, so GCD(18, 12) = GCD(12, 6). Divide 12 by 6: quotient 2, remainder 0. Once the remainder hits 0, the other number in the pair is the answer: GCD(48, 18) = 6.

1def gcd(a, b):2    while b != 0:3        a, b = b, a % b4    return a5
6
7print(gcd(48, 18))8print(gcd(100, 35))9print(gcd(17, 13))

6
5
1

The program repeats this on three different pairs. Each remainder is smaller than the divisor that produced it, so the numbers shrink fast, and the loop finishes in only a handful of steps even for large inputs.

Prime numbers and trial division

A prime number has exactly two divisors: 1 and itself. To test whether n is prime, look for a divisor between 2 and the square root of n. If none divides n, it is prime.

Stopping the search at the square root is not a shortcut for convenience, it is exact. If n has a divisor d bigger than its square root, then n / d is a divisor smaller than the square root. Divisors always pair up around the square root, so checking below it is enough to catch both halves of every pair.

Try it on 47. Its square root is about 6.9, so check 2, 3, 4, 5 and 6. None divides 47, so 47 is prime.

1def is_prime(n):2    if n < 2:3        return False4    i = 25    while i * i <= n:6        if n % i == 0:7            return False8        i += 19    return True10
11
12print(is_prime(47))13print(is_prime(48))14print(is_prime(2))15print(is_prime(1))

True
False
True
False

The four calls cover the cases worth knowing. is_prime(47) is True, and is_prime(48) is False because 2 divides it. is_prime(2) is True: 2 is the smallest prime, and the only even one. is_prime(1) is False: 1 fails the definition, since a prime needs exactly two divisors and 1 has only one.

Factoring and counting divisors

Factoring a number means finding the primes that multiply to give it. Trial division does this directly: divide out 2 as many times as it fits, then try 3, then 5, and so on, always with the smallest remaining candidate.

Counting divisors does not need a full list. Suppose 36 people need to stand in equal-sized rows. How many row sizes work? Every divisor of 36 is a valid row size, so the question is really "how many divisors does 36 have?"

Write 36 as a product of primes: 36 = 2² × 3². Each exponent tells you how many powers of that prime you can choose for a divisor, 0 through the exponent, so 3 choices for the power of 2 and 3 choices for the power of 3. Multiply the counts: (2 + 1) × (2 + 1) = 9 divisors, so 9 row sizes.

1def count_divisors(n):2    count = 03    i = 14    while i * i <= n:5        if n % i == 0:6            count += 17            if i * i != n:8                count += 19        i += 110    return count11
12
13print(count_divisors(36))14print(count_divisors(12))15print(count_divisors(1))

9
6
1

The program checks this formula against a direct count for three numbers. count_divisors(36) is 9, matching the row-size answer above. count_divisors(12) is 6 (1, 2, 3, 4, 6, 12). count_divisors(1) is 1: 1 divides only itself.

Least common multiple

The least common multiple, or LCM, of two numbers is the smallest positive number that both divide evenly. You get it from the GCD: LCM(a, b) = (a × b) / GCD(a, b).

This works because a × b contains every prime factor of a and every prime factor of b, counted twice wherever a prime appears in both. Dividing by GCD(a, b) removes exactly one of those duplicated copies, leaving the smallest number that still contains everything a and b need.

For 12 and 18: GCD(12, 18) = 6, so LCM(12, 18) = (12 × 18) / 6 = 36.

Modular arithmetic and cycles

A remainder tells you where you are inside a repeating cycle, which is exactly what modular arithmetic is for.

Suppose day 1 is a Monday, and you want to know the day of the week on day 100. There are 7 days in the cycle, and day 100 is (100 - 1) % 7 = 0 days after a Monday, so day 100 is a Monday too.

Here is a second kind of cycle question. One process runs every 5 days and another every 7 days, and both run on day 1. When do they next both run on the same day? The answer is day 1 plus their LCM: LCM(5, 7) = 35, so the next shared day is day 36.

Getting these right

A prime check that only rules out even numbers is not finished. Every prime bigger than 2 is odd, but plenty of odd numbers are not prime, so you still need to test the odd candidates up to the square root.

GCD and LCM are easy to swap by accident. GCD(12, 18) = 6 is the largest number that divides both. LCM(12, 18) = 36 is the smallest number that both divide. One shrinks toward the numbers, the other grows away from them.

And when you factor a number, remember that 1 is not prime and 2 is the only even prime. A factoring loop that starts testing at 1, or that assumes every prime is odd, will get the wrong answer on small inputs.