Applications of GCD in measurements

Lets see applications of GCD in measurements of following with examples.




Measurement of Area


Question: Consider that you are given the dimensions of a rectangular room (Say 24ft by 40 ft). The requirement is to lay minimum number of square tiles in the floor. The tiles have to be perfect and cannot be broken down to fill gaps. What is the dimension of the square tile you need?

Answer: This is a very simple application of GCD. We know that dimension of square is same on all sides. The dimension of the square tile should be a divisor of both length and width (common divisor) of the room in order for it to perfectly fit without the usage of any broken tiles. Since our requirement is to use minimum number of tiles, we should opt for biggest possible square tile. Therefore we need to find the greatest common divisor of length and width of the room which will give us the dimension of the square tile. Here, the GCD is 8. So the dimension of the biggest possible square tile is 8.

Measurement of Length

Question: Take two ropes of length 9 inches and 12 inches. What are the possible lengths that you can measure using these two ropes? ( Assume that you cannot bend/twist the rope. Also you have access to some cutting tool/marker)

When you only have a rope of length 9 inches you can measure – 9,18,27,36.. – all multiples of 9.

Similarly with 12 inches rope, you can measure – 12,24,36,48…- all multiples of 12.

So when you have both the ropes you can of course measure the multiples of both the lengths. Is that all? Can you not measure anything else?

You can measure the difference in lengths of the two ropes and play around using that to check if you can measure anymore lengths. In our case, 12-9 is 3. So you can now measure 3. Which means you can also measure all multiples of 3 (3,6,9,12,15…).¬† If you take this 3 and try to measure either of the ropes using that, you can see it perfectly fits 9 – 3 times or 12 – 4 times. If in case if it hadn’t fit perfectly, you will have one more smaller length that you can measure. In our case, it was not possible because, 3 is the greatest common divisor of 9 and 12. So, we are done here. The minimum lengths that you can measure is 3. And then all the multiples of 3.

In general you can say that – If two ropes of different lengths are given, the smallest length that can be measured is the gcd of the two lengths. All the multiples of GCD can also be measured.

If you are wondering how we ended up with GCD with the help of difference in lengths, you should check proof for euclid’s algorithm.

Lets see one more example to make this clear.

Question: Take two ropes of length 20 inches and 28 inches. What are the possible lengths that you can measure using these two ropes? ( Assume that you cannot bend/twist the rope. Also you have access to some cutting tool/marker).

With 20 and 28 inches ropes you can measure all the multiples of these numbers. Apart from that, first you can measure 28-20 which is 8 inches. You don’t have to stop here. Try measuring this new length ‘8’ in any one of the ropes. You can measure two 8’s in the 20 inches rope. You will now have the difference of 4. (2*8 = 16. 20-16 is 4. Refer to the diagram). If you again try to measure this 4 in any of the ropes, you will notice that it perfectly divides all the rope lengths you have – 8,20 and 28. Because 4 is the GCD of 20 and 28.

In the first step if you try to measure the difference of 8 in the bigger rope instead of smaller one, you will end up with the same result.

We can conclude that the smallest length that can be measured with 20 inches and 28 inches ropes is 4. All multiples of 4 (4,8,12,16,20,24,28…) can also be measured. [Notice that the original rope lengths will always be included in our answer set. Because they are the multiple of the length that we concluded as it is a divisor of both the numbers.]

If you take ropes of length 7 and 11 inches, you will end up with 1 inch if you follow similar steps. Since you have got unit length (1 inch), you can measure any length using that. It is possible because 7 and 11 are coprimes – GCD is 1. Thus, if the given ropes are co primes, then any length can be measured.

Measurement of Volume

Exactly same concept can be applied to the measurement of volumes. But this gets little trickier because, measuring volumes is not as straight forward as measuring length. With length, we can easily make markings or cut the ropes. But with volumes, we cannot make markings (unless we assume that the containers are evenly shaped and are transparent. But this assumption is kind of impractical). So we have to keep transferring liquid between containers to achieve the results.

If you have two containers of volume v1 and v2, general rule is,

  1. Keep filling the smaller container with water and pour it into the bigger container.
  2. If the bigger container is full, empty it.

You should keep track of the measurement in the bigger container. Repeat the above steps until you get the desired volume.

The minimum volume that you can measure is gcd(v1,v2). Then all multiples of the gcd can be measured until less than v2(the bigger container volume). Because its the maximum capacity that you have. If you have  additional containers to offload the liquid measured, then it is possible to measure any multiple of the gcd based on the capacity.

Watch the video to understand how transferring of liquid yields different volumes.