Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
    
Please check your edits-the post has become harder to read, not easier. There are some stray $3k$ and $3k=1$s around, "od" is not a word. You don't need to say "for some $k \in \mathbb{Z}$" when you have exhibited the value of $k$. You still need parentheses around $(3q+1)^2$. The first case has not resolved my earlier comment. –  Ross Millikan Sep 8 '11 at 13:58
    
I want to ask how about now... but I am sure there is something I missed. –  Dennis Hayden Sep 8 '11 at 14:09
    
@Dennis: Variables getting mixed up? The cases are $n=3k$, $n=3k+1$ and $n=3k+2$. It makes the structure of your solution clearer to state this. Then I would write it e.g. like $$(3k+1)^2=9k^2+6k+1=3q+1,$$ where $q=3k^2+2k$. In other words: to get $q$ appear in the final form, the number that you square should use another variable, like $k$, because $q$ and $k$ are not the same number. –  Jyrki Lahtonen Sep 8 '11 at 14:35

6 Answers 6

up vote 3 down vote accepted

Here's how I would further clean up your answer:


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.

share|improve this answer
    
aha, sorry, I was confused by your comment you added to my answer (now deleted)... –  Tomas Sep 8 '11 at 19:31

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

share|improve this answer

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.

share|improve this answer

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

share|improve this answer
    
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
1  
@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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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