math.wiki
Logic, proof and discrete math › Introductory number theory › Divisibility as a relation
Open on the map
Discrete Mathematics and Proof

Divisibility as a relation

Inside the integers, where dividing does not always work, how do we say exactly that one number goes into another, and what kind of comparison between two numbers is that?

You need
Divisibility and primesGrades 4 to 6
Unlocks
The division algorithmDiscrete Mathematics and Proof
Where you are 8 in Introductory number theory
Logic, proof and discrete math6
Introductory number theory8
Divisibility as a relation
Modular arithmetic7The division algorithmNumbers in other basesThe Euclidean algorithm and coprime numbers▾ Show all 8 (3 more)

Why this exists

Add, subtract or multiply two integers and you get an integer. Divide them and you often do not: 12 \div 5 = 2.4 has left the integers. Number theory needs a way to say “3 goes into 12 evenly” that never leaves them.

The way out is to ask about multiplication instead: 12 is 3 times some integer. Written this way, divisibility becomes a relation: a yes-or-no comparison between two integers, like a \le b, with rules of its own that can be proved. The earlier work on factors (Divisibility and primes, and listing factors in Factors and multiples) used the idea for positive whole numbers; here it is made exact for every integer.

Definition

For integers a and b, we say a divides b, and write a \mid b, when there is an integer k with

b = ak.

Then a is a divisor (or factor) of b, and b is a multiple of a. When no such integer exists we write a \nmid b, “a does not divide b”. So 3 \mid 12 because 12 = 3 \cdot 4, and 5 \nmid 12 because 5 \cdot 2 = 10 and 5 \cdot 3 = 15 step over 12. Nothing in the definition excludes a = 0 or negative numbers; those cases are settled below. An integer n is even exactly when 2 \mid n, which is the definition used in Proving statements about even and odd numbers.

A statement, not a number. a \mid b is a sentence. It is either true or false, the way 7 < 2 is false. The fraction \displaystyle \frac{b}{a} is a number. They answer different questions: 3 \mid 12 says “yes, 3 goes in evenly”, and \displaystyle \frac{12}{3} says “it goes in 4 times”. So “3 \mid 12 = 4” means nothing, and 3 \mid 12 is not “\displaystyle \frac{3}{12}” either. Notice the order: in a \mid b the divisor comes first, in \displaystyle \frac{b}{a} it comes second.

Intuition

Start at 0 and step along the number line by a in both directions. You land on \ldots, -2a, -a, 0, a, 2a, \ldots, the multiples of a. Then a \mid b says that b is one of the landing spots. Every step size lands on 0, size 1 lands everywhere, and size 0 never leaves 0.

For one positive number, its divisors and the relation fit in one picture.

30 6 10 15 2 3 5 1
Figure 1The positive divisors of 30. A line runs up from a to b when a \mid b with no divisor between; a \mid b exactly when an upward path leads from a to b.

Only twelve true statements are drawn. Others, such as 2 \mid 30, are read off as upward paths (2 to 6 to 30), which the transitive property below makes legitimate.

Results

For all integers a, b, c and n:

  • Edge cases. 1 \mid n, n \mid n, and n \mid 0. But 0 \mid b only when b = 0.
  • Signs do not matter. If a \mid b, then -a \mid b, a \mid -b and -a \mid -b.
  • Reflexive. a \mid a.
  • Transitive. If a \mid b and b \mid c, then a \mid c.
  • Not symmetric. a \mid b does not force b \mid a: 2 \mid 6 but 6 \nmid 2.
  • Size bound. If a \mid b and b \ne 0, then |a| \le |b|.
  • Antisymmetric on the positive integers. If a, b > 0, a \mid b and b \mid a, then a = b. Over all integers, a \mid b and b \mid a give a = b or a = -b.

A further rule, that a \mid b and a \mid c give a \mid bx + cy for all integers x, y, is proved and used in Proving statements about divisibility.

Why it is true

Each proof writes out what the definition says and finds the integer k it asks for.

Proof of the edge cases. n = 1 \cdot n, n = n \cdot 1 and 0 = n \cdot 0, with n, 1 and 0 integers, so 1 \mid n, n \mid n and n \mid 0. If 0 \mid b, then b = 0 \cdot k = 0 for some integer k; and 0 \mid 0 holds because 0 = 0 \cdot 0. \square

Proof that signs do not matter. Suppose b = ak with k an integer. Then b = (-a)(-k), -b = a(-k) and -b = (-a)k, and -k is an integer. \square

Reflexivity is the case n \mid n above.

Proof of transitivity. Suppose a \mid b and b \mid c. Then b = ak and c = bm for some integers k and m. Substituting the first into the second,

c = (ak)m = a(km),

by the associative property of multiplication. A product of integers is an integer, so km is an integer, and c = a(km) says a \mid c. \square

Proof of the size bound. Suppose b = ak with k an integer and b \ne 0. Then k \ne 0, since k = 0 would make b = 0. A nonzero integer has |k| \ge 1, so

|b| = |a|\,|k| \ge |a| \cdot 1 = |a|. \qquad \square

Proof of antisymmetry. Suppose a \mid b and b \mid a. If b = 0, then 0 \mid a, so a = 0 = b. If b \ne 0, then a \ne 0 too, since 0 \mid b would force b = 0. Now both are nonzero, and the size bound applied twice gives |a| \le |b| and |b| \le |a|, so |a| = |b|, which means a = b or a = -b. When a and b are both positive, a = -b is impossible, so a = b. \square

Worked examples

Example 1

Deciding true or false

Decide each statement and justify it from the definition: (a) 6 \mid 42, (b) 42 \mid 6, (c) 9 \mid 0, (d) 0 \mid 9, (e) -7 \mid 35, (f) 8 \mid -20, (g) 0 \mid 0.

Solution

(a) True: 42 = 6 \cdot 7.

(b) False: 6 = 42k would need \displaystyle k = \frac{1}{7}, not an integer.

(c) True: 0 = 9 \cdot 0.

(d) False: 0 \cdot k = 0 for every integer k, never 9.

(e) True: 35 = (-7)(-5), and -5 is an integer.

(f) False: 8 \cdot (-3) = -24 and 8 \cdot (-2) = -16, and -20 falls strictly between two consecutive multiples of 8, so no integer k gives 8k = -20.

(g) True: 0 = 0 \cdot 0. Here the fraction \displaystyle \frac{0}{0} is undefined, yet the statement 0 \mid 0 is true. This is why divisibility is defined by multiplication and not by asking whether \displaystyle \frac{b}{a} is an integer.

Example 2

Statement or number

Write each in notation and give its value: (a) “91 has 7 as a factor”, (b) “the number of times 7 goes into 91”, (c) “5 is a divisor of 91”.

Solution

(a) This is the statement 7 \mid 91. Its value is true, because 91 = 7 \cdot 13.

(b) This is the number \displaystyle \frac{91}{7}. Its value is 13. It makes no sense to call 13 true or false.

(c) This is the statement 5 \mid 91. Its value is false: 5 \cdot 18 = 90 and 5 \cdot 19 = 95, so 5 \nmid 91, although the number \displaystyle \frac{91}{5} = 18.2 exists.

Example 3

Every divisor of 30

List every integer a with a \mid 30, and explain why the list is complete.

Solution

By the size bound, a \mid 30 forces |a| \le 30, so only finitely many integers can qualify. By the sign rule, a divides 30 exactly when -a does, so it is enough to find the positive ones and attach both signs. Testing 1 through 30, the positive divisors are 1, 2, 3, 5, 6, 10, 15, 30 (for instance 30 = 5 \cdot 6, while 4 \nmid 30 since 4 \cdot 7 = 28 and 4 \cdot 8 = 32). So the divisors of 30 in \mathbb{Z} are

\pm 1,\ \pm 2,\ \pm 3,\ \pm 5,\ \pm 6,\ \pm 10,\ \pm 15,\ \pm 30,

sixteen integers in all. The figure shows the eight positive ones.

Example 4

What transitivity forces

An integer n satisfies 15 \mid n. Which of the divisors 1, 2, 3, 5, 6, 10, 15, 30 of 30 must divide n?

Solution

Each of 1, 3, 5, 15 divides 15, and 15 \mid n, so by transitivity each divides n. In the figure these are exactly the divisors with an upward path to 15.

The other four need not. One example settles all of them: take n = 15, which satisfies 15 \mid 15. Then 2 \nmid 15 (2 \cdot 7 = 14, 2 \cdot 8 = 16), 6 \nmid 15 (6 \cdot 2 = 12, 6 \cdot 3 = 18), 10 \nmid 15 (10 \cdot 1 = 10, 10 \cdot 2 = 20), and 30 \nmid 15 by the size bound.

Example 5

Dividing each other

Find every integer b with 6 \mid b and b \mid 6.

Solution

By antisymmetry over the integers, 6 \mid b and b \mid 6 give b = 6 or b = -6. Both work: 6 = 6 \cdot 1 in both directions, and -6 = 6 \cdot (-1), 6 = (-6)(-1). So the answer is b = \pm 6. On the positive integers the only answer is 6 itself, which is what “antisymmetric” means.

Example 6

A shifted divisor

Find every integer n with (n - 3) \mid 10.

Solution

The divisor here is the integer n - 3, so it must be one of the divisors of 10. By the size bound and the sign rule, those are \pm 1, \pm 2, \pm 5, \pm 10. Setting n - 3 equal to each and adding 3:

n - 3nn - 3n
14-12
25-21
58-5-2
1013-10-7

So n \in \{-7, -2, 1, 2, 4, 5, 8, 13\}. Check one: n = -7 gives -10 \mid 10, true since 10 = (-10)(-1). And n = 3 is out, since 0 \nmid 10.

Example 7

Three numbers in a circle

Prove: if a, b, c are positive integers with a \mid b, b \mid c and c \mid a, then a = b = c.

Solution

Proof. From a \mid b and b \mid c, transitivity gives a \mid c. Together with c \mid a, and since a and c are positive, antisymmetry gives a = c. Now b \mid c reads b \mid a, and with a \mid b, antisymmetry gives a = b. So a = b = c. \square

Positivity matters: a = 2, b = -2, c = 2 meets all three conditions.

Boundaries

  • The integer k carries the definition. If k were allowed to be any rational number, every nonzero number would divide every number (\displaystyle 5 = 3 \cdot \frac{5}{3}), and the relation would say nothing. Divisibility is a relation on \mathbb{Z}.
  • Not the same as “\displaystyle \frac{b}{a} is an integer”. The two agree when a \ne 0. When a = 0 the fraction is undefined, while 0 \mid 0 is true and 0 \mid b is false for b \ne 0.
  • The size bound needs b \ne 0. Every integer divides 0, so 7 \mid 0 although |7| > |0|.
  • Antisymmetry needs a sign condition. Over all integers, 3 \mid -3 and -3 \mid 3 with 3 \ne -3. Only “a = \pm b” survives.
  • Not every pair compares. Unlike \le, two positive integers may be incomparable: 2 \nmid 3 and 3 \nmid 2. In the figure, 6 and 10 have no path between them.

Where this goes next

The same reflexive, transitive, antisymmetric pattern appears for \le and for “is a subset of”; Relations and their properties: reflexive, symmetric, antisymmetric, transitive names these properties for any relation and studies them together. The rules for combining divisibility facts, sums, multiples and products, are proved in Proving statements about divisibility. When a \nmid b, The division algorithm measures by how much it fails, with a remainder, and that leads to the The Euclidean algorithm and coprime numbers, to Modular arithmetic and to the fundamental-theorem-of-arithmetic, which explains the shape of the figure: 30 = 2 \cdot 3 \cdot 5, and each divisor is a choice of which of the three primes to include.

Exercises

Reading the definition

  1. True or false, with a reason from the definition: (a) 9 \mid 63, (b) 63 \mid 9, (c) -8 \mid 56, (d) 12 \mid -54, (e) 0 \mid 17, (f) 17 \mid 0, (g) 1 \mid -40.
  2. Write each sentence in notation and decide it: (a) “45 is a multiple of 15”, (b) “7 is a factor of 60”, (c) “-4 is a divisor of 0”.
  3. Say whether each is a statement or a number, and give its value: 8 \mid 72, \displaystyle \frac{72}{8}, 72 \mid 8, \displaystyle \frac{8}{72}.
  4. For each true statement, find the integer k the definition asks for: (a) 13 \mid 91, (b) -6 \mid 48, (c) 11 \mid 0, (d) 0 \mid 0. In which case is k not determined?
  5. List every integer divisor of 20.
  6. Find every integer n with (n + 4) \mid 6.

The relation and its diagram

  1. Find every pair of integers a, b with a \mid b, b \mid a and a + b = 10.
  2. Give two positive integers, neither of which divides the other, and say what this shows about divisibility compared with \le.
  3. An integer n satisfies 21 \mid n. Which of 1, 3, 7, 14, 21, 42 must divide n?
  4. Find every integer a with a \mid 1.
  5. (a) Is there an integer a with a \mid 45 and a > 45? (b) Is there one with a \mid 0 and a > 45?
  6. Draw the diagram for the positive divisors of 12, in the style of the figure, and list its lines.
  7. Among the positive divisors of 30, how many pairs (a, b) with a \ne b have a \mid b? How many of them are drawn as lines in the figure?

Reasoning and proof

  1. Prove that for all integers a and b, a \mid b if and only if |a| \mid |b|.
  2. Prove that if a \mid b, b \mid c and c \mid d, then a \mid d.
  3. Prove that the only integers that divide every integer are 1 and -1.
  4. Prove: if a and b are positive integers with a \mid b and b < 2a, then a = b.
  5. Refute with a counterexample: “If a \mid c and b \mid c, then ab \mid c.”
  6. Ebo says that for positive integers, a \mid b implies a \le b. Mael says that for positive integers, a \le b implies a \mid b. Decide who is right, with a proof or a counterexample.
  7. Prove that a nonzero integer has finitely many divisors, and an even number of them.
  8. The figure has no line from 2 to 30, though 2 \mid 30. Explain why no information is lost.
  9. Prove: if a \mid b and |b| < |a|, then b = 0.
Answers
  1. (a) True, 63 = 9 \cdot 7. (b) False, 9 = 63k needs \displaystyle k = \frac{1}{7}. (c) True, 56 = (-8)(-7). (d) False, 12 \cdot (-5) = -60 and 12 \cdot (-4) = -48, so -54 lies strictly between consecutive multiples. (e) False, 0 \cdot k = 0 \ne 17. (f) True, 0 = 17 \cdot 0. (g) True, -40 = 1 \cdot (-40).
  2. (a) 15 \mid 45, true: 45 = 15 \cdot 3. (b) 7 \mid 60, false: 7 \cdot 8 = 56, 7 \cdot 9 = 63. (c) -4 \mid 0, true: 0 = (-4) \cdot 0.
  3. 8 \mid 72 is a statement, true (72 = 8 \cdot 9). \displaystyle \frac{72}{8} is the number 9. 72 \mid 8 is a statement, false (size bound). \displaystyle \frac{8}{72} is the number \displaystyle \frac{1}{9}.
  4. (a) k = 7. (b) k = -8, since 48 = (-6)(-8). (c) k = 0. (d) Every integer k works, since 0 = 0 \cdot k; this is the case where k is not determined. When a \ne 0, k is the one number \displaystyle \frac{b}{a}.
  5. \pm 1, \pm 2, \pm 4, \pm 5, \pm 10, \pm 20, twelve integers. The size bound limits the search to |a| \le 20, and the sign rule pairs each positive divisor with its negative.
  6. n + 4 must be one of \pm 1, \pm 2, \pm 3, \pm 6, so n \in \{-10, -7, -6, -5, -3, -2, -1, 2\}. (n = -4 is excluded, since 0 \nmid 6.)
  7. Only a = b = 5. Antisymmetry over the integers gives a = b or a = -b. If a = -b, then a + b = 0 \ne 10; if a = b, then 2a = 10, so a = 5, and 5 \mid 5 checks.
  8. For example 4 and 6: 6 = 4k needs \displaystyle k = \frac{3}{2}, and 4 = 6k needs \displaystyle k = \frac{2}{3}. Any two integers compare under \le, but not under divisibility.
  9. 1, 3, 7, 21 must, by transitivity, since each divides 21. 14 and 42 need not: n = 21 satisfies 21 \mid 21, while 14 \nmid 21 (14 \cdot 1 = 14, 14 \cdot 2 = 28) and 42 \nmid 21 (size bound).
  10. a = 1 or a = -1. a \ne 0 because 0 \nmid 1, and the size bound gives |a| \le 1; both 1 = 1 \cdot 1 and 1 = (-1)(-1) check.
  11. (a) No: the size bound gives |a| \le 45. (b) Yes, for example 46, since 0 = 46 \cdot 0. The size bound needs b \ne 0.
  12. Rows from the bottom: 1; 2, 3; 4, 6; 12. Seven lines: 1 to 2, 1 to 3, 2 to 4, 2 to 6, 3 to 6, 4 to 12, 6 to 12. There is no line from 3 to 4, since 3 \nmid 4, and none from 2 to 12, since 4 sits between them.
  13. 19 pairs, of which 12 are lines. The other 7 are upward paths of more than one line: (1, 6), (1, 10), (1, 15), (2, 30), (3, 30), (5, 30) and (1, 30).
  14. Proof. Suppose b = ak with k an integer. Then |b| = |a|\,|k| and |k| is an integer, so |a| \mid |b|. Conversely suppose |b| = |a|\,m with m an integer. Write a = s|a| and b = t|b| with s, t \in \{1, -1\}; then |a| = sa because s^2 = 1, and b = t|a|m = a(stm), with stm an integer. So a \mid b. \square
  15. Proof. Transitivity on a \mid b and b \mid c gives a \mid c; transitivity again on a \mid c and c \mid d gives a \mid d. (Directly: b = ak, c = bm, d = cp give d = a(kmp).) \square
  16. Proof. 1 and -1 divide every integer n, since n = 1 \cdot n = (-1)(-n). Conversely, if a divides every integer, then a \mid 1. So a \ne 0 and the size bound gives |a| \le 1, which leaves a = 1 or a = -1. \square
  17. Proof. Write b = ak with k an integer. Since a, b > 0, \displaystyle k = \frac{b}{a} > 0, so k \ge 1. From b < 2a, ak < 2a, and dividing by the positive number a gives k < 2. The only integer with 1 \le k < 2 is k = 1, so b = a. \square
  18. a = 4, b = 6, c = 12: 4 \mid 12 and 6 \mid 12, but ab = 24 and 24 \nmid 12 by the size bound.
  19. Ebo is right. Proof. If a \mid b with b > 0, then b \ne 0, and the size bound gives a = |a| \le |b| = b. \square Mael is wrong: 2 \le 3 but 2 \nmid 3.
  20. Proof. Let b \ne 0. If a \mid b, the size bound gives |a| \le |b|, so every divisor is among the finitely many integers from -|b| to |b|. Since 0 \nmid b, each divisor a is nonzero, so a \ne -a, and by the sign rule -a is a divisor too. The divisors split into pairs \{a, -a\}, so their number is even. \square
  21. The path 2 to 6 to 30 records 2 \mid 6 and 6 \mid 30, and transitivity turns that into 2 \mid 30. Every true statement a \mid b among the divisors is an upward path, so drawing only the lines with nothing between keeps the diagram readable and loses nothing.
  22. Proof. Suppose a \mid b and b \ne 0. The size bound gives |a| \le |b|, which contradicts |b| < |a|. So b = 0. \square
kg1128 · updated 2026-10-22 · CC-BY-SA-4.0