Mathematics for the liberal arts (2013)

Part II. TWO PILLARS OF MATHEMATICS

Chapter 5. NUMBER THEORY

5.2 Divisibility

Of the four common operations on integers—addition, subtraction, multiplication, and division—division presents special difficulties. The reason is simple. When we add, subtract, or multiply integers, the result is an integer; but when we divide one integer by another, the result is not guaranteed to be an integer. Because of this, much of number theory is devoted to problems of division.

Definitions and Examples

Definition. For integers a and b, with a ≠ 0, we say that a divides b if there is some integer c such that b = ac. If a divides b, we write a|b. If a does not divide b, we write a b.

In other words, a divides b if b is a multiple of a.

EXAMPLE 5.1

(a) 7|343 because 343 = 7 · 49.

(b) 5 24 because there is no integer c such that 24 = 5c. Of course, 24 = 5 × 4.8, but 4.8 is not an integer.

(c) –31 (–33), because –33 = –3 · 11.

Simple Properties of Divisibility

In this section we will work out a few simple rules of divisibility, simple but useful. Some of them may seem obvious to you, but mathematicians like to prove everything, so we will proceed accordingly.

Let a, b, and c be integers, and suppose that a|b. Then a | bc.

Proof. Since a | b, there is some integer d such that b = ad. Then

By the definition, since there is an integer dc such that bc = a(dc), we have a | bc.

EXAMPLE 5.2

Suppose that x is some integer. Show that 7|343x.

Solution: This is a straightforward application of the last theorem. We saw above that 7|343. So applying the theorem, with a = 7, b = 343, and c = x, we conclude that 7|343x.

i. If a | b and a | c, then a | (b + c) and a | (b – c).

ii. If a | b and c | d, then ac | bd.

iii. If a | b and b | c, then a | c.

Important Note: Does this seem dry to you? Too abstract and formal? Do statements like “if a | b and c | d, then ac | bd” make your eyes glaze over? There is a cure. Pick numbers for the letters. Find numbers a and b so that adivides b. Find numbers c and d such that c divides d. Convince yourself that ac divides bd. If that isn’t enough, find some more examples. We are dealing with familiar numbers. If you do enough examples, this will make sense to you.

Proof. (i) Let a | b and a | c. Since a | b, there is some integer e such that b = ae. Since a | c, there is some integer f such that c = af. Thus

so a | (b + c). Similarly

so a | (b – c).

(ii) Let a | b and c | d. Since a | b, there is some integer e such that b = ae. Since c | d, there is some integer f such that d = cf. Using these last two facts, we have

So ac | bd.

(iii) Let a | b and b | e. Since a | b, there is some integer e such that b = ae. Since b | c, there is some integer f such that c = bf. Thus

So c = a(ef), which implies that a | c.

Definition. Let n be an integer. Then n is even if 2 | n, and n is odd if 2 n.

EXAMPLE 5.3

The sum of any two even numbers is even. Proof: Suppose that b and c are even numbers. We apply the result (i) above, with a = 2. We have 2 | b and 2 | c, so 2 | (b + c), i.e., b + c is even.

EXAMPLE 5.4

Let x be even, and y be divisible by 3. Then xy is divisible by 6.

Solution: We have 2 | x and 3 | y. Applying result (ii) above, with a = 2, b = x, c = 3, and d = y, we find that (2 · 3) | xy; in other words, 6 divides xy.

EXAMPLE 5.5

Any integer divisible by 10 is divisible by 5.

Solution: Suppose that x is divisible by 10. Applying (iii) above, with a = 5, b = 10, and c = x, we conclude that 5 | x.

EXAMPLE 5.6

An integer is divisible by 5 if and only if its last digit is 0 or 5.

Solution: Let’s assume that n is a positive integer. If this is true for positive integers, it is true for all integers, since n and – n have the same divisors.

Let a be the last digit of n. We will see that 5 divides n precisely when 5 divides a. First note that n – a ends in 0, so is divisible by 10. By the last example, 5 also divides n – a, say n – a = 5b. So we have n = 5b + a. Using (i) above:

If 5 divides a, then 5 divides n = 5b + a.

If 5 divides n, then 5 divides a = n – 5b.

So 5 | n if, and only if, 51 a. Since a is a digit, i.e., between 0 and 9, it is divisible by 5 precisely when it is 0 or 5.

Division and Remainders

In the last section, we introduced the notion of divisibility: For two integers a and b, either b | a or b a. But this is not the end of the story.

The Division Theorem. Let a and b be integers, with b positive. Then there exist unique integers q and r such that

i. a = bq + r, and

ii. 0 ≤ r < b.

Does this look familiar? Think q for quotient and r for remainder. This theorem is the basis for long division. Of course, b divides a if and only if r = 0.

EXAMPLE 5.7

Apply the Division Theorem to a = 237 and b = 13.

Solution: If you remember your long division, you can divide 237 by 13, and get quotient 18, remainder 3. So let q = 18 and r = 3. We can verify the two statements of the theorem:

i. 237 = 13 · 18 + 3

ii. 0 ≤ 3 < 13.

But the theorem says more than this; it says that q and r are unique. There is only one choice of q and r that satisfy the two conditions above. (Unlike in our everyday, imprecise language, in mathematics unique doesn’t mean “unusual” or “very.” It means one. It is from a French word, meaning “single.”)

There are other choices of q and r that satisfy condition (i) above. Here are two:

Let q = 17 and r = 16. You can check that 237 = 13 · 17 + 16.

Let q = 19 and r = – 10. Check that 237 = 13 · 19 + (– 10).

You can probably see that there are many other choices for q and r, but none of them also satisfies the condition 0 ≤ r < 13. That is why we can talk about the quotient and the remainder. This uniqueness will be important to us in future sections.

Many people find long division hard. Even mathematicians get lazy. Can’t we do this on a calculator? Simple calculators do not find quotients and remainders for us, but they will divide numbers. We can use this, with an alternate version of part (i) of the theorem:

(Make sure you understand how this follows from (i).)

Looking at our last example, use your calculator to divide 237 by 13. Your result depends on how many digits your calculator displays, but will be something like 18.230769. This gives the quotient as 18. Now

Hence r/13 must be (approximately) .230769. So if we multiply .230769 by 13, we should get r. The result may be something like r = 2.999999. Since we know r to be an integer, we round to r = 3.

EXAMPLE 5.8

Show that the product of two odd numbers is odd.

Solution: The Division Theorem gives us a useful way to think about odd numbers. It tells us that any number n can be written as n = 2x or n = 2x + 1, depending on its remainder. Numbers of the form 2x are even, and numbers of the form 2x + 1 are odd. Suppose then that we have two odd numbers, say, 2x + 1 and 2y + 1. Then their product is (2x + 1)(2y + 1) = 4xy + 2x + 2y + 1 = 2(2xy + x + y) + 1. Hence, the product is of the form 2z + 1, with z = 2xy + x + y, so is odd.

Finally, if you look at the statement of the Division Theorem, you will see that a can be any integer, even a negative one. How does this work? Let us consider an example: a = – 14, b = 3. Since 14 has remainder 2 upon division by 3, you may think that – 14 has remainder – 2. But the remainder has to be 0,1 or 2, so this can’t work. In fact, we have –14 = 3 · (– 5) + 1 and 0 ≤ 1 < 3, so the uniqueness part of the theorem tells us that the quotient is –5 and the remainder is 1. In general, we have to be careful with negative integers here. We will later see how to make them easier to deal with.

EXERCISES

5.1 True or false: the sum of any two odd numbers is odd.

5.2 Does 7 divide 6998? (Hint: add 2.)

5.3 In one of our examples, we stated a divisibility rule for 5, i.e., a rule that allows us to quickly check whether a number is divisible by 5. Find divisibility rules for each of the following.

a) 2

b) 25 (Hint: look at the last two digits.)

c) 4

5.4 Using the notation of the Division Theorem, find q and r for each of the following.

a) a = 82, b = 7

b) a = 34526, b = 23

c) a = –17, b = 5

5.5 You have two numbers. Dividing the larger by the smaller gives you a quotient of 3 and a remainder of 8. If the sum of the numbers is 80, what are the numbers?

5.6 The remaining problems give assertions about arbitrary integers a, b, c, and d. For each, decide whether it is always true. If it can be false, give a counterexample, a selection of integers for which the statement is false.

a) If a | b and a | (b + c), then a | c.

b) If a | b and a (b + c), then a c.

c) If a | c and b | c, then ab | c.

d) If a | bc and a b, then a | c.

e) If a | b and b | a, then a = b.

f) If a | b and ac | bd, then c | d.