Diagonal in a Rectangle

A 1000 × 1004 rectangle is split into 1 × 1 squares. How many of these squares does the main diagonal of the large rectangle pass through?

SOLUTION

Notice that the number of small squares the main diagonal passes through is equal to the number of horizontal and vertical lines it intersects. Indeed, every time the diagonal goes through the interior of one square to the interior of another, it must intersect one of these lines.

There are 1000 + 1004 = 2004 lines which are intersected by the main diagonal. However, on four occasions (which is the greatest common divisor of 1000 and 1004), the main diagonal intersects one horizontal and one vertical line at the same time, which results in double-counting., so we must subtract 4 from the answer.

Therefore, the answer is 1000 + 1004 – 4 = 2000.