Mock PRMO question I find a interesting question of my PRMO mock and 2019 AMC 10A
The rectangular floor of a bathroom is covered with square tiles (all of the same size). A
spider starts at one corner of the bathroom, and walks to the corner diagonally opposite. For
example, the figure below shows a 6 × 8 bathroom, in which the spider touches 12 tiles on
its path. (A spider doesn’t touch a tile if it just walks over the grout at the corner of a tile.)
For an $m\times n$ bathroom, how many tiles does the spider touch on its walk?


My assumption is that number of tiles bugs walk through is $2* (\text{no. of columns})$ but I am unable to prove it.

Can anyone please help me with solution?
 A: The solution provided by Reza , though correct , is a little advanced , I think.
Let me provide a easier version of the solution.
Let us first focus on a smaller floor . Let it be 5 by 3 .

We see it crosses 7 tiles .
We see in the diagram above and see whenever we enter into a new square
either right or in the up direction we enter a new tile.
So in the 5 by 3 example we go right 5 times because it is the length and up 3
times .
So we go through 5+3-1=7 tiles. We subtract one because when we reach the
corner we are simultaneously going up and right
Now let’s take example of 6 by 4 floor.

Now applying the previous logic here , by the formula we get 6+4-1 =9 tiles ,
but in actuality 8 tiles are crossed.
This is because we see this time the diagonal simultaneously moves right and
up two times , once in the center and once in the corner.
So for the general formula we just have to count how many times a diagonal
crosses a corner.
We see this is just the gcd of the dimensions.
So for a m by n floor , no of tiles crossed by diagonal are
m + n - gcd(m,n)
A: First, we assume $(m,n)=1$.
Let's locate the rectangular on the coordinate system such that the beginning corner  is $(0,0)$ and the final corner is $(m,n),$ and each intersection inside the rectangular has integer coordinates. Due to assuming $(m,n)=1$, the spider does not cross any intersection. This fact leads to the conclusion below.
In general, for the $k$th column ($k <m$), the spider touches $[\frac{k(n)}{m}]-[\frac{(k-1)n}{m}]+1$ tiles of the $k$the column.
To prove that, just consider the intersections of pairs of lines $y=\frac{n}{m}x, x=k-1$ and $y=\frac{n}{m}x, x=k.$
However, for the $m$th column, since $\frac{nm}{m}$ is an integer, the spider touches $[\frac{mn}{m}]-[\frac{(m-1)n}{m}]$ tiles.
Therefore,
$$[\frac{n}{m}]+1 + ([\frac{2n}{m}]-[\frac{n}{m}]+1) + ([\frac{3n}{m}]-[\frac{2n}{m}]+1) + ... + ([\frac{mn}{m}]-[\frac{(m-1)n}{m}]) \\ =m-1 +n$$
is the total number of tiles that the spider touches.

If $(m,n)=d$, then the $\frac{m}{d} \times \frac{n}{d}$ rectangular repeats $d$ times in the main rectangular. For example, in your case where $(6,8)=2$:


The answer is $m+n-(m,n)$.
A: As the line moves from south-west to north-east, each time it crosses either a vertical or horizontal edge (including the left and bottom border lines, but not the right and top), the line enters a new tile. There are exactly $m$ vertical edge crossings and $n$ horizontal edge crossings. This suggests there are $m+n$ tiles touched.
However, there is double-counting whenever the path enters via a corner, since it is crossing both the vertical and horizontal edges. We correct for this double-counting by subtracting the number of tiles entered from a corner. You can confirm the number of corner-entrances is $\gcd(m,n)$. A corner crossing occurs at $(m/d,n/d)$, where $d$ is any common divisor of $m$ and $n$, so the first crossing must occur at the $(m/\gcd(m,n),n/\gcd(m,n))$. Thereafter, the same pattern must repeat, meaning there are exactly $\gcd(m,n)$ corner crossings.
Therefore,
\begin{align}
\text{# tiles touched } =\,\,&\text{(# tiles entered from vertical edge)} 
\\&+\text{(# tiles entered from horizontal edge)}
\\&-\text{(# tiles entered from both vertical and horizontal)}
\\&\hspace{-.6cm}=m+n-\gcd(m,n)
\end{align}
