1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Jan 14, 2008 #1
    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
    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. jcsd
  3. Jan 14, 2008 #2

    Tom Mattson

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
  4. Jan 14, 2008 #3
    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.
  5. Jan 14, 2008 #4
    ah, simple arithmetic :) thank you!
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook