XXVIII - I - Task 3

Let $ a $ and $ b $ be natural numbers. A rectangle with sides of length $ a $ and $ b $ has been divided by lines parallel to the sides into unit squares. Through the interiors of how many squares does the diagonal of the rectangle pass?
Consider a rectangle $ABCD$ with base $\overline{AB}$ of length $a$ and height $\overline{BC}$ of length $b$. Let's consider its diagonal $\overline{AC}$ connecting the lower left vertex $A$ with the upper right vertex $C$ (Fig. 4).
First, assume that the numbers $a$ and $b$ are relatively prime. If a vertex $E$ of a unit square contained within the rectangle $ABCD$ lies on $\overline{AC}$, then we have $\displaystyle \frac{a}{b} = \frac{AB}{BC} = \frac{AF}{EF}$, which means $a \cdot EF = b \cdot AF$, where $F$ is the projection of point $E$ onto line $AB$. Since $a$ and $b$ are relatively prime and $EF$ and $AF$ are natural numbers, it follows from the last equation that $a$ is a divisor of $AF$. This is impossible because $AF < AB = a$.
The obtained contradiction proves that the diagonal $\overline{AC}$ does not pass through any vertex of a unit square contained within the rectangle $ABCD$. Therefore, it defines a sequence of unit squares whose interiors it consecutively intersects. Each subsequent square in the sequence shares a side with the previous one and is located to the right or above it. By following the path defined by the squares of this sequence, we perform $a - 1$ moves to the right and $b - 1$ moves upwards. In total, we have $a + b - 2$ moves, meaning the path consists of $a + b - 1$ squares, i.e., the diagonal $\overline{AC}$ passes through the interiors of $a + b - 1$ unit squares.
If, however, the numbers $a$ and $b$ are not relatively prime and their greatest common divisor is $d$, then let $a = da'$ and $b = db'$. In this case, the numbers $a'$ and $b'$ are relatively prime. The diagonal of a rectangle with sides of length $a'$ and $b'$ consists of $d$ equal segments, each of which is the diagonal of a rectangle with sides of length $a'$ and $b'$. Based on the already considered case, each such segment of the diagonal passes through the interiors of $a' + b' - 1$ unit squares, and therefore the entire diagonal passes through the interiors of $d(a' + b' - 1)$ unit squares.