math.wiki
Logic, proof and discrete math › Proof techniques › Direct proof › Proving statements about divisibility
Open on the map
Discrete Mathematics and Proof

Proving statements about divisibility

You know that some integers divide some others. How do you prove that a different integer divides a different number?

You need
Divisibility and primesGrades 4 to 6
Where you are 2 in Direct proof
Logic, proof and discrete math6
Proof techniques14
Direct proof2
Proving statements about even and odd numbers
Proving statements about divisibility

When you reach for it

A claim says that one integer divides another: 12 \mid n^2 + 2n, or 7 \mid ab - 1, or “d divides 1”. The statement a \mid b is true or false; there is nothing inside it to calculate with. The move of this lesson is to trade it for an equation. By the definition of divides, a \mid b means b = ak for some integer k, and an equation can be substituted, expanded and factored. At the end the same definition is used in the other direction, to trade an equation back for the statement.

Reach for it whenever the hypothesis or the conclusion says “divides”, “is a multiple of” or “is divisible by”. The words come from Divisibility and primes: a factor of b goes into b with nothing left over. The shape is the one used in Proving statements about even and odd numbers, where “even” was traded for n = 2k. That was the divisor 2; this lesson is every other divisor.

The lesson takes two days. Day 1 is the unpacking and packing, and the rules it proves, which later proofs cite instead of redoing. Day 2 uses them on expressions: factoring, numbers that sit a fixed amount past a multiple, and claims that turn out to be false.

The procedure

Day 1: unpack, work, pack

Unpack each hypothesis. A hypothesis a \mid b becomes b = ar for some integer r, and each hypothesis gets its own new letter. Writing b = ak and c = ak with the same k would claim b = c, which nobody said.

Work with the equations. Substitute them into the expression the conclusion is about, then expand or regroup.

Pack the conclusion. The goal m \mid N means N = mq for some integer q. So the work aims at writing N as m times something, and the proof then says why that something is an integer. The reason is almost always closure: a sum, difference or product of integers is an integer. A proof that stops at an equation has not finished; the last sentence turns the equation back into the words of the claim (Writing a proof as prose).

Done once in general, this gives rules. Every letter below stands for an integer. The reflexive law a \mid a, the transitive law (a \mid b and b \mid c give a \mid c), and the size bound (a \mid b with b \ne 0 gives |a| \le |b|) are proved in Divisibility as a relation and cited here.

Multiple rule. If a \mid b, then a \mid bc for every integer c.

Proof. Since a \mid b, b = ar for some integer r. Then bc = (ar)c = a(rc) by the associative property of multiplication. The integer rc is a product of integers, so bc is a times an integer, and a \mid bc. \square

Linear-combination rule. If a \mid b and a \mid c, then a \mid bx + cy for all integers x and y.

Proof. Write b = ar and c = as for integers r and s. By the distributive property,

bx + cy = arx + asy = a(rx + sy).

Since rx + sy is an integer, a \mid bx + cy. \square

An expression bx + cy with integers x and y is a linear combination of b and c. Three special cases come up constantly. With x = y = 1, a divides b + c (the sum rule, set as an exercise in What may be assumed and what must be shown). With x = 1 and y = -1, a divides b - c. With y = 0, a divides bx, which is the multiple rule again. On a number line the multiples of a are evenly spaced marks, and the rule says that adding or taking away whole numbers of steps keeps you on the marks.

0 3 6 9 12 15 18 21 24
c - b
 b c
b + c
Figure 1The multiples of 3 are evenly spaced marks. With b = 9 and c = 15 on marks, their sum 24 and their difference 6 land on marks too.

Product rule. If a \mid b and c \mid d, then ac \mid bd.

Proof. Write b = ar and d = cs. Then bd = (ar)(cs) = (ac)(rs), regrouping by the commutative and associative properties. Since rs is an integer, ac \mid bd. \square

Power rule. If a \mid b, then a^n \mid b^n for every positive integer n.

Proof. Write b = ak. Then b^n = (ak)^n = a^n k^n, since a power of a product is the product of the powers (the commutative and associative properties again). The number k^n is a product of n integers, so it is an integer, and a^n \mid b^n. \square

Backwards rule. If a \mid b and a \mid b + c, then a \mid c.

Proof. Write c as a linear combination of the two numbers a is known to divide: c = 1 \cdot (b + c) + (-1) \cdot b. The linear-combination rule gives a \mid c. \square

The backwards rule is how a proof strips off a piece it does not care about: a multiple of a can be added or removed without changing whether a divides the rest.

Day 2: divisibility of expressions

Factoring. To show that one expression divides another, factor the second so that the first appears as a factor. The cofactor is built from integers by adding and multiplying, so closure makes it an integer. The identities used most are these, each checked by multiplying out the right side.

\begin{aligned} x^2 - y^2 &= (x - y)(x + y) \\ x^3 - y^3 &= (x - y)(x^2 + xy + y^2) \\ x^3 + y^3 &= (x + y)(x^2 - xy + y^2) \end{aligned}

A fixed amount past a multiple. A hypothesis such as 7 \mid a - 3 unpacks as a - 3 = 7r, that is, a = 7r + 3: a is 3 more than a multiple of 7. In that form a can be substituted anywhere, and the same packing finishes the proof.

Disproving. A divisibility claim about all integers is false as soon as one choice of integers makes every hypothesis true and the conclusion false (Counterexample). Numbers whose factors can be split up, such as 4, 6, 10 and 15, are where such choices usually live.

Worked examples

Example 1

Day 1: Unpacking and packing with a new divisor

Prove: if 6 \mid n, then 12 \mid n^2 + 2n.

Solution

The given is about 6 and the goal about 12, so no rule applies directly; go to the definition.

Proof. Since 6 \mid n, n = 6k for some integer k. Substituting,

\begin{aligned} n^2 + 2n &= (6k)^2 + 2(6k) \\ &= 36k^2 + 12k \\ &= 12(3k^2 + k). \end{aligned}

The last step factors out 12 by the distributive property, possible because 36 and 12 are both multiples of 12. The number 3k^2 + k is an integer by closure, so n^2 + 2n is 12 times an integer. Therefore 12 \mid n^2 + 2n. \square

A check: n = 6 gives 36 + 12 = 48 = 12 \cdot 4.

Example 2

Day 1: Citing the rules instead of the definition

Prove: if a \mid b and a \mid c, then a^2 \mid b^2 + 3bc.

Solution

Proof. By the power rule with exponent 2, a^2 \mid b^2. By the product rule applied to a \mid b and a \mid c, a \cdot a \mid bc, that is, a^2 \mid bc. So a^2 divides both b^2 and bc, and the linear-combination rule with x = 1 and y = 3 gives a^2 \mid b^2 + 3bc. \square

The same claim from the definition: b = ar and c = as give b^2 + 3bc = a^2r^2 + 3a^2rs = a^2(r^2 + 3rs) where r^2 + 3rs is an integer. Both proofs are complete; the first is shorter because the work was done once, in the rules. A check: a = 3, b = 6, c = 9 give 36 + 162 = 198 = 9 \cdot 22.

Example 3

Day 1: Stripping off a piece

Find every integer n for which n \mid n^2 + 6.

Solution

By the multiple rule, n \mid n \cdot n = n^2 for every integer n. If also n \mid n^2 + 6, the backwards rule (with b = n^2 and c = 6) gives n \mid 6. So n is one of \pm 1, \pm 2, \pm 3, \pm 6.

That shows these are the only candidates, not that they all work. For the other direction, suppose n \mid 6. Together with n \mid n^2, the sum rule gives n \mid n^2 + 6. So the answer is exactly

n \in \{-6, -3, -2, -1, 1, 2, 3, 6\}.

The integer 0 is not on the list, because 0 \nmid 6. A check at n = -3: 9 + 6 = 15 = (-3)(-5).

Example 4

Day 1: A combination that leaves 1

Prove: if an integer d divides both 5n + 3 and 3n + 2 for some integer n, then d = 1 or d = -1.

Solution

The aim is to make n disappear. Multiplying the first expression by 3 and the second by 5 makes both n terms 15n, and subtracting cancels them.

Proof. Suppose d \mid 5n + 3 and d \mid 3n + 2. The linear-combination rule with x = 3 and y = -5 gives

\begin{aligned} d &\mid 3(5n + 3) - 5(3n + 2) \\ &= 15n + 9 - 15n - 10 \\ &= -1. \end{aligned}

So -1 = dq for some integer q, which gives 1 = d(-q) and d \mid 1. Then d \ne 0, since 0 \cdot (-q) = 0, and the size bound gives |d| \le 1. So d = 1 or d = -1. \square

In words: for every integer n, the numbers 5n + 3 and 3n + 2 share no factor other than \pm 1. For n = 4 they are 23 and 14; for n = 7, 38 and 23. Such a pair is called coprime, and the extended Euclidean algorithm is the systematic way to find combinations like this one.

Example 5

Day 2: Factoring a difference of cubes

Prove that x - y \mid x^3 - y^3 for all integers x and y. Then show that 2^{30} - 1 is divisible by 11 and by 31.

Solution

Proof. Multiplying out,

\begin{aligned} &(x - y)(x^2 + xy + y^2) \\ &\quad = x^3 + x^2y + xy^2 - x^2y - xy^2 - y^3 \\ &\quad = x^3 - y^3. \end{aligned}

The cofactor x^2 + xy + y^2 is an integer by closure, so x^3 - y^3 is x - y times an integer, and x - y \mid x^3 - y^3. \square

The proof does not need x \ne y: when x = y it says 0 \mid 0, which is true, since 0 = 0 \cdot 1.

For the number, take x = 2^{10} and y = 1, so that x^3 = 2^{30} and y^3 = 1:

2^{10} - 1 \mid 2^{30} - 1.

Now 2^{10} - 1 = 1023 = 3 \cdot 11 \cdot 31, so 11 \mid 1023 and 31 \mid 1023, and the transitive law gives 11 \mid 2^{30} - 1 and 31 \mid 2^{30} - 1. Nobody had to compute 2^{30} - 1 = 1{,}073{,}741{,}823; the factoring did the work. (The cofactor is 2^{20} + 2^{10} + 1 = 1{,}049{,}601.)

Example 6

Day 2: Numbers a fixed amount past a multiple

Prove: if 7 \mid a - 3 and 7 \mid b - 5, then 7 \mid ab - 1.

Solution

Proof. Unpack each hypothesis with its own letter: a - 3 = 7r and b - 5 = 7s for some integers r and s, so a = 7r + 3 and b = 7s + 5. Then

\begin{aligned} ab - 1 &= (7r + 3)(7s + 5) - 1 \\ &= 49rs + 35r + 21s + 15 - 1 \\ &= 7(7rs + 5r + 3s + 2). \end{aligned}

Since 7rs + 5r + 3s + 2 is an integer, 7 \mid ab - 1. \square

Why it works: every term of the product carries a factor 7 except 3 \cdot 5 = 15, and 15 - 1 = 14 is a multiple of 7. A check: a = 10 and b = 12 satisfy the hypotheses, and ab - 1 = 119 = 7 \cdot 17.

Example 7

Day 2: Two claims that fail

Decide whether each claim holds for all integers. (a) If a \mid bc, then a \mid b or a \mid c. (b) If a \mid b + c, then a \mid b.

Solution

(a) False. Look for an a whose factors can be split between b and c. Take a = 10, b = 4, c = 15. Then bc = 60 = 10 \cdot 6, so the hypothesis 10 \mid bc holds. But 10 \nmid 4 and 10 \nmid 15, so the conclusion fails. The 2 in 10 came from b and the 5 from c, and neither holds all of 10 alone.

(b) False. Take a = 5, b = 2, c = 3. Then 5 \mid 5 = b + c, but 5 \nmid 2. The backwards rule reaches a conclusion about one piece only with the extra hypothesis that a divides the other piece; knowing that a sum is a multiple of a says nothing about the pieces on their own.

Each counterexample settles its claim completely. Claim (a) does become true when a is prime. That fact, Euclid’s lemma, is stated here without proof; its usual proof writes 1 as a combination of a and b by Bezout’s identity.

Boundaries

  • Every rule is about integers, and the multipliers must be integers too. Closure is what made rx + sy an integer; with \displaystyle x = y = \frac{1}{2} the linear-combination rule fails (Exercise 23).
  • The rules run one way. From a \mid c and b \mid c it does not follow that ab \mid c; from a \mid bc it does not follow that a \mid b or a \mid c; and a \mid b + c alone says nothing about b. Each becomes true only with an extra hypothesis, such as a prime or a \mid b.
  • The power rule is for positive integers n. At n = 0 it reads 1 \mid 1, true and empty; for negative n the powers are in general not integers, so divisibility does not apply to them.
  • Every proof here is direct: unpack, compute, pack. A claim with no divisibility hypothesis to unpack, such as 5 \mid n^5 - n for every integer n, needs splitting by remainders (Proof by cases) or induction.
  • Factoring handles one exponent at a time here. For every positive n, x - y \mid x^n - y^n follows from x^n - y^n = (x - y)q with q = x^{n-1} + x^{n-2}y + \cdots + y^{n-1} because the product cancels in pairs when multiplied out.

Where this goes next

The linear-combination rule grows into the Euclidean algorithm and Bezout’s identity, which finds a combination of two numbers equal to their greatest common factor, as Example 4 reached 1. Hypotheses like 7 \mid a - 3 become the congruences of Modular arithmetic, where the computation of Example 6 shrinks to one line. In induction proofs of divisibility, the inductive step is exactly this lesson: unpack the assumed case, then use the rules to pack the next one. And Proof by contraposition turns some claims, such as Exercise 22, into proofs of this direct kind.

Exercises

Day 1: Unpacking and packing

  1. Prove: if 4 \mid m, then 8 \mid m^2 + 6m.
  2. Prove: if a \mid b, then a \mid b^2 - 4b + 6a.
  3. Prove: if a \mid b, then a^3 \mid b^3 + ab^2.

Day 1: Using the rules

  1. Suppose 9 \mid u and 9 \mid v. Which rule, with which x and y, shows that 9 \mid 4u - 11v?
  2. Prove: if a \mid b and a \mid c, then a \mid 2b^2 - 7c.
  3. Prove: if 2 \mid m and 3 \mid n, then 36 \mid m^2 n^2.
  4. Prove: if m \mid n, then m^3 \mid n^5.
  5. Find every integer n for which n - 1 \mid n + 5.
  6. Find every integer n for which n + 2 \mid n^2 + 10.
  7. Prove: if d divides both 7n + 4 and 5n + 3 for some integer n, then d = 1 or d = -1.

Day 2: Factoring

  1. Prove that x + y \mid x^3 + y^3 for all integers x and y.
  2. Use Exercise 11 to show that 13 \mid 5^6 + 1 without computing 5^6.
  3. Prove that n - 1 \mid n^3 - 1 for every integer n, and use it to show that n^3 - 1 is not prime for any integer n \ge 3.
  4. Write 2^{12} - 1 as a difference of two squares, and conclude that 7 and 13 both divide it.

Day 2: A fixed amount past a multiple

  1. Prove: if 5 \mid a - 2 and 5 \mid b - 4, then 5 \mid ab - 3.
  2. Prove: if 9 \mid a - 4 and 9 \mid b - 7, then 9 \mid a + b - 2 and 9 \mid ab - 1.
  3. Prove: if m \mid a - b, then m \mid a^2 + ab - 2b^2.

Day 2: True or false

For each claim about integers, give a proof or a counterexample.

  1. If a \mid c and b \mid c, then ab \mid c.
  2. If a \mid b^2, then a \mid b.
  3. If a \mid b + c and a \mid c, then a \mid b - c.
  4. If a \mid b + c and a \mid b - c, then a \mid b.

Reasoning

  1. Prove: if a \mid b and a \nmid c, then a \nmid b + c.
  2. The proof of the linear-combination rule ends “since rx + sy is an integer”. Find integers a, b and c with a \mid b and a \mid c but \displaystyle a \nmid \frac{1}{2}b + \frac{1}{2}c, and say which step of the proof breaks.
  3. Prove that x - y \mid x^5 - y^5 for all integers x and y.
Answers
  1. Since 4 \mid m, m = 4k for an integer k. Then m^2 + 6m = 16k^2 + 24k = 8(2k^2 + 3k) where 2k^2 + 3k is an integer, so 8 \mid m^2 + 6m. \square
  2. Write b = ak. Then b^2 - 4b + 6a = a^2k^2 - 4ak + 6a = a(ak^2 - 4k + 6) where ak^2 - 4k + 6 is an integer, so a \mid b^2 - 4b + 6a. \square
  3. Write b = ak. Then b^3 + ab^2 = a^3k^3 + a \cdot a^2k^2 = a^3(k^3 + k^2) where k^3 + k^2 is an integer. \square
  4. The linear-combination rule with b = u, c = v, x = 4 and y = -11. From the definition: u = 9r and v = 9s give 4u - 11v = 9(4r - 11s).
  5. By the multiple rule, a \mid b \cdot b = b^2. Then a divides b^2 and c, and the linear-combination rule with x = 2, y = -7 gives a \mid 2b^2 - 7c. \square
  6. The product rule gives 2 \cdot 3 \mid mn, that is, 6 \mid mn. The power rule with exponent 2 gives 36 \mid (mn)^2 = m^2 n^2. \square
  7. Write n = mk. Then n^5 = m^5k^5 = m^3(m^2k^5), and m^2k^5 is an integer, so m^3 \mid n^5. \square (Or: the power rule gives m^3 \mid n^3, then the multiple rule with the factor n^2.)
  8. n \in \{-5, -2, -1, 0, 2, 3, 4, 7\}. Since n + 5 = (n - 1) + 6 and n - 1 \mid n - 1, the backwards rule turns n - 1 \mid n + 5 into n - 1 \mid 6, so n - 1 is one of \pm 1, \pm 2, \pm 3, \pm 6. Conversely, n - 1 \mid 6 and the sum rule give n - 1 \mid n + 5. Check n = -5: -6 \mid 0.
  9. n \in \{-16, -9, -4, -3, -1, 0, 5, 12\}. By the multiple rule, n + 2 \mid (n + 2)(n - 2) = n^2 - 4, and n^2 + 10 = (n^2 - 4) + 14. So n + 2 \mid n^2 + 10 exactly when n + 2 \mid 14 (the backwards rule one way, the sum rule the other), that is, when n + 2 is one of \pm 1, \pm 2, \pm 7, \pm 14. Check n = 12: 14 \mid 154 = 14 \cdot 11.
  10. The linear-combination rule with x = 5, y = -7 gives d \mid 5(7n + 4) - 7(5n + 3) and that number is 20 - 21 = -1. So d \mid 1, d \ne 0, and the size bound gives |d| \le 1, so d = 1 or d = -1. \square
  11. Multiplying out (x + y)(x^2 - xy + y^2) gives x^3 - x^2y + xy^2 + x^2y - xy^2 + y^3 which is x^3 + y^3. The factor x^2 - xy + y^2 is an integer, so x + y \mid x^3 + y^3. \square
  12. 5^6 + 1 = (5^2)^3 + 1^3, so Exercise 11 with x = 25, y = 1 gives 26 \mid 5^6 + 1. Since 13 \mid 26, the transitive law gives 13 \mid 5^6 + 1. (Indeed 5^6 + 1 = 15{,}626 = 13 \cdot 1{,}202.)
  13. n^3 - 1 = (n - 1)(n^2 + n + 1), so n - 1 \mid n^3 - 1. For n \ge 3 the factor n - 1 is at least 2 and n^2 + n + 1 is at least 13, so n^3 - 1 is a product of two integers each greater than 1, and is not prime. (At n = 2, n^3 - 1 = 7 is prime, which is why the claim starts at 3.)
  14. 2^{12} - 1 = (2^6)^2 - 1^2, which factors as (2^6 - 1)(2^6 + 1) = 63 \cdot 65. Since 7 \mid 63 and 13 \mid 65, the multiple rule gives 7 \mid 2^{12} - 1 and 13 \mid 2^{12} - 1. (The number is 4095.)
  15. Write a = 5r + 2 and b = 5s + 4. Then ab - 3 = 25rs + 20r + 10s + 8 - 3 = 5(5rs + 4r + 2s + 1) and so 5 \mid ab - 3. \square
  16. Write a = 9r + 4 and b = 9s + 7. Then a + b - 2 = 9r + 9s + 9 = 9(r + s + 1) and ab - 1 = 81rs + 63r + 36s + 28 - 1 = 9(9rs + 7r + 4s + 3) so 9 divides both. \square
  17. a^2 + ab - 2b^2 = (a - b)(a + 2b), so the multiple rule applied to m \mid a - b gives m \mid a^2 + ab - 2b^2. \square
  18. False: a = 4, b = 6, c = 12. Then 4 \mid 12 and 6 \mid 12, but ab = 24 and 24 \nmid 12.
  19. False: a = 8, b = 4. Then 8 \mid 16 = b^2, but 8 \nmid 4.
  20. True. Write b - c = 1 \cdot (b + c) + (-2) \cdot c. Since a divides b + c and c, the linear-combination rule gives a \mid b - c. \square
  21. False: a = 2, b = 1, c = 1. Then 2 \mid 2 = b + c and 2 \mid 0 = b - c, but 2 \nmid 1. Adding the two hypotheses gives only a \mid 2b.
  22. Suppose instead that a \mid b + c. Together with a \mid b, the backwards rule gives a \mid c, which contradicts a \nmid c. So a \nmid b + c. \square
  23. Take a = 2, b = 2, c = 4: 2 \mid 2 and 2 \mid 4, but \displaystyle \frac{1}{2} \cdot 2 + \frac{1}{2} \cdot 4 = 3 and 2 \nmid 3. Here r = 1 and s = 2, so \displaystyle rx + sy = \frac{1}{2} + 1 = \frac{3}{2}, which is not an integer: the closure step fails.
  24. Multiplying out (x - y)(x^4 + x^3y + x^2y^2 + xy^3 + y^4) gives x^5 - y^5, since each middle term appears once with a plus sign and once with a minus sign. The second factor is an integer, so x - y \mid x^5 - y^5. \square
kg1128 · updated 2026-10-22 · CC-BY-SA-4.0