I was writing up a description of the Euclidean algorithm for a set of course notes and was playing around with one geometric intuition for the algorithm that involves tiling an $m \times n$ rectangle with progressively smaller squares, as seen in this animation linked from the Wikipedia article:
I was looking over this animation and was curious whether or not the squares that you would place down in the course of this algorithm necessarily gave the minimum number of squares necessary to cover the entire rectangle.
More formally: suppose that you are given an $m \times n$ rectangle, where $m, n \in \mathbb{N}$ and $m, n > 0$. Your goal is to tile this rectangle with a set of squares such that no two squares overlap. Given $m$ and $n$, what is the most efficient way to place these tiles?
Is the tiling suggested by the Euclidean algorithm (that is, in an $m \times n$ rectangle, with $m \ge n$, always place an $n \times n$ rectangle, then recurse on the remaining rectangle) always optimal? If not, is there are more efficient algorithm for this problem?
I am reasonably sure that the Euclidean approach is correct, but I was having a lot of trouble formalizing the intuition with a proof due to the fact that there are a lot of different crazy ways you can try to place the squares. For example, I'm not sure how to have the proof handle the possibility that squares could be at angles, or could have side lengths in $\mathbb{R} - \mathbb{Q}$.
Thanks!