Number Theory: A Very Short Introduction

three digits:

Divisibility by 4: n is divisible by 4 if and only if its last two digits are 00, 04, 08, …, 92, or 96.

Divisibility by 8: n is divisible by 8 if and only if its last three digits are 000, 008, 016, …, 984, or 992.

For example, 19,724 is divisible by 4 and 19,728 is divisible by 8.

These are because 4 divides all the powers of 10, except for 10¹ and 10⁰, and so n is divisible by 4 if and only if 4 divides the two-digit number a₁a₀. Likewise, 8 divides all the powers of 10, except for 10², 10¹, and 10⁰, and so n is divisible by 8 if and only if 8 divides the three-digit number a₂a₁a₀.

We next turn our attention to divisibility by 3 and by 9.

Divisibility by 3: n is divisible by 3 if and only if the sum of its digits is divisible by 3.

Divisibility by 9: n is divisible by 9 if and only if the sum of its digits is divisible by 9.

For example, 19,725 is divisible by 3 because the sum of its digits is , which is divisible by 3, and 19,728 is divisible by 9 because the sum of its digits is 27, which is divisible by 9.

These are because 3 and 9 divide all of the numbers 9, 99, 999, …, and so each power of 10 leaves a remainder of 1 when divided by 3 or 9. It follows that when

is divided by 3 or 9, the resulting remainder is simply the sum of its digits,

and so n is divisible by 3 or 9 if and only if this ‘digital sum’ is divisible by 3 or 9.

We can use a similar idea to test for divisibility by 11:

Divisibility by 11: n is divisible by 11 if and only if the alternating sum of its digits is divisible by 11.

Here the ‘alternating sum’ is . For example, 19,723 is divisible by 11 because its alternating sum is divisible by 11.

The method works because the powers of 10 leave remainders of 1 and −1 alternately when divided by 11, so n is divisible by 11 if and only if this alternating sum is divisible by 11.

We can test for divisibility by other numbers by combining these results. For example, we can test for divisibility by 6 by testing whether n is divisible by 2 and also by 3, and we can test for divisibility by 88 by testing whether n is divisible by 8 and also by 11. In general, if n is divisible by both a and b, where a and b are coprime, then n is divisible by , as long as .Casting out nines

We’ll conclude this chapter with an ancient method for checking the accuracy of an arithmetical calculation. Known as ‘Casting out nines’, it is based on the fact that a number and its digital sum leave the same remainder when divided by 9. The method seems to have developed in India around the year 1000, and was later transmitted by Islamic scholars to Europe where versions of it are still sometimes used—for example, in bookkeeping. It’s similar in idea to the final ‘check digit’ of a book’s 13-digit ISBN number, which is included to provide a check on the accuracy of the first twelve digits.

Consider a number such as 4567. Its remainder after division by 9 is the same as that of its digital sum which in turn is the same as that of its digital sum, . Similarly, the remainder when the number 6537 is divided by 9 is the same as that of its digital sum , which in turn is the same as that of its digital sum, . And in general, we can similarly reduce any given number n to a single-digit number, called its ‘digital root’, which is the remainder when we divide n by 9. (If the digital root is 9, we replace it by 0.)

In most cases, we can use these digital roots to verify the correctness (or otherwise) of an arithmetical calculation. To illustrate the idea we’ll start with the incorrect addition sum

Here the digital root of 4567 is 4 and of 6537 is 3, so the remainder on dividing the left-hand side by 9 is which is 7. But the digital root of 11,144 is 2, so the remainder on dividing the right-hand side by 9 is 2. Because these remainders disagree, the calculation must be incorrect—the correct answer is 11,104. And this happens in general: whenever the digital roots of the two sides differ, then we know (without carrying out the calculation) that the answer is wrong.

However, the method sometimes fails: for example, consider the addition sum

Here, the digital root of each side of the equation is 7, so the two digital roots of the two sides agree, even though the calculation is incorrect. In these cases, the correct and incorrect answers must always differ by a multiple of 9.

This method of casting out nines can be used as a check whenever we wish to add, subtract, or multiply whole numbers: in each case, we replace each number by its digital root, and check the same calculation on these digital roots. As an example of multiplication, consider the product

The digital roots of the numbers on the left-hand side are 5 and 8, and the digital root of their product is 4. But the digital root of the right-hand side is 3, so the digital roots disagree and the calculation is incorrect—the correct answer is 2047.

In medieval times, calculators would draw the diagram in Figure 16, where the numbers on the left and right are the digital roots 5 and 8, the number at the top is the digital root of the given answer, 3, and the number