with sums of 38, 21, 16, 14, 13, 13, 11, and 10, respectively. The census-taker, seeing the house number, would know which of these was correct, unless the sum were the repeated number 13, in which case there are two possibilities. But because the two youngest children are not the same age, their ages cannot be 9, 2, and 2, and so must be 6, 6, and 1.
Least common multiple and greatest common divisor
In this section we’ll investigate two important numbers associated with the numbers a and b.The least common multiple
Let’s look at two situations. The first involves two ancient calendars:
In the first millennium ad the Mayans of Central America had two yearly calendars, one based on 260 days and the other on 365 days, which they then combined into a single ‘calendar round’ of 18,980 days (= 52 years). But where did this number come from?
The second situation involves two gears (see Figure 7):
7. Two gears with 90 and 54 teeth.
I have two rotating gears, with 90 and 54 teeth. When do the starting positions of these gears align?
The starting positions align whenever the number of teeth that have passed the starting position is simultaneously a multiple of 90 and a multiple of 54. So what are these multiples?
For the first gear, the first few multiples are
whereas for the second gear, they are
and the multiples that they have in common are the numbers in bold type—that is, 270 and 540. The smaller of these is 270, and we say that 270 is the ‘least common multiple’ of 90 and 54. So the starting positions align whenever 270 teeth have passed—that is, after every three rotations of the first gear and every five rotations of the second gear.
In general, m is a common multiple of the integers a and b if m is a multiple of both a and b, and the least common multiple is the smallest positive common multiple. If m is the least common multiple of a and b, we write . In the above example,
and further examples are
For the Ancient Mayans, the two calendars came together after each period of .
Many people meet least common multiples for the first time when they learn how to add fractions. For example, to add the fractions and we first put them over a common denominator:
We can now add these fractions directly to give , which then simplifies to . Here, the common denominator is the least common multiple, The greatest common divisor
Related to the least common multiple of two integers is their greatest common divisor.
The divisors of 90 are
and those of 54 are
so the ones that they have in common are 1, 2, 3, 6, 9, and 18. The largest of these is 18, so 18 is the ‘greatest common divisor’ of 90 and 54.
In general, d is a common divisor of the numbers a and b if d divides both a and b, and the greatest common divisor is the largest of these common divisors. If d is the greatest common divisor of a and b, we write ; it is sometimes called their highest common factor (written hcf). In the example above,
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:
