If $n$ is odd and $3\not\mid n \Rightarrow \ 3\mid n+1 \text{ or } 3\mid n-1$

I'm proving that:

If $3\not\mid n$ and $n$ is odd $\Rightarrow 6\mid n^2 - 1$

First, I do this:

$$n^2 - 1 = (n-1)(n+1)$$ If the original proposition is true, then by unique factorization in $\mathbb{Z}$ it must be satisfied that: $$3\mid(n-1) \text{ or } 3\mid(n+1)$$

But I can't prove this fact. Can anyone help me? Thanks.

• I do not understand, you have just proved it, using unique factorization, though it is a little simpler to invoke Euclid's Lemma. To show $3$ divides $n^2-1$, note that $n\equiv \pm 1\pmod{3}$. – André Nicolas Jul 14 '16 at 16:52
• That's the wrong direction. Instead, from $\,3\nmid n\,$ it follows that $\,3\mid n-1\,$ or $\,3\mid n-2\,$ (by the Division Algorithm). But $\,3\mid n-2\,\iff 3\mid n+1.\$ Thus $\,3\mid (n-1)(n+1) = n^2-1.\ \$ – Gone Jul 14 '16 at 17:03
• @AndréNicolas Sorry, "deduce" was not the correct verb to describe my situation. I wanted to say that if $3\not|n$ and $n$ is odd $\Rightarrow 6|n^2 - 1$ we need that 3|(n+1) or 3|(n-1) but I haven't proved this fact. – Rubén Ballester Jul 14 '16 at 17:04
• You can do it all in one blow. If $n$ is odd and not divisible by $3$, then $n\equiv \pm 1\pmod{6}$, so $n^2\equiv 1\pmod{6}$. – André Nicolas Jul 14 '16 at 17:07
• @AndréNicolas, Bill Dubuque, Thank you, your answers have helped me to prove that fact. – Rubén Ballester Jul 14 '16 at 17:13

$3\not\mid n$ and $n$ is odd $\iff$ $n$ is of the form $6k\pm1$.

In this case, $n^2-1 = 36k^2+12k$ is a multiple of $6$ (it is even a multiple of $24$).

that $3|n-1$ or $3|n+1$ follows from the division alg. as $n$ is of the form $3q+r$, $r\in\{{1,2}\}.$ that $2$ divides $(n-1)(n+1)$ follows from this being even as $n$ is odd.

For sake of contradiction, presume $!(3|n-1$ or $3|n+1)$.

By DeMorgan's Law, $!(3|n-1$ or $3|n+1) \leftrightarrow !(3|n-1)$ and $!(3|n+1)$.

n is odd $\rightarrow$ n is an integer $\rightarrow$ $n (mod3) \in \{0, 1, 2\}$

This gives 3 cases:

Case 1:

$n(mod3) = 0 \rightarrow 3|n$ which contradicts $!(3|n)$

Case 2:

$n(mod3) = 1 \rightarrow n-1(mod3) = 1-1\rightarrow n-1(mod3) = 0 \rightarrow 3|n-1$ which contradicts $!(3|n-1)$.

Case 3:

$n(mod3) = 2 \rightarrow n+1(mod3) = 2+1 \rightarrow n+1(mod3) = 3 \rightarrow n+1(mod3) = 0 \rightarrow 3|n+1$ which contradicts $!(3|n+1)$.

Since all cases lead to a contradiction, $(3|n-1$ or $3|n+1)$.

Can you just look at $\mathbb{Z}$ modulo 3 and 2? You know that $n^2 \equiv 1( mod \ 3)$ and that $n\equiv 1 (mod \ 2)$. That's all the knowledge you need.

Any positive integer is of the form 3m,3m+ 1, or 3m+ 2. But 2= 3- 1 so this can also be written 3m+ 3- 1= 3(m+ 1)- 1. So any positive integer can be written 3m, 3m+ 1, or 3m- 1. If 3 does not divide n, n is of the form 3m+ 1 or 3m- 1. Further, if n is odd, then n- 1= 3m+ 1- 1= 3m or 3m-1- 1= 3m- 2, n+ 1= 3m+ 1+ 1= 3m+ 2 or 3m-1+ 1= 3m must be even. That means that m itself must be even so m= 2k and n= 3m+1= 6k+ 1 or n= 3m- 1= 6k- 1.

In the case n= 6k+ 1, n^2- 1= 36k^2+ 12k+ 1- 1= 36k^2+ 12k= 6(6k^2+ 2k). In the case n= 6k- 1, n^2- 1= 36k^2- 12k+ 1- 1= 36k^2- 12k= 6(6k^2- 2k).

In fact, it looks like you can say more- if n is an odd number, not divisible by 3, then n^2- 1 is divisible by 12.