# Counting squares of maximum size in a rectangle

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?

-

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$. To 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}$$

-

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$.

-
Someone who is bad at math will not understand this answer, you're going way too fast. – Tim Vermeulen May 31 '13 at 21:30
@timjver - my answer is identical to what you posted after me. If he had a problem with my answer he could have asked and I would have answered. Why downvote a correct answer because you think it is too terse? – svenkatr May 31 '13 at 21:35
The only reason I posted after you is because I motivated my answer more elaborately. But you're right, in essence our answers are equal. – Tim Vermeulen May 31 '13 at 22:02