(1)  The first figure above proves that we can cut a square into 4 smaller
squares.
(2)  The second figure above proves that we can cut a square into 6 smaller
squares.  
(3)  The third figure above proves that we can cut a square into 8 smaller
squares.

LEMMA:  If we can cut a square into n smaller squares,  we can also cut a square
into n+3 smaller squares.
Proof: Suppose we have a square cut into smaller squares. Now suppose we cut one
of its smaller squares into 4 even smaller squares.  We then will have lost the
square that we cut in the count, but we will have gained 4 squares, for a net
gain of 3 squares.  QED

Therefore, by the LEMMA, we can also cut a square into 7 smaller squares, by
picking one of the squares in the first figure and cutting it into 4 smaller
squares.

So we have proved that we can cut a square into 6, 7, or 8 smaller squares.

Every integer divided by 3 leaves a remainder of 0, 1, or 2.
So every integer is either a multiple of 3, 1 more than a multiple of 3,
or 2 more than a multiple of 3.

Proof by induction: Assume that up through k, where , it is possible
to cut a square into k smaller squares. Then by the LEMMA, a square can be cut
into k+1 squares, by cutting a square in (k+1)-3 or k-2 smaller squares, and
then cutting any one of its smaller squares into 4 even smaller squares, cutting
the square into (k-2)+3 or k+1 squares.

So we can cut any square into n smaller squares except for n=2,3,5.  QED

Edwin