Skip to content

Lesson 5 · Divisibility and Primes

Divisibility and Its Properties

Define divisibility, prove its core rules such as transitivity and linear combinations, count divisors, and use the rules to solve problems, with runnable Python checks.

We say that an integer a divides an integer b, written a | b, when b = a·k for some integer k. The number a is then a divisor or factor of b, and b is a multiple of a. For example 6 | 42 because 42 = 6·7, and 5 ∤ 42 because no integer k gives 5k = 42.

This sounds like a trivial definition, but nearly every later idea (primes, gcd, congruences) is built on a handful of rules about "divides". This lesson proves those rules and shows how they combine to solve problems that look hard at first glance.

The basic rules

Let a, b, c be integers. Each rule below follows directly from the definition b = a·k.

  1. Reflexive: a | a, since a = a·1.
  2. Transitive: if a | b and b | c then a | c (shown in the previous chapter's proof lesson).
  3. Everything divides 0, and 1 divides everything: 0 = a·0 and b = 1·b.
  4. Multiples: if a | b then a | bc for any integer c.
  5. Sums and differences: if a | b and a | c then a | (b + c) and a | (b − c).
  6. Linear combinations: if a | b and a | c then a | (bx + cy) for all integers x and y.
  7. Size: if a | b and b ≠ 0 then |a| ≤ |b|. So a nonzero number has finitely many divisors.
  8. Antisymmetric for positives: if a | b and b | a with a, b > 0 then a = b.

Rule 6 is the workhorse. If b = a·m and c = a·n, then bx + cy = a(mx + ny), a multiple of a. It means that a common divisor of two numbers divides every combination of them. The Euclidean algorithm will rest entirely on this.

Python Check the rules on examples

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Using the rules

Problem: if 7 divides 3a + 2b, must 7 also divide 5a + 6b? And must it divide 4a + 5b?

Do not start proving. First test both claims on a range of integers, because a false claim cannot be proved and the counterexample will often show what is going on.

Python Test before you prove

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The first claim has counterexamples (for instance a = 1, b = 2 gives 3 + 4 = 7 but 5 + 12 = 17), so it is false. The second has none, which suggests it is true. Now find the combination that proves it: multiply the known multiple of 7 by 6 and subtract the target.

6(3a + 2b) − (4a + 5b) = 18a + 12b − 4a − 5b = 14a + 7b = 7(2a + b).

Since 7 divides 3a + 2b, it divides 6(3a + 2b) by rule 4. It also divides 7(2a + b), so by rule 5 it divides 4a + 5b. The next chapter on congruences turns this style of argument into routine algebra.

Counting divisors

The divisors of 36 are 1, 2, 3, 4, 6, 9, 12, 18, 36. They come in pairs whose product is 36: (1, 36), (2, 18), (3, 12), (4, 9), and (6, 6). Every divisor d at most √n pairs with n/d at least √n. So you only need to search up to √n to list all divisors, which turns an O(n) loop into O(√n).

Python Divisors in square-root time

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A number is a perfect square exactly when its divisor count is odd, because only squares have a "pair" (d, d) that counts once. The next lessons give a formula for the number of divisors in terms of the prime factorization.

Even and odd, and parity arguments

Parity (even or odd) is divisibility by 2. Short rules: even + even = even, odd + odd = even, even · anything = even, odd · odd = odd. Parity arguments are surprisingly powerful. Example: can you pick 1, 2, ..., 9 in some order a₁, ..., a₉ so that (a₁ − 1)(a₂ − 2)···(a₉ − 9) is odd? Each factor must be odd, so aᵢ and i have opposite parity. But there are five odd positions and only four even numbers to put there, so no.

flowchart TD
  A["a divides b"] --> B["b = a * k"]
  B --> C["a divides b*x"]
  B --> D["a divides b+c, if a divides c"]
  C --> E["a divides b*x + c*y"]
  D --> E

Every divisibility rule comes from unfolding b = a·k.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. Which statement is true?

    0 = 5 * 0, so 5 | 0. Also 0 divides only 0, 5 does not divide 12, and -3 divides 9.
  2. 2. If a | b and a | c, which expression must a also divide?

    Any integer linear combination bx + cy is a multiple of a.
  3. 3. How many divisors does 36 have?

    They are 1, 2, 3, 4, 6, 9, 12, 18, 36. The count is odd because 36 is a perfect square.
  4. 4. Why is searching up to the square root of n enough to find all divisors?

    Each divisor above sqrt(n) pairs with a small divisor n/d.

Summary

  • a | b means b = a·k for an integer k; every integer divides 0 and 1 divides every integer.
  • Divisibility is reflexive and transitive, and a common divisor divides every integer combination bx + cy.
  • A nonzero integer has only finitely many divisors, and they pair up around √n.
  • Perfect squares are the numbers with an odd count of divisors.
  • Test a claim on many integers before you try to prove it.

Next: Divisibility Tests