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/