Prove that the square of every natural number is of the form $3k$ or $3k+1$, where $k \in \mathbb{Z}$.

I'm trying to reach a contradiction by assuming $n^2 = 3k+2$. Any ideas?

  • 2
    $\begingroup$ Do you know induction? $\endgroup$
    – Cass
    Apr 1 '14 at 20:45
  • $\begingroup$ Better to verify it for $n=0,1,2$ and then do three inductions, going from $n$ to $n+3$ in each. $\endgroup$
    – Lubin
    Apr 1 '14 at 20:46

Go for a direct proof. Any natural number is one of the forms: $3m, 3m+1, 3m+2$ where $m$ is a natural number. What do you get when you take the squares of these forms?


Well, you know that any integer can be written in the form $3k$, $3k + 1$ or $3k + 2$ following the division algorithm.

Now let's take the square of each of them;

$(3k)^2 = 9k^2 = 3(3k^2)$, of the form $3k$;

$(3k+1)^2 = 9k^2 + 6k + 1 = 3(3k^2 + 2k) + 1$, of the form $3k + 1$;

$(3k+2)^2 = 9k^2 + 12k + 4 = 9k^2 + 12k + 3 + 1 = 3(3k^2+4k+1)+1$, of the form $3k + 1$;

therefore no integer $n^2$ can be written in the form $3k + 2$, hence all integers squared are of the form $3k$, or $3k + 1$.


Hint mod 3: $n \equiv 0, \pm 1 \implies n^2 \equiv 0, 1$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.