3
$\begingroup$

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

  • 0
    Also the case 1 should look something like $(3q)^2 = 9q^2 = 3(3q^2)$.2011-09-08
  • 0
    Thanks for that one I don't know how I forgot that (3q)^2 =9q^22011-09-08
  • 0
    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.2011-09-08
  • 0
    I want to ask how about now... but I am sure there is something I missed.2011-09-08
  • 0
    @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.2011-09-08
  • 0
    For your final sentence, you want to say "In conclusion, $n^2$ must be of form $3q$ or $3q+1$ as shown above." You still have a stray $3k$ and two stray $3k+1$s. I would use "of the form 3k (or 3k+1)" instead of "of the form 3q (or 3q+1)" to avoid confusion with the other use of q. I would also take out "still" in the 3q case. But it is improving2011-09-08
  • 0
    @Jyrki I really like that idea I will rewrite the proof.2011-09-08
  • 0
    I think it looks much better now. (but what do I know :P)2011-09-08

6 Answers 6

1

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.

5

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

3

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.

  • 0
    aha, sorry, I was confused by your comment you added to my answer (now deleted)...2011-09-08
3

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.

1

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

  • 0
    I JUST learned about this Wednesday it amazes me how you were able to see this in the problem that needs proved2011-09-08
  • 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.)2011-09-08
  • 0
    @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$.).2011-09-08
  • 0
    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.2011-09-08
1

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.