Prove that #a^2-1# is divisible by #8# for all odd integers #a# (induction)?

I am running into an issue when trying to prove the above statement using induction. My attempt is shown below (only mathematical steps and short explanation included, not formal proof):

If #a in ZZ# is odd, then #EE l in ZZ# s.t. #a=2l+1#, and if #8|a^2-1#, #EE m in ZZ# s.t. #8m=a^2-1#, so:

#8m=(2l+1)^2-1#

#8m=4l^2+4l+1-1#

Induction step, #n=k+1#

#8m=4(k+1)^2+4(k+1)-1#

#8m=4k^2+12k+8#

#8m=4(k^2-1)+12k+12#

#8m=4(8m)+12k+12#

#8m=8(4m)+12(k+1)#

But if I have #8m=8(4m)+8((3k)/2+3/2)#, the RHS #!inZZ#.

Any guidance would be greatly appreciated!

2 Answers
Teddy
Jul 4, 2018

See below.

Explanation:

#1^2-1=0# which is divisible by 8 (base case for #a=1#).
Since #a# is odd, write #a=2n-1, ninNN#.
Assume #(2n-1)^2-1# is divisible by 8.
#4n^2-4n+1-1# is divisible by 8.
Since #8n# is divisible by 8, we can add it to our expression.
#4n^2-4n+8n+1-1# is divisible by 8.
#4n^2+4n+1-1# is divisible by 8.
#:.(2n+1)^2-1# is divisible by 8.
Since #(2n+1)^2-1# is divisible by 8 whenever #(2n-1)^2-1# is divisible by 8 and #(1)^2-1# is divisible by 8, we have shown that #a^2-1# is divisible by 8 for all odd #a#.

Narad T.
Jul 4, 2018

Please see the proof below.

Explanation:

You can use modular arithmetic

We want to prove that

#a^2-1-=0 [mod8]#

#a^2-=1 [mod8]#

Let, #a=2k+1#, #k in NN#

Therefore,

#(2k+1)^2-=1[mod8]#

#4k^2+4k+1-=1[mod8]#

#4k^2+4k-=0[mod8]#

#4(k^2+k)-=0[mod8]#

#4k(k+1)-=0[mod8]#

But,

#k(k+1)# is divisible by #2#

Let #k(k+1)=2a#

Then

#4k(k+1)-=4*2a-=8a-=0[mod8]#

Related questions
Impact of this question
12728 views around the world
You can reuse this answer
Creative Commons License