Using Relative Primes
Date: 12/07/96 at 17:20:14 From: Natasha Chin Subject: (no subject) I have a problem that I think can be solved using the Pythagorean theorem, but I'm not sure. Am I completely missing the boat? A basketball court is made up of square parquet tiles, all the same size, laid side by side to form a rectangle 105 tiles wide and 135 tiles long. If a straight line is drawn diagonally from one corner of the floor to the opposite corner, how many tiles will the diagonal intersect? I have a feeling that I have to use the Pythagorean theorem, but I also have this feeling that it's a red herring. Wouldn't it just be too simple? Things can't be too simple. There must be some kind of catch! HELP!
Date: 12/09/96 at 05:12:44 From: Doctor Pete Subject: Re: (no subject) Well, here's how you'd decide whether or not the Pythagorean theorem will help. What does it tell you? It will give you the length of the diagonal, but how does that translate into finding how many tiles it crosses? To get a better idea of what's going on, think about how the diagonal can cross a square. Either it will go through two sides of a tile, or it will pass through a corner (or two corners, if it's at a 45-degree angle). Say we had a simpler case, where there are only six tiles, arranged in a 2 x 3 block: ___________ |\ | | | \ | | | \ | | |---\-|-----| | \| | | | | |_____|\____| | | \ | | | \ | | | \ | |-----------| I know it's not a perfect drawing, but I hope you get the picture (hah-hah). Notice that when we draw a diagonal, it doesn't go through any corners except where we started and stopped. If you think about it, that's because 2 and 3 are *relatively prime*. If two numbers are relatively prime, it means that their greatest common divisor is 1. The diagonal passes through 4 squares, because if it doesn't go through any corners on its way across, then we know it must pass through a square each time it goes 1 square down, and it must pass through another square each time it goes 1 square to the right. So it passes through (2+3)-1 = 4 squares. So we can see that if we had a grid of m tiles by n tiles, where m and n are relatively prime, then the diagonal passes through exactly m+n-1 squares. Now, how does this help us when m and n *aren't* relatively prime? To answer this, we look at the 2 x 3 grid again, and notice if we were to make it a 4 x 6 grid by placing a copy of itself alongside the original, then the number of squares the diagonal passes through is simply twice as many since the diagonal hits a corner in the middle. So it becomes clear that if we had a 6 x 9 grid, it passes through 3 times as many squares, and so on. In other words, we simply factor out the greatest common divisor. So if we had a grid of squares that measured 130 x 215, we first factor 130 and 215 to get: 130 = 2(5)(13) 215 = 5(43) Thus the greatest common divisor of 130 and 215 is 5. So we need to find how many squares are intersected in a grid of dimensions 26 x 43. Since these are relatively prime, the diagonal intersects 26+43-1 = 68 squares. Multiplying by 5, we see that the diagonal intersects 5(68) = 340 squares. Now, try it on your original problem. I hope my explanation made sense. -Doctor Pete, The Math Forum Check out our web site! http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994-2013 The Math Forum