Question 1203906
<pre>

{{{drawing(100,100,-1,13,-1,13,

line(0,0,12,0),line(0,6,12,6),line(0,12,12,12),
line(0,0,0,12),line(6,0,6,12),line(12,0,12,12) )}}}{{{drawing(100,100,-1,13,-1,13,

line(0,0,12,0),line(0,8,12,8),line(0,12,12,12),
line(0,0,0,12),line(8,0,8,12),line(12,0,12,12),
line(4,8,4,12),line(8,4,12,4))}}}{{{drawing(100,100,-1,13,-1,13,

line(0,0,12,0),line(0,9,12,9),line(0,12,12,12),
line(0,0,0,12),line(9,0,9,12),line(12,0,12,12),
line(3,9,3,12),line(6,9,6,12),line(9,6,12,6),line(9,3,12,3)
)}}}

(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 {{{k>=6}}}, 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</pre>