Why is it for every $k\in\mathbb{N}\setminus\{2,3,5\}$ possible, to partition a square into $k$ non-overlapping squares (they have not to have the same size).
This should be proved with induction. The induction basis $k=1$ is clear.
But what should I do in the induction step?
Instead of induction, it will be easier to prove the results directly.
We are going to show for all $n \ge 2$, we can split the square into $k = 2n$ and $k = 2n+3$ squares.
This will cover the cases for all even $k \ge 4$ and all odd $k \ge 7$. This leaves us with $k = 1, 2, 3, 5$. Since $k = 1$ is clearly possible, we can conclude for all $k \in \mathbb{N} \setminus \{ 2, 3, 5 \}$, we can split the square into $k$ smaller squares.
Let's back to the proof. WOLOG, we will assume the original square is the unit square $[0,1] \times [0,1]$.
To split the unit square into $2n$ smaller squares.
We first cut out a square of side $1 - \frac1n$ along the lines $x = \frac1n$ and $y = \frac1n$. We then split the remaining $L$-shape into $2n-1$ squares of side $\frac1n$ ( the $\color{red}{\verb/red squares/}$ in figure below).
To split the unit square into $2n+3$ smaller squares.
We first split the unit square into $2n$ smaller squares like above. We then split the square of side $1 - \frac1n$ into 4 equal pieces (the $\color{blue}{\verb/blue squares/}$ in figure below )
As an illustration of this procedure, following is a picture showing how to split the unit square into $11 = 2\cdot 4 + 3$ smaller squares.
$\hspace 1.5in$ 
