# Would like a proofreading of my proof

Prove that if $n\in\mathbb Z$, then $n^2$ is of the form $3q$ or $3q+1$ for some $q\in\mathbb Z$

I would like to show that 3q+2 is = 3q+1 thus $n^2$ can be of the form of 3q or 3q+1.

Case one

$(3k)^2=(3k)(3k)=9k^2=3(3k^2)$ and is still of the form $3q$

When $q=3k^2$

$3q$

Case two

$(3k+1)^2= (3k+1)(3k+1)= 9k^2+6k+1$

$(9k^2+6k)+1 =3(3k^2+2k)+1$ this is of the form $3q+1$ when $q=3k^2+2k$

$3q+1$

Case three

$(3k+2)^2= (3k+2)(3k+2) =9k^2+12k+4$

$(9k^2+12k+4) = 3(3k^2+4k+1)+1$

This is of the form $3q+1$ when $q=3k^2+4k+1$

$3q+1$

using a direct proof with cases we see that when $n$ is of the form $3k$ it's in the form $3q$ after squaring. Also when n is in the form $3k+1$, $n$ squared is still in the form $3q+1$ after squaring. Lastly we saw that when $n$ was in the form $3k+2$ we could simplify to the form $3q+1$.

-
You should be more careful and precise about what you write. You forgot several brackets and "$3q + 2$ is $= 3q + 1$" does not make any sense. I understand you are trying to say something like $(3q + 1)^2 \equiv (3q + 2)^2 \mod 3$, but I should not have to read between the lines. –  TMM Sep 8 '11 at 13:38
Also the case 1 should look something like $(3q)^2 = 9q^2 = 3(3q^2)$. –  Srivatsan Sep 8 '11 at 13:46
Thanks for that one I don't know how I forgot that (3q)^2 =9q^2 –  Dennis Hayden Sep 8 '11 at 13:55
@Dennis: Your proof still contains lots of errors. And even what Srivatsan just pointed out is not correct yet, as $3q^2 \neq 9q^2$. –  TMM Sep 8 '11 at 13:59
My initial comment that "$3q+2$ is $=3q+1$" does not make any sense still stands. And "Lastly we saw that when $n$ was in the form $3k+2$ we could simplify to the form $3q+1$." is still a bit clumsy, if you do not add "$n^2$" somewhere in that sentence. –  TMM Sep 8 '11 at 17:08

We show that if $n = 3k$, $n = 3k+1$ or $n = 3k+2$ for some $k \in \mathbb{Z}$, then $n^2 = 3q$ or $n^2 = 3q + 1$ for some $q \in \mathbb{Z}$. Since any $n \in \mathbb{Z}$ can be written in one of the forms $3k, 3k+1$ or $3k + 2$ for some $k \in \mathbb{Z}$, the result then follows.

Case one: $n = 3k$.

If $n = 3k$, then $n^2 = (3k)^2 = 9k^2 = 3(3k^2) = 3q$ for $q = 3k^2 \in \mathbb{Z}$.

Case two: $n = 3k+1$.

If $n = 3k+1$, then $n^2 = (3k+1)^2 = 9k^2 + 6k + 1 = 3(3k^2 + 2k) + 1 = 3q + 1$, for $q = 3k^2 + 2k \in \mathbb{Z}$.

Case three: $n = 3k + 2$.

If $n = 3k+2$, then $n^2 = (3k+2)^2 = 9k^2 + 12k + 4 = 3(3k^2 + 4k + 1) + 1 = 3q + 1$, for $q = 3k^2 + 4k + 1 \in \mathbb{Z}$.

So we see that when $n$ is of the form $3k$, then $n^2$ is of the form $3q$. Also when $n$ is of the form $3k+1$, then $n^2$ is of the form $3q+1$. Lastly we saw that when $n$ was of the form $3k+2$, then $n^2$ is of the form $3q+1$.

Formally, what you want to prove is the following five statements.

$$[n \in \mathbb{Z}] \Longrightarrow \left([n = 3k, k \in \mathbb{Z}] \vee [n = 3k + 1, k \in \mathbb{Z}] \vee [n = 3k + 2, k \in \mathbb{Z}]\right)$$ $$[n = 3k, k \in \mathbb{Z}] \Longrightarrow [n^2 = 3q, q \in \mathbb{Z}]$$ $$[n = 3k+1, k \in \mathbb{Z}] \Longrightarrow [n^2 = 3q+1, q \in \mathbb{Z}]$$ $$[n = 3k+2, k \in \mathbb{Z}] \Longrightarrow [n^2 = 3q+1, q \in \mathbb{Z}]$$ $$\left([n = 3k, k \in \mathbb{Z}] \vee [n = 3k + 1, k \in \mathbb{Z}] \vee [n = 3k + 2, k \in \mathbb{Z}]\right)$$ $$\Longrightarrow \left([n^2 = 3q, q \in \mathbb{Z}] \vee [n^2 = 3q+1, q \in \mathbb{Z}]\right)$$

We have explicitly proved statements two, three and four, while the last can be logically deduced from the previous three statements. The first one we did not prove, but if it has been proved before you can simply use it here.

-
aha, sorry, I was confused by your comment you added to my answer (now deleted)... –  Tomas Sep 8 '11 at 19:31
@Tomas: Yes, I removed it as I posted this answer, and I thought it was a bit too nitpicky anyway ;) –  TMM Sep 8 '11 at 20:41

Proof is easy ($k \in Z$)

1) if $n = 3k$, $n^2 = 9k^2$, QED

2) if $n = 3k + 1$, then $n^2 = 3kn + n = 3kn + 3k + 1$, QED

3) if $n = 3k + 2$, then $n^2 = 3kn + 2n = 3kn + 6k + 3 + 1$, QED

-

You can unify the cases via variable remainder. Division Algorithm $\rm\Rightarrow n = 3\ q + r,\ r\in \{0\ 1\ 2\}\:.\:$ So $\rm\: n^2 = (3\:q+r)^2 =$ $\rm\: 3\:(3\:q^2+2\:q\:r)+r^2 =$ $\rm\:3\:Q + r^2\:.\:$ For $\rm\:r\in \{0\ 1\}\:,\:$ $\rm\:r^2 = r\$ so $\rm\:n^2 = 3\:Q+r,\ r\in\{0\ 1\}\:.\:$ Else $\rm\:r = 2\$ so $\rm\:r^2 = 3+1\:,\:$ so $\rm\:n^2 = 3\:Q+3+1 = 3\:(Q+1)+1\:.\ \$ QED

It's simpler via mod arithmetic: $\rm\ \{0\ \:\pm1\}^2\ \equiv\ \{0\:\ 1\}\pmod{3}\ \$ exploiting $\rm\ 2\:\equiv\: {-}1$

Another useful case is $\rm\ odd^2\ \equiv \{\pm 1\:\ \pm3\}^2\: \equiv\ 1\pmod{8}\ \$ exploiting $\rm\ 5\:\equiv\: {-3},\ \ 7\:\equiv\: {-1}$

This is one of many examples where simplification entails by employing remainders (residues) of least magnitude - also called a balanced system of representatives for the residue classes.

-

Let me try a slightly different tack... Let us use the terminology of modular arithmetic, which is the same thing you wrote, but denoted differently. Let $n \equiv 0\ \mathrm{mod}\ 3$. Then $n^2 \equiv 0\ \mathrm{mod}\ 3$. Next, for $n \equiv 1\ \mathrm{mod}\ 3$, we have $n^2 \equiv 1\ \mathrm{mod}\ 3$. Lastly, for $n \equiv 2\ \mathrm{mod}\ 3$, we have $n^2 \equiv 4 \equiv 1 \ \mathrm{mod}\ 3$. Therfore, the possibility that $n^2 \equiv 2\ \mathrm{mod}\ 3$ is impossible; i.e., it cannot be of the form $3q+2$.

-
I JUST learned about this Wednesday it amazes me how you were able to see this in the problem that needs proved –  Dennis Hayden Sep 8 '11 at 13:32
@George: This is not what Dennis wrote, but denoted differently. It's a proper proof, whereas what Dennis wrote has lots of gaps and errors and doesn't treat the $3q+2$ case at all. (I'm writing this because Dennis asked us to proof-read his proof, and it's not helpful to him if you imply that it's correct when it isn't.) –  joriki Sep 8 '11 at 13:34
@joriki: You are right. Dennis Hayden: Sorry, I didn't mean to imply that you solved it. But your approach was right. I just put it in a more fancy language, and completed it(implicitly using a multiplicative property of modular arithmetic; please check that it is used to see what happens with $n^2$.). –  George Sep 8 '11 at 13:42
This is very nice and elegant way to see the solution, but you must first prove that $\mathbb Z\ \mathrm{mod}\ 3$ is an algebraic group and that you can use multiplication in this way. –  Tomas Sep 8 '11 at 14:46

When working by cases, you need to go through all three of them. So you should square $3q$ and find $(3q)^2=9q^2=3k$ for $k=3q$, then square $3q+1$ and $3q+2$ and find they equal $3k+1$ for some $k$. Under case two, you need an equal sign between the two lines. You skipped squaring $3q+2$. You also need parentheses around $3q+1$ when you square it-$3q+1^2\ne(3q+1)^2$. But the basic idea is fine.

-

To answer your question: The basic idea of studying residue classes modulo 3 one at a time is very much ok, and your proof should be fine, after you fix the typos observed by several people.

For a slightly different way of using the same idea let me propose the following. Let $n$ be any integer. Then the number $$n^2(n^2-1)=n\cdot\bigl((n-1)n(n+1)\bigr)$$ is always divisible by 3, because it has 3 consecutive integers: $n-1,n,n+1$ as factors, and one of them is divisible by 3. Because 3 is a prime number, this means that either $n^2$ or $n^2-1$ must also be divisible by 3. But that's exactly what you wanted to show.

-