by Robin Wilson
and further examples are
If , we say that a and b are relatively prime or coprime: for example, 17 and 10 have no positive factors in common, except 1, and so are coprime.
Surprisingly, these ideas even arise in nature—in the life cycles of certain insects. In North America three types of cicada (see Figure 8) have life cycles of 7, 13, and 17 years, all of which are prime numbers. Is this a coincidence? Cicadas stay underground for most of their lives, and then emerge all at once for an orgy of eating, chirping, mating, laying eggs, and then dying. But when they do appear they’re vulnerable to predators (such as birds and certain wasps) with shorter life cycles of up to five years. If a cicada’s life cycle were 12 years, or some other composite number, then the likelihood of being consumed by a predator would be greatly increased. But because they’ve evolved life cycles of 7, 13, and 17 years, and because these numbers are all coprime to 2, 3, 4, and 5, the cicadas can more easily avoid that unhappy fate.
8. A periodical cicada.
A fundamental property of the greatest common divisor d of two numbers a and b is that we can always write d as a combination of a and b. To see what is involved, consider the following simple problem involving American coinage:
Jack and Jill have a number of quarters (25 cents) and dimes (10 cents), and Jack wishes to pay Jill 5 cents. How can this be done?
One way is for Jack to give Jill 1 quarter and for Jill to give Jack 2 dimes. We can write this as
Another way is for Jill to give Jack 1 quarter and for Jack to give Jill 3 dimes. We can write this as
Taking and and noting that , we can generalize these observations as follows:
If a and b are positive integers, and if , then there are integers m and n for which .
In particular, if a and b are coprime, then , and this result tells us that there are integers m and n for which
As above, the integers m and n can’t both be positive, and there are many possible choices for them: for example, and
We’ll conclude this section with an interesting connection between the least common multiple and the greatest common divisor and of two numbers a and b: this is
For example, if and , then , , and
In Chapter 3 we’ll explain why this happens.
Euclid’s algorithm
How can we calculate the greatest common divisor of two given numbers?
In Book VII of his Elements, Euclid presented a method for doing so which depends on an elementary, yet fundamental, result that’s known as the ‘division rule’. This tells us that if we’re given any integers a and b, then we can divide b by a to give an answer (called a ‘quotient’), usually with a remainder: for example, if we divide 34 by 10 we get a quotient of 3 and a remainder of 4, because
We notice that the remainder is less than 10, the number that we divided by.
Division rule: Given any positive integers a and b, there are unique numbers q (the quotient) and r (the remainder) with , where .
This result is illustrated in Figure 9. As a special case, if b is a multiple of a, then the remainder r is 0 and the quotient q is b/a.
9. The division rule.
Some important special cases of the division rule, which we’ll need later in this chapter, are as follows; they are illustrated in Figure 10:
10. Special cases of the division rule.
If , then or 1, so:
Every integer b has the form 2q (the even integers) or (the odd integers).
If , then , so:
Every integer b has the form 3q, , or .
If , then , so:
Every integer b has the form 4q, , , or ,
and so on.
We come now to Euclid’s algorithm. An algorithm is a finite procedure for solving a problem, step by step. It’s rather like a recipe in a cookery book or a set of road instructions for driving from one location to another. When we supply the appropriate input data (the ingredients or the two locations) and ‘turn the handle’, our output should be the required solution (such as a cake or a suitable route). Algorithms are named after the 9th-century Persian mathematician al-Khwārizmī.
Euclid’s algorithm for finding the greatest common divisor of two numbers uses the division rule over and over again. The following example, where we show that , illustrates the method. Here, the numbers in bold type are the original numbers 57 and 21 and the remainders that arise in the successive divisions.
We stop when we obtain a remainder of 0, and the greatest common divisor is then the last non-zero remainder, which here is 3. Figure 11 depicts this process.
11.
We can also use these same calculations to write gcd (57, 21) as a combination of 57 and 21, as we described earlier. To do so we work upwards from the last-but-one equation, substituting for the remainder at each step, as follows.
and substituting this into the last-but-one equation gives
Finally, by the first application of the division rule,
and substituting this into the previous equation gives
So , where and .
In general, we can find the greatest common divisor of any two positive integers a and b in the same way—by using the division rule repeatedly to find each quotient and remainder in turn, until we get a remainder of 0. Then:
The greatest common divisor gcd (a, b) is the last non-zero remainder.
We can then reverse the process to write gcd (a, b) as a combination of a and b. To do so, we start with the last-but-one equation and work upwards through the equations, as in the example we’ve just given.
How efficient is Euclid’s algorithm? Sometimes Euclid’s method works quickly and we find the highest common factor in a small number of steps. For example, to show that requires just three steps:
So (see Figure 12).
12. .
But sometimes it takes more steps—for example, when it is applied to successive numbers in the sequence
where each number is the sum of the previous two numbers: for example, . These numbers are usually named Fibonacci numbers after Leonardo Fibonacci of Pisa who mentioned them in a problem in the year 1202, although their origins are older than this. For example, using Euclid’s algorithm to find gcd (89, 55) requires nine steps (see Figure 13):
13. .
Here the greatest common divisor and every quotient (except the last) are all 1, and all the non-zero remainders are themselves Fibonacci numbers.
So sometimes Euclid’s algorithm works more quickly than at other times. But in spite of this, it is by far the most efficient algorithm for finding greatest common divisors in general.
Squares
Perfect squares feature throughout number theory. As we saw in Chapter 1, the Pythagoreans have been credited with noticing that adding the first few odd numbers always gives a square: for example,
They supposedly explained such results by drawing square diagrams similar to that in Figure 14, where the numbers of dots in the L-shaped regions are 1, 3, 5, 7, and 9. In fact, for any number k,
14. The sum of the first few odd numbers is a square.
Other results involving squares arise from our earlier special cases of the division rule. For example:
Every square has the form 4n or , for some integer n.
This is because every integer b has the form 2q or :
if , then ,
which has the form 4n with : for example, ;
if , then ,
which has the form with : for example, .
So if b is even then b2 has the form 4n, and if b is odd then b2 has the form .
An immediate consequence of this result is that none of the numbers
can be a square. This is because these numbers all have the form , for some integer n: for example, and .
But we can say a little more. We’ve just seen that if , then
But is the product of two consecutive integers (one odd and the other even), and so is even. It follows that is divisible by 8, and so:
The square of every odd nu
mber has the form , for some integer n.
We can also demonstrate this result geometrically: see Figure 15, for the case . Here, b2 dots are arranged as eight triangles with an extra dot in the centre. Now
15. If b is odd, then b2 has the form .
and so b2 has the form .
In Chapter 1 we saw that the squares from 12 to 102 end with 1, 4, 5, 6, 9, or 0. Is this true for all squares? By the division rule, every integer can be written as , where , and so
So the square of ends with the same digit as the square of r, and so must also be 1, 4, 5, 6, 9 or 0. It follows that no perfect square can end in 2, 3, 7, or 8.
We can also use the division rule to obtain results involving cubes. A single example will give the idea.
Every cube has the form .
This is because every integer b has the form , or :
if , then ,
which has the form 9n with : for example, ;
if , then ,
which has the form with : for example, ;
if , then ,
which has the form : for example, .
So if then b3 has the form 9n, if then b3 has the form , and if then b3 has the form .
We conclude this section by stating without proof an intriguing result that links squares and cubes. In Chapter 1 we asked whether the sum of the first few positive cubes must always be a perfect square. But it can be proved that, for any number n,
and so the result is indeed true: for example,
Divisor tests
In our decimal counting system we can write any whole number, such as 47,972, as a sum of powers of 10 (where 100 is taken to be 1):
and in general we can write any positive number in the form
Because our decimal system is a place-value system, we need to use only the ten digits
with the two 7s in 47,972 standing for 7000 and 70. We can therefore carry out our calculations in columns, with the columns representing units, tens, hundreds, thousands, …, as we move from right to left.
In a similar way, we can write any number as a sum of powers of 2 (the binary counting system used in computing), or of 12 (the duodecimal system used for feet and inches, and formerly in Britain for shillings and pence), or of any other integer greater than 1, and many statements about the decimal system have their analogues in these other systems too. For simplicity we’ll consider only decimal numbers here.
In this section we’ll see some tests that tell us very quickly whether a given positive number is divisible by the integers 2, 3, 4, 5, 8, 9, 10, 11, and 25, and we’ll also explain why they work. We’ll also show how to test for divisibility by some larger numbers.
As we saw in Chapter 1, we can easily test the number for divisibility by 10 and by 5 by checking its last digit, a0:
Divisibility by 10: n is divisible by 10 if and only if its last digit is 0.
Divisibility by 5: n is divisible by 5 if and only if its last digit is 0 or 5.
For example, 19,720 is divisible by both 10 and 5, and 19,725 is divisible by 5.
These are because if
then 10 divides all the powers of 10, except for , and so n is divisible by 10 if and only if 10 divides a0—that is, , and so n ends in 0. Likewise, 5 also divides all powers of 10, except for 100, and so n is divisible by 5 if and only if 5 divides a0—that is, or 5, and so n ends in 0 or 5.
We can likewise test for divisibility by 25 by checking its last two digits, a1 and a0:
Divisibility by 25: n is divisible by 25 if and only if its last two digits are 00, 25, 50, or 75.
For example, 19,725 is divisible by 25.
This is because 25 divides all the powers of 10, except for 101 and 100, and so n is divisible by 25 if and only if 25 divides the two-digit number —that is, n ends in 00, 25, 50, or 75.
In Chapter 1 we saw that.
Divisibility by 2: n is divisible by 2 if and only if its last digit is 2, 4, 6, 8, or 0.
For example, 19,726 is divisible by 2.
This is because 2 divides all the powers of 10, except for 100, and so n is divisible by 2 if and only if 2 divides a0—that is, its last digit is even.
We can likewise test for divisibility by 4 or by 8 by checking the last two or 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 101 and 100, and so n is divisible by 4 if and only if 4 divides the two-digit number a1a0. Likewise, 8 divides all the powers of 10, except for 102, 101, and 100, and so n is divisible by 8 if and only if 8 divides the three-digit number a2a1a0.
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 calcul
ation 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 at the bottom is the digital root 4, obtained by multiplying the digital roots 5 and 8. When the numbers at the top and bottom disagree, as here, the calculation is incorrect. When they agree, the calculation is usually correct.