Counting squares of maximum size in a rectangle

Question

Given a rectangle of sides $m$ and $n$. $( m,n \in [1,1000] )$ We can cut the rectangle into smaller identical pieces such that each piece is a square having maximum possible side length with no left over piece of the rectangle. How could we count this squares of maximum size?

For example: If the rectangle is of size $6 \times 9$. We can cut it into 54 squares of size $1 \times 1$, $0$ of size $2 \times 2$, $6$ of size $3 \times 3$, $0$ of size $4 \times 4$, $0$ of size $5 \times 5$ and $0$ of size $6 \times 6$. The minimum number of squares of maximum size that can cut is $6$.

My approach: I computed the product $m \times n$ say $K$.Then found the maximum perfect square that divides $K$. The quotient of this division seems to be the required answer. But unfortunately it's doesn't seem to yield correct answer. Where exactly I am going wrong?

Answer 1

You should find the GCD of the sides of the rectangle, i.e., the GCD of $m$ and $n$. This is the side of the largest square you can use to fill in the entire rectangle. To find out the number of squares, calculate $\frac{mn}{\gcd(m,n)^2}$. For your example, $\gcd(6,9) = 3$. The number of squares = $6*\frac{9}{3^2}=6$.

Answer 2

You want to cut the rectangle in squares with side length $s$ without pieces of the rectangle left over, so $s$ must divide both $m$ and $n$. The maximum possible value of $s$ is thus the greatest common divisor of $m$ and $n$: $$s = \gcd(m,n)$$

To find the number of squares the rectangle is cut into, you need to find how many squares fit in the length of the rectangle $\left(\frac{m}{\gcd(m,n)}\right)$ and multiply that with the amount of squares that fit in the width of the rectangle $\left(\frac{n}{\gcd(m,n)}\right)$:

$$ \left(\frac{m}{\gcd(m,n)}\right) \times \left(\frac{n}{\gcd(m,n)}\right) = \frac{m \times n}{\gcd(m,n)^2} $$