For what natural $n$ does there exist a square composed of $n$ squares?

Question

I recently stumbled upon a cute puzzle involving squares:

For what natural $n$ does there exist a square composed of $n$ squares?

For example, $1,4,$ and $6$ are valid:

But $2$ and $3$ are not valid.

Answer 1

Note first that you can always add three squares to a configuration by splitting one sub-square into four.

Then take a $3\times 3$ square out of the corner of a square of side $4$ to find a configuration with $8$ squares.

This gives $1+3n; 6+3n; 8+3n$ as possibles, leaving just $2,3,5$ as impossible.

See also the comment on cute squares in this link: https://en.wikipedia.org/wiki/Squaring_the_square which says it can be done with squares of no more than two sizes for all positive integers other than 2,3,5.

Answer 2

There is no way to add one square to an arrangement and still get only squares. You can add 2 squares to any arrangement after the first 2 and still have all squares (for example, your move from 4 to 6 squares). You can also always add 3 squares and still get only squares (for example, from 1 to 4). You do this by breaking any given square into 4 squares. You can also add 5 squares by starting with a 3x3 that is 1 square and breaking up the first row and the first column into squares. But this can also be achieved by starting with a 4x4 and adding 2 squares. There is no other way to add squares to any arrangement. Therefore, $$n = 1 + 2a + 3b,$$ where $b \geq 0$, $a \geq 0$, and for $b = 0$ you must have $a=0$, since you cannot add 2 on the first step.