Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
High School Basic Algebra
High School Euclidean/Plane Geometry
High School Geometry

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search