On squared paper, draw a rectangle and one of its diagonals. How many grid squares are crossed by the diagonal?

Let a = (0,0) and x coordinate is to right and y coordinate downwards

Let the rectangle be ABCD as in the diagram and of the size m * n. The diagonal is AC. There are m+ 1 vertical lines and n+1 horizontal in the above diagram m = 4 and n = 3

Now let us see when it shall pass though a point which is a corner that is intersection of horizontal line and vertical line say at (p , q) coordinate

Slope of the line = m/n = p/ q where p < m , q < n .

This may pass through multiple points and let p/q is with the lowest p and q

m/p = n/q is the GCD (m,n)

So if gcd(m,n) is 1 then we do not have p/q form and the line does not pass through any point (p,q) that is a corner( we define a corner as intersection of horizontal line and vertical line)

So we take 2 cases

1) GCD(m,n) is 1 that is m,n are coprime

The diagonal from A to C shall pass through m vertical sections which shall be m squares and n-1 horizontal lines shall be cut by the diagonal ( at a point other than a corner point) so each shall give 2 squares that is addition of 1 square that making m+n-1 squares. So the diagonal pass through m+n-1 squares.

2) GCD(m,n) is not one that is m ,n are not coprimes say GCD (m,n) = p

Now m/p and n/p are coprimes and we get p parts of (m/p, n/p) rectangle through which the diagonal passes.

So number of points = p(m/p + n/p – 1) = m+ n – p

So we combining (1) and (2) get m+ n – gcd(m,n)

For example in the above figure m = 4, n= 3.

It goes through 1+ 2 + 2 + 1 ( note that in the 2^nd region and 3^rd region it is 2 as diagonal cuts the horizontal line) = 6

m+n – 1 = 4 + 3 -1 = 6