Skip to content
Tutorials Center
My learning

Topics

Lesson 5 of 37 ยท 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