Junior's first number theory proof

Back in my undergrad days, when I was taking a number theory class, I noticed that all squares that weren't multiples of three were always one more than a multiple of three, never one less.

16 = 15 + 1

25 = 24 + 1

100 = 99 + 1

After I thought about it for a while I realized that this had to be the case and there was a simple algebraic proof that showed it (there's a also a simple geometric proof -- think about cutting the square into two smaller squares and two rectangles -- but that can wait for another day).

I'd assign this with the following hint:

think about (x + 1)(x + 1) and (x - 1)(x - 1)

Here's the proof. All natural numbers can be written as:

I. 3k

II. 3k + 1

III. 3k - 1

We're talking about squares that aren't multiples of three so we can skip the first case and look at II and III.

(3k + 1)(3k + 1) = 9k^2 + 6k + 1 = 3(3k^2 + 2k) + 1

(3k - 1)(3k - 1) = 9k^2 - 6k + 1 = 3(3k^2 - 2k) + 1

I like this problem for a few reasons.

First, it's simple. The question is easy to state and the proof is at the right level for a beginner.

Second, it gives the student a chance to do something interesting with polynomials.

Third, it demonstrates an important problem solving technique -- breaking the problem down to cases.

Fourth, it introduces number theory and it gets the students thinking about numbers in a different way.