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
    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 $w$as conf$u$sed 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
    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.