1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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}$. $\endgroup$ – André Nicolas Jul 14 '16 at 16:52
  • 2
    $\begingroup$ 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.\ \ $ $\endgroup$ – Gone Jul 14 '16 at 17:03
  • $\begingroup$ @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. $\endgroup$ – Rubén Ballester Jul 14 '16 at 17:04
  • 1
    $\begingroup$ 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}$. $\endgroup$ – André Nicolas Jul 14 '16 at 17:07
  • $\begingroup$ @AndréNicolas, Bill Dubuque, Thank you, your answers have helped me to prove that fact. $\endgroup$ – Rubén Ballester Jul 14 '16 at 17:13
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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