# Determine number of squares in progressively decreasing size that can be carved out of a rectangle

How many squares in progressively decreasing size can be created from a rectangle of dimension $a\;X\;b$

For example, consider a rectangle of dimension $3\;X\;8$

As you can see, the biggest square that you can carve out of it is of dimension $3\;X\;3$ and they are ABFE and EFGH

The next biggest square is of dimension $2\;X\;2$ which is GJIC

Followed by two other squares of dimension $2\;X\;2$ which are JHLK and KLDI

Is there any mathematical approach of solving it for a rectangle of arbitrary dimension?

-
I have full faith that you have the stamina to type out the word "number" rather than just typing "no," so please use "number instead! – rschwieb Apr 30 '13 at 20:13
@rschwieb: Its more of a habit rather than a stamina. Sorry about that – Abhijit May 1 '13 at 5:31

Following the algorithm you seem to be doing, cutting the largest possible square off a rectangle, it is a simple recursive algorithm. If you start with an $n \times m$ rectangle with $n \ge m$, you will cut off $\lfloor \frac nm \rfloor m \times m$ squares and be left with a $(n-\lfloor \frac nm \rfloor m) \times m$ rectangle. Then you remove as many $(n-\lfloor \frac nm \rfloor m)$ squares as you can and continue. The smallest square will be the greatest common divisor of $n$ and $m$
It's quickly a hard problem. For example, can a $189\times189$ or $190\times188$ rectangle be cut into 47 decreasing squares? This problem is too combinatorially hard to solve at the moment.