# (Proof) Square of integer is 3k or 3k+1

1. Jan 14, 2008

### jimmypoopins

1. The problem statement, all variables and given/known data
Prove that the square of any integer a is either of the form 3k or of the form 3k+1 for some integer k.

2. Relevant equations
The Division Algorithm: Let a,b be integers with b>0. Then there exists unique integers q and r such that a = bq + r and 0<=r<b

3. The attempt at a solution
I know from the division algorithm that any integer a can be written as 3q, 3q+1, or 3q+2, so
a^2=(3q)^2=9q^2=3(3q^2), or
a^2=(3q+1)^2=9q^2+6q+1, or
a^2=(3q+2)^2=9q^2+12q+4,
but i don't understand how the 3q+1 or 3q+2 case helps me.

Can anyone give me some hints or point me further in the right direction? thanks.

Last edited: Jan 14, 2008
2. Jan 14, 2008

### Tom Mattson

Staff Emeritus
Well it's obviously not going to be of the form 3k, right? So try to fit it to the other form, namely 3k+1. That means strip a +1 off from the +4 at the end. It should fall right out.

3. Jan 14, 2008

### ircdan

Good Work, you are basically done. Copying and pasting what you wrote,

a^2=(3q)^2=9q^2=3(3q^2), or
a^2=(3q+1)^2=9q^2+6q+1 = 3(3q^2 + 2q) + 1, or
a^2=(3q+2)^2=9q^2+12q+4 = 3(3q^2 + 4q + 1) + 1,

so you are done.

4. Jan 14, 2008

### jimmypoopins

ah, simple arithmetic :) thank you!