Prove that if n is an odd integer, then $n^2-1$ is a multiple of 8

Question

I've gotten through proving this all the way to $\cfrac{K^2+K}{8}$, where $n=2K+1$. Since it says that $n^2-1$ is a multiple of 8, the result needs to be an integer, i.e, p (representing $K^2+K$) needs to be something like $2(K^2+K)$.

Is using $4K+1$ to represent n the only way to get around this? I'd prefer to use $2K+1$ because that's more obvious.

EDIT: My work

$(2k+1)^2-1=8j \\ 4k^2+4k+1-1=8j \\ 4k(k+1)=8j \\ 4(k^2+k)=8j \\ \cfrac{4(k^2+k)}{8}=j$

I realize I made a mistake with forgetting to divide 8 by 4. But still how does $\cfrac{(k^2+k)}{2}=j$ mean it's a multiple of 8?

Your first sentence is pretty obscure but it looks to me as if you have made a mistake with your algebra. Please post details of your working so that someone can help you. Note that $\frac{K^2+K}8$ is obviously not always an integer, eg, when $K=1$. — David, Aug 27 '18 at 02:56
Your argument starts by assuming what you are required to prove. This is not a sound method of inference. — Angina Seng, Aug 27 '18 at 04:49

score 5 · Answer 1 · answered Aug 27 '18 at 02:57

5

$(2k+1)^2-1=4(k^2+k)$ and $k^2+k$ is even

answered Aug 27 '18 at 02:57

Asinomás

105,651

How does this make it a multiple of 8 though? – user2793618 Aug 27 '18 at 03:08
1

@user2793618 if $k^2+k$ is even than $k^2+k=2m$ thus $4(k^2+k)=4(2m)=8m$ – ℋolo Aug 27 '18 at 03:18
Is it because you can represent $k^2+k$ as $2p$ and then you get $8p$? So then my question becomes why is $k^2+k$ even? – user2793618 Aug 27 '18 at 03:18
Never mind, figured it out. It's because $k^2+k = k(k+1)$ and an even times an odd is even. – user2793618 Aug 27 '18 at 03:23

score 3 · Accepted Answer · answered Aug 27 '18 at 02:58

3

$n = 2m + 1; \tag 1$

$n + 1 = 2m + 2; \tag 2$

$n - 1 = 2m; \tag 3$

$n^2 - 1 = (n + 1)(n - 1) = (2m + 2)(2m) = 4m(m + 1); \tag 4$

at least one of $m, m + 1$ is even; thus

$m(m + 1) = 2k; \tag 5$

then

$n^2 - 1 = 4(2k) = 8k \Longrightarrow 8 \mid n^2 - 1. \tag 6$

answered Aug 27 '18 at 02:58

Robert Lewis

71,180

2

Huh this is very sneaky. I like it. – user2793618 Aug 27 '18 at 03:07
1

@user2793618: sneaky, eh? Not that I mind, in fact I'm chuckling as I write, but why "sneaky"? I mean, I just started with $n$ odd and took it from there . . . ;) – Robert Lewis Aug 27 '18 at 03:13
1

You used the definition of an even number to represent m(m+1), thereby allowing you to use the 4 present to make it 8k. – user2793618 Aug 27 '18 at 03:14
2

@user2793618: OK, I guess I'm all for "sneaky" mathematics, if it's rigorous! Cheers! – Robert Lewis Aug 27 '18 at 03:15

score 3 · Answer 3 · answered Aug 27 '18 at 03:06

3

Since $n$ is odd, $n\equiv 1$ or $n\equiv 3 \bmod 4$. In either case, one of $n-1,n+1$ is divisible by 2 and one by 4. Hence $n^2 - 1 = (n+1)(n-1)$ is divisible by 8.

answered Aug 27 '18 at 03:06

mheldman

737

score 1 · Answer 4 · answered Aug 27 '18 at 02:57

1

Use this technique

$$n = 2k + 1$$

Then,

$n^2 - 1 = 4k^2 + 4k = 4k \left( k + 1 \right)$

Now, since $k$ and $k + 1$ are consecutive integers, either $k$ is even or $k + 1$ is even. Therefore,

$$n^2 - 1 = 8k' \left( k + 1 \right)$$

OR

$$n^2 - 1 = 8kk''$$

where if $k$ is even, then $k = 2k'$ and if $k + 1$ is even then $k + 1 = 2k''$

Hence, in any case, $8$ divides $n^2 - 1$.

answered Aug 27 '18 at 02:57

Aniruddha Deshmukh

3,997
1
13
33

What is k prime and k prime prime? – user2793618 Aug 27 '18 at 03:05
1

They are just some other integers. – Aniruddha Deshmukh Aug 27 '18 at 03:14
How did you go from 4k(k+1) to 8k'(k+1)? – user2793618 Aug 27 '18 at 03:15
I wrote it in the answer that either $k$ is even or $k + 1$ is even. If $k$ is even then, $k = 2k'$, where $k' \in \mathbb{Z}$ and if $k + 1$ is even, then $k + 1 = 2k''$, where $k'' \in \mathbb{Z}$. – Aniruddha Deshmukh Aug 27 '18 at 03:16

score 1 · Answer 5 · answered Aug 27 '18 at 02:58

1

Proof:

An odd integer n is either a $4k+1$ or a $4k+3$.

$(4k+1)2 – 1 = 16k2+ 8k + 1 - 1 =8(2k^2 +k)$, which is a multiple of 8.

$(4k+3)2 – 1 = 16k2+ 24k + 9 - 1 =8(2k^2 +3k + 1)$, which is a multiple of 8

answered Aug 27 '18 at 02:58

tien lee

1,775

score 0 · Answer 6 · answered Aug 27 '18 at 03:37

Here is an inductive proof.

Denote $n=2k+1$ where $k=0,1,2,\cdots.$ Then $n^2-1=(2k+1)^2-1=4k^2+4k.$ We are to prove $4k^2+4k$ is a multiple of $8$.

Let $k=0$. Then $4k^2+4k=0$, which is a multiple of $8$. Assume it holds for $k=p$, namely $4p^2+4p=8q,q\in \mathbb{N}$. Then for $k=p+1$, we obtain $$4(p+1)^2+4(p+1)=(4p^2+4p)+8(p+1)=8q+8(p+1)=8(p+q+1),$$ which is also a multiple of $8$. Thus, by mathematical induction, we are done.

mr_e_man · Answer 7 · 2018-08-27T03:55:45.547

0

If you're talking about multiples, it often helps to use modular arithmetic. In this case, we only need to prove that $n^2-1=0$ for $n=1,3,5,7$, modulo $8$. But this is easy:

$$1^2=1$$ $$3^2=9=8+1=1$$ $$5^2=25=3*8+1=1$$ $$7^2=49=6*8+1=1$$

All larger odd numbers can be reduced to one of these four cases; if $m=8k+n$, where $n=1,3,5,$ or $7$, then

$$m^2=(8k+n)^2=(8k^2+2kn)*8+n^2=n^2$$

edited Aug 27 '18 at 03:55

answered Aug 27 '18 at 03:50

mr_e_man

5,364

Prove that if n is an odd integer, then $n^2-1$ is a multiple of 8

7 Answers7