Ganita Prakash II · Chapter 3 — Finding Common Ground

Sameeksha wants to tile a room 12 ft wide and 16 ft long with square tiles, all the same size, with sides a whole number of feet. She wants as few tiles as possible. What size should she buy?

For tiles to fit the 12 ft side exactly, the tile side must divide 12. For the 16 ft side, it must divide 16. So the side must be a common factor of 12 and 16.

The tile could be 1 ft, 2 ft or 4 ft. The bigger the tile, the fewer tiles are needed, so she picks 4 ft. Along the width there are 12 ÷ 4 = 3 tiles and along the length 16 ÷ 4 = 4 tiles, so 3 × 4 = 12 tiles in all.

The HCF. The Highest Common Factor (HCF) of two or more numbers is the greatest of their common factors. It is also called the Greatest Common Divisor (GCD). Here the HCF of 12 and 16 is 4.

Another example. Lekhana buys 84 kg of rice from one farm and 108 kg from another. She packs it into bags of equal whole-number weight, each bag from one farm only, using as few bags as possible. The bag weight must be a common factor of 84 and 108: 1, 2, 3, 4, 6 or 12 kg. The fewest bags come from the heaviest weight, 12 kg, which is the HCF. She needs 84 ÷ 12 = 7 bags and 108 ÷ 12 = 9 bags, that is 16 bags.

Jumps on a number line. If treasures lie on 14 and 30, the longest jump from 0 that lands on both must divide both numbers, so it is the HCF, 2. For 28 and 42 it is 14, and for 7 and 11 it is only 1.

Why listing is not enough. Listing every factor works for small numbers, but it is slow for numbers such as 840, which has 32 factors, and it is easy to miss one. In the next topics we find a faster and more reliable way using primes.

A prime is a number greater than 1 whose only factors are 1 and itself: 2, 3, 5, 7, 11, 13, and so on. A number greater than 1 that is not prime is composite. The number 1 is neither.

Prime factorisation. Every composite number can be written as a product of primes. Keep breaking any composite factor until only primes are left. For 90: 90 = 9 × 10 = 3 × 3 × 2 × 5. We could also start with 3 × 30 or 2 × 45, but we always end with the same primes, 2, 3, 3 and 5, only in a different order. This is a remarkable fact: every number has exactly one prime factorisation, apart from order.

The division method. Divide by a prime, write the quotient below, and repeat until the quotient is prime.

So 1200 = 2 × 2 × 2 × 2 × 3 × 5 × 5. Reading the primes down the left side and the last number at the bottom gives the factorisation. This is quicker and safer than splitting 1200 as 40 × 30 = 5 × 8 × 5 × 6 and then breaking 8 and 6 again.

Tips for the division method. Try the small primes in order: 2 while the number is even, then 3 (digit sum divisible by 3), then 5 (ends in 0 or 5), then 7, 11 and so on. Stop when the last quotient is prime. For 105: 105 ÷ 3 = 35, 35 ÷ 5 = 7, so 105 = 3 × 5 × 7.

Bigger is not always longer. Anshu guessed: ‘the larger a number, the longer its prime factorisation’. But 96 = 2 × 2 × 2 × 2 × 2 × 3 has six primes while the larger number 121 = 11 × 11 has only two. A statement made without proof is called a conjecture. One example that shows it is false is a counterexample, and one counterexample is enough to disprove a conjecture.

The prime factorisation of a prime number is just the number itself, for example 13 = 13.

The prime factorisation of a number is like a box of building blocks: every factor of the number is built from some of those blocks. We call such a selection a subpart of the factorisation.

Example. 840 = 2 × 2 × 2 × 3 × 5 × 7. Is 28 = 2 × 2 × 7 a factor? Regroup the primes: 840 = (2 × 2 × 7) × (2 × 3 × 5) = 28 × 30. So 28 is a factor, and the leftover primes give the partner factor 30.

Is 2 × 2 × 2 = 8 a factor of 840? Yes, there are three 2s available. Is 3 × 3 × 3 = 27 a factor? No: 840 has only one 3, so we cannot pick three of them.

Listing every factor of 225. 225 = 3 × 3 × 5 × 5. Build subparts in order of size:

So the factors of 225 are 1, 3, 5, 9, 15, 25, 45, 75 and 225, nine in all. Because we built them systematically, we cannot miss one.

A neat way to count. From 3 × 3 we may take no 3, one 3 or two 3s: 3 choices. From 5 × 5 we also have 3 choices. Every combination gives a different factor, so 225 has 3 × 3 = 9 factors. In the same way 840 = 2 × 2 × 2 × 3 × 5 × 7 has 4 × 2 × 2 × 2 = 32 factors, and 360 = 2 × 2 × 2 × 3 × 3 × 5 has 4 × 3 × 2 = 24 factors.

Why it matters. If a factor of a number must use only its own primes, then a factor common to two numbers must be built from primes that both numbers share. This is the key idea behind finding the HCF quickly in the next topic.

A common factor of two numbers must be a subpart of both factorisations. The HCF is the largest such common subpart.

Example 1: 45 and 75. 45 = 3 × 3 × 5 and 75 = 3 × 5 × 5. The common subparts are 3, 5 and 3 × 5. With 1, the common factors are 1, 3, 5 and 15. The HCF is 15.

Example 2: 112 and 84. 112 = 2 × 2 × 2 × 2 × 7 and 84 = 2 × 2 × 3 × 7. The common subparts are 2, 7, 2 × 2, 2 × 7 and 2 × 2 × 7. The HCF is 2 × 2 × 7 = 28.

Example 3: 96 and 275. 96 = 2 × 2 × 2 × 2 × 2 × 3 and 275 = 5 × 5 × 11. They share no prime, so the only common factor is 1. Numbers whose HCF is 1 are called co-prime.

A direct rule. We need not list all the common subparts. Take each prime that appears in both numbers, as many times as it appears in the number that has fewer of it.

Why the fewest? For 30 and 72, the HCF cannot contain two 2s, because 30 has only one 2. So it gets one 2. The same reasoning applies to every prime.

Three or more numbers. Use the same rule across all the numbers. For 42, 75 and 24: 42 = 2 × 3 × 7, 75 = 3 × 5 × 5, 24 = 2 × 2 × 2 × 3. Only 3 is in all three, once, so the HCF is 3.

A trap. 72 = 6 × 12 and 144 = 8 × 18 look as if they share nothing. But 6, 12, 8 and 18 are not primes. Breaking them down shows 72 = 2 × 2 × 2 × 3 × 3 and 144 = 2 × 2 × 2 × 2 × 3 × 3, with HCF 72. Always go all the way to primes.

Anshu stitches torans from cloth strips 6 cm long, and Guna from strips 8 cm long. They want to make torans of the same length. What is the shortest such length?

Anshu's torans can be 6, 12, 18, 24, 30, 36, 42, 48 cm, and so on: the multiples of 6. Guna's can be 8, 16, 24, 32, 40, 48 cm, and so on: the multiples of 8. Lengths in both lists are common multiples: 24, 48, 72, and so on. The shortest is 24 cm.

The LCM. The Lowest Common Multiple (LCM) of two or more numbers is the smallest of their common multiples. The LCM of 6 and 8 is 24. Notice that there is no largest common multiple, because the list goes on for ever.

Free gajak. A sweet shop gives free gajak every Monday, that is every 7 days. Kabamai visits every 10 days, and both happened today. Shop days come after 7, 14, 21, … days; her visits after 10, 20, 30, … days. They first coincide after 70 days, the LCM of 7 and 10.

The idli-vada game. Players count 1, 2, 3, … and say ‘idli’ on multiples of one number and ‘vada’ on multiples of the other. The first time they must say ‘idli-vada’ is at the LCM.

HCF or LCM? A useful check is the size of the answer. Cutting or sharing into equal parts gives an answer that is no larger than the numbers: think HCF. Things repeating until they line up again give an answer that is no smaller than the numbers: think LCM.

Listing multiples is fine for small numbers, but for 14 and 30 you must go to 210. Prime factorisation gives the LCM much faster, as the next topic shows.

A multiple of a number contains all the primes of that number, plus possibly more. For example 36 = 2 × 2 × 3 × 3, and its multiple 648 = 36 × 18 = (2 × 2 × 3 × 3) × (2 × 3 × 3). The factorisation of 36 sits inside the factorisation of 648.

So a common multiple of two numbers must contain the whole factorisation of each. The LCM is the smallest product that does this.

Example: 14 and 35. 14 = 2 × 7 and 35 = 5 × 7. We need 2 × 7 inside, and 5 × 7 inside. The product 2 × 5 × 7 = 70 contains both, sharing the single 7. Removing any prime would lose one of them, so the LCM is 70. Products such as 2 × 7 × 5 × 7 × 3 are also common multiples, but larger.

A direct rule. For each prime that appears in either number, take it as many times as it appears in the number that has more of it.

Example: 96 and 360.

LCM = 2 × 2 × 2 × 2 × 2 × 3 × 3 × 5 = 1440. Fewer 2s would not contain 96; more would make a larger common multiple.

Compare with the HCF. For 30 = 2 × 3 × 5 and 72 = 2 × 2 × 2 × 3 × 3: the HCF takes the fewest of each shared prime, 2 × 3 = 6. The LCM takes the most of every prime, 2 × 2 × 2 × 3 × 3 × 5 = 360.

Three numbers. The rule works for any number of values. For 105 = 3 × 5 × 7, 195 = 3 × 5 × 13 and 65 = 5 × 13, take 3, 5, 7 and 13 once each: LCM = 1365.

Using answers as primes. It is often fine to leave an LCM in factorised form, such as 2⁵ × 3² × 5, when a question asks for it that way.

Mathematicians look for patterns and then try to explain them. A statement that holds in all cases is a general statement, and finding one is called generalisation.

When one number divides the other. The HCF of 6 and 18 is 6, and the LCM is 18. In general, for a number n and a multiple of it such as 5n, the HCF is n and the LCM is 5n. The HCF is the smaller number and the LCM is the larger.

More patterns to test with examples.

Why is the HCF of two consecutive numbers always 1? Any common factor would also divide their difference, which is 1. The same idea shows that two consecutive odd numbers, which differ by 2 and are both odd, also have HCF 1.

Doubling. If both numbers are doubled, each gets one extra 2 in its factorisation, and that 2 goes into the HCF. So the HCF doubles too. For 270 and 50, the HCF is 10; for 540 and 100, it is 20.

A shared multiplier. 14 × 6 and 14 × 9 clearly have 14 as a common factor. But 6 and 9 still share a 3, so the HCF is 14 × 3 = 42, not 14. The HCF equals the shared multiplier only when the leftover numbers are co-prime, as in 10 × 38 and 10 × 21, where the HCF is 10.

LCM and the product. The product of two numbers is always a common multiple, so the LCM is never larger than the product. It equals the product exactly when the numbers are co-prime.

Here is an efficient way to get the HCF and the LCM together. Write the two numbers side by side and keep dividing both by a common factor until the two quotients share no factor.

HCF = the product of the divisors on the left: 2 × 2 × 3 = 12.
LCM = the divisors on the left times the two numbers at the bottom: 2 × 2 × 3 × 7 × 15 = 1260.

Why it works. The left column collects exactly the primes the two numbers share, so it is the HCF. The bottom row holds the primes that belong to only one number. The LCM needs the shared part once plus all the leftover parts, which is exactly the left column times the bottom row.

Bigger steps are allowed. You need not divide by primes only. For 630 and 770, divide both by 10 to get 63 and 77, then by 7 to get 9 and 11, which share nothing. HCF = 10 × 7 = 70 and LCM = 10 × 7 × 9 × 11 = 6930. For 300 and 150, divide by 50 and then by 3 to reach 2 and 1, so HCF = 150 and LCM = 300.

A beautiful relation. For 105 = 3 × 5 × 7 and 95 = 5 × 19, the LCM is 3 × 5 × 7 × 19 = 1995 and the HCF is 5. The product 105 × 95 = 9975 = 1995 × 5. In general:

The reason is that, in the product, every shared prime appears twice and every unshared prime once. The HCF takes one copy of the shared primes and the LCM takes the other copy along with all the unshared ones. Check: for 12 and 18, HCF 6 × LCM 36 = 216 = 12 × 18.

Careful. This relation is for two numbers. For three numbers it usually fails.