8.1: Divisibility
- Page ID
- 48331
The nature of number theory emerges as soon as we consider the divides relation.
Definition \(\PageIndex{1}\)
\(a\) divides \(b\) (notation \(a \mid b\)) iff there is an integer \(k\) such that
\[\nonumber ak = b.\]
The divides relation comes up so frequently that multiple synonyms for it are used all the time. The following phrases all say the same thing:
- \(a \mid b,\)
- \(a \text{ divides } b,\)
- \(a \text{ is a } \textit{divisor} \text{ of } b,\)
- \(a \text{ is a } \textit{factor} \text{ of } b,\)
- \(b \text{ is } \textit{divisible} \text{ by } a,\)
- \(b \text{ is a } \textit{multiple} \text{ of } a.\)
Some immediate consequences of Definition 8.1.1 are that for all \(n\)
\[\nonumber n \mid 0, \quad n \mid n, \text{ and } \quad \pm 1 \mid n.\]
Also,
\[\nonumber 0 \mid n \text{ IMPLIES } n = 0.\]
Dividing seems simple enough, but let’s play with this definition. The Pythagoreans, an ancient sect of mathematical mystics, said that a number is perfect if it equals the sum of its positive integral divisors, excluding itself. For example, \(6 = 1 + 2 + 3\) and \(28 = 1 + 2 + 4 + 7 + 14\) are perfect numbers. On the other hand, 10 is not perfect because \(1 + 2 + 5 = 8\), and 12 is not perfect because \(1 + 2 + 3 + 4 + 6 = 16\). Euclid characterized all the even perfect numbers around 300 BC (Problem 8.2). But is there an odd perfect number? More than two thousand years later, we still don’t know! All numbers up to about \(10^{300}\) have been ruled out, but no one has proved that there isn’t an odd perfect number waiting just over the horizon.
So a half-page into number theory, we’ve strayed past the outer limits of human knowledge. This is pretty typical; number theory is full of questions that are easy to pose, but incredibly difficult to answer. We’ll mention a few more such questions in later sections.1
Facts about Divisibility
The following lemma collects some basic facts about divisibility
Lemma 8.1.2.
- If \(a \mid b\) and \(b \mid c\), then \(a \mid c\).
- If \(a \mid b\) and \(a \mid c\), then \(a \mid sb + tc\) for all \(s\) and \(t\).
- For all \(c \neq 0\), \(a \mid b\) if and only if \(ca \mid cb\).
Proof. These facts all follow directly from Definition 8.1.1. To illustrate this, we’ll prove just part 2:
Given that \(a \mid b\), there is some \(k_1 \in \mathbb{Z}\) such that \(ak_1 = b\). Likewise, \(ak_2 = c\), so
\[\nonumber sb \pm tc = s(k_1a) + t(k_2a) = (sk_1 + tk_2)a.\]
Therefore \(sb + tc = k_3a\) where \(k_3 ::= (sk_1 + tk_2)\), which means that
\[\nonumber a \mid sb+tc. \quad \blacksquare\]
A number of the form \(sb + tc\) is called an integer linear combination of \(b\) and \(c\), or, since in this chapter we’re only talking about integers, just a linear combination. So Lemma 8.1.2.2 can be rephrased as
If \(a\) divides \(b\) and \(c\), then \(a\) divides every linear combination of \(b\) and \(c\).
We’ll be making good use of linear combinations, so let’s get the general definition on record:
Definition \(\PageIndex{3}\)
An integer \(n\) is a linear combination of numbers \(b_0, \ldots, b_k\) iff
\[\nonumber n = s_0b_0 + s_1b_1 + \cdots + s_kb_k\]
for some integers \(s_0, \ldots, s_k\).
When Divisibility Goes Bad
As you learned in elementary school, if one number does not evenly divide another, you get a “quotient” and a “remainder” left over. More precisely:
Theorem \(\PageIndex{4}\)
[Division Theorem]2 Let \(n\) and \(d\) be integers such that \(d>0\). Then there exists a unique pair of integers \(q\) and \(r\), such that
\[\label{8.1.1} n = q \cdot r \text{ AND } 0 \leq r < d \]
The number \(q\) is called the quotient and the number \(r\) is called the remainder of \(n\) divided by \(d\). We use the notation \(\text{qcnt}(n, d)\) for the quotient and \(\text{rem}(n, d)\) for the remainder. For example, \(\text{qcnt}(2716, 10) = 271\) and \(\text{rem}(2716, 10) = 6\), since \(2716 = 271 \cdot 10 + 6\). Similarly, \(\text{rem}(-11, 7) = 3\), since \(-11 = (-2) \cdot 7 + 3\).
There is a remainder operator built into many programming languages. For example, “32 % 5” will be familiar as remainder notation to programmers in Java, C, and C++; it evaluates to \(\text{rem}(32, 5) = 2\) in all three languages. On the other hand, these and other languages treat remainders involving negative numbers inconsistently, so don’t be distracted by your programming language’s behavior, and remember to stick to the definition according to the Division Theorem 8.1.4.
The remainder on division by \(n\) is a number in the (integer) interval from 0 to \(n - 1\). Such intervals come up so often that it is useful to have a simple notation for them.
\[\nonumber \begin{array}{ll}
(k . . n)::= & \{i \mid k<i<n\}, \\
(k . . n]::= & (k, n) \cup\{n\}, \\
{[k . . n)::=} & \{k\} \cup(k, n), \\
{[k . . n]::=} & \{k\} \cup(k, n) \cup\{n\}=\{i \mid k \leq i \leq n\}.
\end{array}\]
Die Hard
Die Hard 3 is just a B-grade action movie, but we think it has an inner message: everyone should learn at least a little number theory. In Section 5.4.4, we formalized a state machine for the Die Hard jug-filling problem using 3 and 5 gallon jugs, and also with 3 and 9 gallon jugs, and came to different conclusions about bomb explosions. What’s going on in general? For example, how about getting 4 gallons from 12- and 18-gallon jugs, getting 32 gallons with 899- and 1147-gallon jugs, or getting 3 gallons into a jug using just 21- and 26-gallon jugs?
It would be nice if we could solve all these silly water jug questions at once. This is where number theory comes in handy.
A Water Jug Invariant
Suppose that we have water jugs with capacities \(a\) and \(b\) with \(b \geq a\). Let’s carry out some sample operations of the state machine and see what happens, assuming the \(b\)-jug is big enough:
\[\nonumber \begin{array}{l}
(0,0) & \rightarrow(a, 0) & \text { fill first jug } \\
& \rightarrow(0, a) & \text { pour first into second }\\
& \rightarrow(a, a) & \text { fill first jug } \\
& \rightarrow(2 a-b, b) & \text { pour first into second (assuming } 2 a \geq b) \\
& \rightarrow(2 a-b, 0) & \text { empty second jug }\\
&\rightarrow(0,2 a-b) & \text { pour first into second } \\
& \rightarrow(a, 2 a-b) & \text { fill first }\\
& \rightarrow(3 a-2 b, b) & \text { pour first into second (assuming } 3 a \geq 2 b)
\end{array}\]
What leaps out is that at every step, the amount of water in each jug is a linear combination of \(a\) and \b\). This is easy to prove by induction on the number of transitions:
Lemma 8.1.5 (Water Jugs). In the Die Hard state machine of Section 5.4.4 with jugs of sizes \(a\) and \(b\), the amount of water in each jug is always a linear combination of \(a\) and \(b\).
Proof. The induction hypothesis, \(P(n)\), is the proposition that after \(n\) transitions, the amount of water in each jug is a linear combination of \(a\) and \(b\).
Base case \((n = 0)\): \(P(0)\) is true, because both jugs are initially empty, and \(0 \cdot a + 0 \cdot b = 0\).
Inductive step: Suppose the machine is in state \((x, y)\) after n steps, that is, the little jug contains x gallons and the big one contains \(y\) gallons. There are two cases:
If we fill a jug from the fountain or empty a jug into the fountain, then that jug is empty or full. The amount in the other jug remains a linear combination of \(a\) and \(b\). So \(P(n+1\) holds.
Otherwise, we pour water from one jug to another until one is empty or the other is full. By our assumption, the amount \(x\) and \(y\) in each jug is a linear combination of \(a\) and \(b\) before we begin pouring. After pouring, one jug is either empty (contains 0 gallons) or full (contains \(a\) or \(b\) gallons). Thus, the other jug contains either \(x + y\) gallons, \(x + y - a\), or \(x + y - b\) gallons, all of which are linear combinations of \(a\) and \(b\) since \(x\) and \(y\) are. So \(P(n+1\) holds in this case as well.
Since \(P(n+1\) holds in any case, this proves the inductive step, completing the proof by induction. \(\quad \blacksquare\)
So we have established that the jug problem has a preserved invariant, namely, the amount of water in every jug is a linear combination of the capacities of the jugs. Lemma 8.1.5 has an important corollary:
Corollary. In trying to get 4 gallons from 12- and 18-gallon jugs, and likewise to get 32 gallons from 899- and 1147-gallon jugs,
Bruce will die!
Proof. By the Water Jugs Lemma 8.1.5, with 12- and 18-gallon jugs, the amount in any jug is a linear combination of 12 and 18. This is always a multiple of 6 by Lemma 8.1.2.2, so Bruce can’t get 4 gallons. Likewise, the amount in any jug using 899- and 1147-gallon jugs is a multiple of 31, so he can’t get 32 either. \(\quad \blacksquare\)
But the Water Jugs Lemma doesn’t tell the complete story. For example, it leaves open the question of getting 3 gallons into a jug using just 21- and 26-gallon jugs: the only positive factor of both 21 and 26 is 1, and of course 1 divides 3, so the Lemma neither rules out nor confirms the possibility of getting 3 gallons.
A bigger issue is that we’ve just managed to recast a pretty understandable question about water jugs into a technical question about linear combinations. This might not seem like a lot of progress. Fortunately, linear combinations are closely related to something more familiar, greatest common divisors, and will help us solve the general water jug problem.
1Don’t Panic—we’re going to stick to some relatively benign parts of number theory. These super-hard unsolved problems rarely get put on problem sets.
2This theorem is often called the “Division Algorithm,” but we prefer to call it a theorem since it does not actually describe a division procedure for computing the quotient and remainder.