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
