Proof that if $n^2-1$ is divisible by $8$ then $n$ is odd

Question

I am still very new to proofs. I am just getting some practice, as I am still struggling with the concepts. Any feedback would be greatly appreciated. Thank you in advance.

Claim: If $n^2-1$ is divisible by $8$, then $n$ is odd.

Proof: Suppose $n$ is even; that is, $n=2k$, for some $k \in \mathbb{Z}$. Then, $n^2-1 = (2k)^2-1$, which is odd. Therefore, $n$ must be odd and thus, contradicts our assumption that $n$ is even.

This is my second practice proof I am working on so please be gentle! I am still learning the logic and working through the proofs slowly. Any feedback, tips, or hints/tricks would be greatly appreciated! Thanks.

Answer 1

As you have used the tag number-theory, solution with modular arithmetic: $n^2-1\equiv 0\pmod{8}$ or, $n^2\equiv 1\pmod{8}$, if $n$ is even then we need to check two cases, $n=2k$, with $(2,k)=1$ and $n=2^t\cdot m$ for $t\ge 2$. If $n=2k$ then, $n^2\equiv 4k^2\equiv 1\pmod{8} $ implies $k^2\equiv 4^{-1}\pmod{8}$, as, $4$ has no inverse $\pmod{8}$, the equation can't be satisfied with any $n=2k$ and for $t\ge 2$,$n=2^t\cdot m,n^2\equiv 0\pmod{8}$. Now, if $n$ is odd, $$n^2\equiv 4p^2+4p+1\equiv 4p(p+1)+1\equiv 1\pmod{8}$$ as $p(p+1)\equiv 0\pmod{2}$ for any $p\in \mathbb{N}$. Hence done. $\boxed{}$

Answer 2

In your problem, proof-by-contradiction works as follows:

(Hypothesis) Suppose 8 divides $n^2-1$.

(Assumption) Let us assume that $n$ is even.

$n$ is even $\implies$ $n=2k$ for some $k \in \mathbb{Z}$

Then, $n^2-1 = (2k)^2-1$

$n^2-1 = 2(2k^2)-1 \implies n^2-1 $ is an odd number.

$n^2-1$ is odd $\implies$ 8 does not divide $n^2-1$.

Contradiction! That is, assuming n is even contradicts our hypothesis (i.e., $n^2-1$ is divisible by 8).

So our assumption is wrong. This means $n$ has to be odd.

Alternatively, we can prove the contrapositive (i.e., Proving $A\implies B $ is equivalent to proving $ \neg B \implies \neg A $ ). This works as follows in your case:

Suppose $n$ is even.

Then, $n = 2k$ for some $k \in \mathbb{Z}$

$\implies$ $n^2-1 = (2k)^2-1$

$\implies$ $n^2-1 = 2(2k^2)-1$

$\implies$ $n^2-1$ is odd.

$\implies$ $n^2-1$ is not divisible by 8.

Thus, we have proved this: $n$ is not odd $\implies$ $n^2-1$ is not divisible by 8, which is equivalent to proving this: $n^2-1$ is divisible 8 $\implies n$ is odd.

Answer 3

You can also prove this by the direct approach. Notice that if $n^2-1$ is divisible by $8$, then $n^2-1=8k$ for some integer $k$. Then $n^2=8k+1=2(4k)+1$. Letting $4k=j$ gives us $n^2=2j+1$ which is an odd integer. Since $n^2$ is odd, it follows that $n$ must also be odd. (Q.E.D.)

Hope this really helps you! :)

Answer 4

Yes $8$, as an even number, cannot divide a number unless that number is even. (For the number would then be a multiple of $8$, which in turn is a multiple of $2$; so the number would be a multiple of $2$ also, that is, even)

But, as you have shown, $n$ even implies $n^2-1$ is odd.

Your proof, however, doesn't mention divisibility by $8$, and what it implies; as well as circling around unnecessarily at the end. What I mean is, once you get that $n$ is odd you should be done (no need for a contradiction heaped on top of that; it's what you wanted to prove.) But, it's beside the point, for, as I mentioned, your proof was incomplete... Hang in there and it will get easier...

Answer 5

Assume to the contrary that $n$ is even. That is, $n = 2k$ for some integer $k$.

Then

$$n^2 - 1 = (2k)^2 - 1 = 2(2k^2) - 1$$

Note that this is an odd number which is clearly not divisible by $8$ (an even number).