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

[jimmypoopins]

Homework Statement

Prove that the square of any integer a is either of the form 3k or of the form 3k+1 for some integer k.

Homework 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

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.

 

[quantumdude]

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.

 

[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.

 

[jimmypoopins]

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.

ah, simple arithmetic :) thank you!