9
$\begingroup$

Show that $n^2-1$ is divisible by $8$, if $n$ is an odd positive Integer. Please help me to prove that whether this statement is true or false.

$\endgroup$
10
$\begingroup$

If $n$ is an odd positive integer, then $n=2m+1$ for some non-negative integer $m$. Can you see how to finish? Hint- Do two cases , one where $m$ is odd and one where $m$ is even.

$\endgroup$
  • 4
    $\begingroup$ Combine this with the fact that $n^2-1=(n+1)(n-1)$. $\endgroup$ – copper.hat Sep 19 '12 at 15:52
10
$\begingroup$

Since $n$ is odd $n=4m+1$ or $n=4m+3$.

In the first case $n^2-1=(n-1)(n+1)=4m\cdot(4m+2)=8m(2m+1)$, while in the second case $n^2-1=(n-1)(n+1)=(4m+2)\cdot(4m+4)=8(2m+1)(m+1)$.

So $n^2-1$ is divisible by 8 if $n$ is odd.

$\endgroup$
4
$\begingroup$

This is a nice example of a direct proof. You start with the facts that if $\phi$ is your positive odd integer, then it is in the form $\phi = 2n + 1$ where $n$ is an integer and $\phi^2 - 1 = 8p \quad( p\in\mathbb Z) $ is true.


Recall that if a number is divisible by 8, then 8 is one of its factors.


This is something like a “case-by-case” proof. You prove the hypothesis for $n \in2\mathbb Z$ and then $n \in 2\mathbb Z + 1$.

Let's start with assuming that $n = 2m + 1$ where $m$ is an integer (of course) to prove for odd numbers. It is clear that,$$\begin{align} \phi^2 - 1 =(2n + 1)^2 - 1 &= 4n^2 + 4n \\ &= 4n(n + 1) \\ &= (8mn + 4n)(2m + 2) \\ &=4n\cdot 2\cdot(2m + 1)\cdot (m + 1) \\ & = 8 \cdot (n(2m + 1)(m +1)) \\ & = 8k \end{align} $$ $\rm 0.5\times Q.E.D $


Now $n = 2m$ which is gonna be easier. $$\begin{align}\phi^2 - 1 =(2n + 1)^2- 1 = 4n^2 + 4n &= 4n(n + 1) \\ &= 8mn(2m +1)\\&= 8(2m^2n + mn) \\ &=8k \end{align}$$


Q.E.D

(yay)

$\endgroup$
3
$\begingroup$

Viewing the integer numbers modulo 8, write $a \equiv b$ for $8|(a-b)$.

(This structure, $\mathbb Z_8$ is generated by $8\equiv 0$ and is friendly with operations $+$ and $\cdot$.)

We have the following set of odd numbers: $\{ 1,3,5,7\}$. Or, rewriting by $5\equiv-3$ and $7\equiv -1$, this is only $$\{ 1,3,-3,-1\}$$ The squares of these: $$(\pm 1)^2 = 1\ \text{ and }\ (\pm 3)^2=9\equiv 1$$

$\endgroup$
3
$\begingroup$

Note that $n^2 - 1 = (n+1)(n-1)$. Because n is odd, both $n+1$ and $n-1$ are even. Let $m=n-1$. Noting that $2|m$, consider both $m$ and $m+2$ mod 4. After we see that either $m$ or $m+2$ is divisible by 4, we know that $m(m+2) = (2k)(4l) = 8kl$. (WLOG due the the commutativity of multiplication)

$\endgroup$
2
$\begingroup$

If $n$ is odd, then $n=8q+r$ with $r\in \{ 1,3,5,7 \}$. Then $n^2=64q^2+16qr+r^2=8(8q^2+2r)+r^2$. Thus, it suffices to prove that $r^2-1$ is divisible by $8$, which can be done by a simple calculation.

$\endgroup$
  • 1
    $\begingroup$ Nice try @Ihf, you deserve vote up $\endgroup$ – Saharsh Sep 19 '12 at 16:20
2
$\begingroup$

My favorite proof method is proof by induction. It consists of two steps:

  1. you assume that it's true for $n$, and prove that it then has to be true for $n+2$ (next odd number) as well
  2. prove that it's true for $n = 1$

Then, since it's true for 1 it's also true for 3 (from your first step), for 5, 7, etc.

$(n+2)^2 - 1 = n^2 + 4n + 4 - 1 = (n^2 - 1) + 4 (\overbrace{n+1}^{even} )$

We assumed the first term is divisible by 8, and the second is too. Now show that it's true for $n=1$:

$ n^2-1=1-1=0 $

which is divisible by 8.

$\endgroup$
1
$\begingroup$

$\rm n\ odd\, \Rightarrow\, n = 4k\pm 1\:$ so $4$ divides one of $\rm\:n\pm1,\:$ and $2$ divides other, so $\rm\,8\:|\:(n\!-\!1)(n\!+\!1) = n^2\!-1.$

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