2
$\begingroup$

The question I was trying to solve was:

A rectangular floor $24×40$ is covered by squares of sides $1$. A chalk line is drawn from one corner to the diagonally opposite corner. How many tiles have a chalk line segment on them?

In the answer to the problem, the following was stated

Because $GCD(24, 40)=8$, the chalk line contains 8 points where a row and a column intersect, including the terminal corner.

I came to the same conclusion in a different manner, by simplifying the slope, $\frac{24}{40}$ to $\frac{3}{5}$ and plugging in multiples of $5$ and obtaining the points $\left\{ \left( 3,\; 5 \right),\; \left( 10,\; 6 \right),\; \left( 9,\; 15 \right),\; ... \right\}$ by multiplying both $x$ and $y$ by integral values.

What I want to know is why finding the GCD between the two numbers gives you the number of intersection points between the row and column. How can you prove that this always works?

$\endgroup$
1
$\begingroup$

When you simplified $\frac {24}{40}$ to $\frac 35$, you divided numerator and denominator by $8$, which is $\gcd(24,40)$ The point is in a sense the same as what you did by hand. The first intersection the line goes through is $\left(\frac {24}{\gcd(24,40)},\frac {40}{\gcd(24,40)}\right)$ and the pattern repeats.

$\endgroup$
0
1
$\begingroup$

Hint $ $ Consider the floor placed with lower-left corner at the origin of the plane. Then you are interested in the positive integer points on the line $\,y = \frac{24}{40} x,\,$ i.e points with both $\, 0 \le x,y\in\Bbb N.\,$

$$\ y = \dfrac{24}{40}\, x \iff \dfrac{y}x = \dfrac{3}5 \iff \begin{eqnarray}y\, =\, 3n\\ x\, =\, 5n\end{eqnarray}\ \ \ {\rm for}\ \ n \in \Bbb N$$

When we restrict solutions $\,x\le 40 = 5\cdot\color{#c00}8\,$ there are $\,\color{#c00}8\,$ solutions $\ x = \,1\cdot 5,\ 2\cdot 5,\,\ldots,\, \color{#c00}8\cdot 5,\,$ where $\,\color{#c00} 8 = \gcd(24,40) =\,$ the common factor cancelled to reduce the fraction to lowest terms.

Said in vector language, the solutions $(x,y) = (3n,5n) = n(3,5)$ are integral multiples of the vector $(5,3)$ corresponding to the lowest terms equivalent of the fraction. Said in more visual language, $(3,5)$ is the first integer point you see if you stand at the origin looking down the line.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.