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.