Welcome to MindCipher, a social repository of the world's greatest brain teasers, logic puzzles and mental challenges.

Multiples of 8 plus 1

Squaring the first several odd numbers reveals the following pattern: 3 squared = 8 + 1 5 squared = 24 + 1 7 squared = 48 + 1

8, 24, and 48 are all multiples of 8. Does this pattern hold for all squares of odd numbers? Prove it!

Let n be an odd integer, and assume as a base case that n^2 is one more than a multiple of 8. The next higher odd integer is given by n+2, since we're skipping the even integer in between. Expanding (n+2)^2 gives n^2 + 4n + 4. We assumed that n^2 is one greater than a multiple of 8, so we need to show that 4n + 4 is always a multiple of 8 to prove the pattern. Factoring out a 4 gives 4(n+1). Since n is an odd number, n+1 must be even and therefore divisible by 2. So 4n+4 is divisible by 4 and by 2 and therefore is also divisible by 8. So we've added a multiple of 8 to our n^2 term preserving congruence in mod 8. Assuming that n^2 is one more than a multiple 8, (n+2)^2 must also be one more than a multiple of 8! Use one of the examples given in the problem as a base case and the inductive proof is complete.

Comments


Rahul Kumar

PROOF: Let p be any odd no. (2p+1)^2-1 =4p^2 + 4p +1-1 =4p^2 + 4p =4(p^2 + p) ----(1) clearly when p is an odd no. then p^2 is also an odd no. thus p^2+p is an even no.(as sum of two odd no. is an even no.) let say, p^2 + p =2 x; then eqn (1) becomes: (2p+1)^2-1 = 4(p^2 + p) =42x = 8x proved...

  

Vishal barot

excellent


Charlie

There sure are a lot of smart people here with a lot of really clever answers. However, you all forgot one thing: 1^2=1 1+1=2

And 2 is not a multiple of 8.


Charlie

There sure are a lot of smart people here with a lot of really clever answers. However, you all forgot one thing: 1^2=1 1+1=2

And 2 is not a multiple of 8.


city_slick

Very interesting proof. Are there any other patterns like this that exist among square (or nth powers in general)?

  

Sean Moran

Yes, there are many patterns among powers. I've been kind of trying to figure out all of them, maybe one day I will & it'll be like my magnum opus or something. As someone hinted up above for squares the difference between the squares of any 2 integers, positive or negative, is 2k + 1, where k is the lower number, so between 1^2 & 2^2 it's 2(1) + 1, between 5^2 & 6^2 it's 2(5) + 1, etc. I also found that for cubes, it's 6k(triangular number ending in k) + 1. I'm sure there are more.

  

Aakash

Whoa, the triangular number sounds surprising..could you explain it with another example? If we have 2 and 3: 2^3 = 8, 3^3 = 27.

In this case, what's our "triangular number ending in k"?

  

Sean Moran

Well k is the lower number, so for the difference between, say, 6^2 and 7^2, k would be 6. The difference involves the sequence 1 + 2 + 3 + 4..., and according to Wikipedia, that sequence is triangular numbers. So the difference between 3^2 and 4^ would be 6k(1 + 2 + 3) + 1, or 37. Incidentally, this means for powers up to 3, the difference involves factorials, as the difference between any 2 consecutive integer powers of 1 is 1, the difference between powers of 2 involves 2 (2! or 2 * 1), and for cubes it's 6 (1 * 2 * 3). Then each next power involves adding something weird to the mix, like triangular numbers.

  

Aakash

So interesting...I'll check wikipedia out for some proofs.

  

Sean Moran

I don't think they have any proofs for powers as a whole, which is kind of surprising, as they have proofs of like everything else and have had 1000's of years to do it. Especially if someone like me could come up with a couple in like 10 years.

  

city_slick

Ah too bad - you publish any of these, by chance?

  

Sean Moran

I'm not a mathematician, I just loooooove math. I also don't know any mathematicians (minus random people on the internet who I don't really know).

  

city_slick

Fair enough - I'm an engineer...I know just enough math to be dangerously wrong sometimes. You might enjoy this one if you haven't seen it already.


Sean Moran

Sorry I write a lot (and talk a lot).

  

Aakash

No worries - solid explanation!


Jango

Butts.


hardikasawa

Odd number squares can be written as : (2n-1)^2 , n>1 (2N-1)^2 = 4nn - 4n +1 =4n(n-1) + 1 For any n>1 , n(n-1) will always be even => 4n(n-1) + 1 => 8*x +1 where x=n(n-1)/2

hence Odd no square can always be written as 8x+1


Del

I kind of ended up with something similar, but I didn't quite use a formal proof. I noticed right away that 8 was multiplied by a triangular increasing number, or that it was the sum + x, or n(n+1)/2. You can multiply this by 8 and get 4n(n+1) + 1 = x^2. With a little work you can then notice the pattern in x, is that it is 2n+1, or the progression of odd numbers. In summary, 4n(n+1) + 1 = (2n+1)^2

  

Heather Moore

Yeah I think I might have done something closer to that the first time I did it, and this time through I went ahead and did it inductively. Very nice!


aliya

any odd integer can be written as 2k+1, k is an integer >=1 for this problem => (2k+1)^2 = 4k^2 +4k+1 = 4k(k+1) + 1 k, k+1 are consective integers, hence one is even =>k(k+1) = 2n =>4k(k+1) + 1 = 8n +1 and we are done

  

Heather Moore

Or 2k-1 if you want to include 1. Well phrased solution, thanks.


Ravi

Agreed, great solution!


Adam Larson

A little Python code to illustrate the proof:

Import Pylab:

from pylab import *

m=0 c=0 k = [1,3,5,7,9,11,13,15,] for x in k: m=m+c c=c+1 n=m8+1 print (x,'^2 = 8 ',m,'+ 1','=',n) print ('The multiple of 8 increases by the sequence 0,1,3,6,10, etc...') print ('In other words: 1, then 2, then 3, etc... is added to the multiple at each iteration.')

Execute:

1 ^2 = 8 * 0 + 1 = 1 3 ^2 = 8 * 1 + 1 = 9 5 ^2 = 8 * 3 + 1 = 25 7 ^2 = 8 * 6 + 1 = 49 9 ^2 = 8 * 10 + 1 = 81 11 ^2 = 8 * 15 + 1 = 121 13 ^2 = 8 * 21 + 1 = 169 15 ^2 = 8 * 28 + 1 = 225 The multiple of 8 increases by the sequence 0,1,3,6,10, etc... In other words: 1, then 2, then 3, etc... is added to the multiple at each iteration.


Abdulla Kaleem Abdul Ghafoor
for($i=1;$i<50;$i++){

if($i%2 != 0){
if((($i*$i)-1) % 8 ==0){
    echo  (($i*$i)-1)/8;
    echo "* 8 are :";
    echo  ($i*$i)-1;echo "<br>";

}
}

}


Виктория Яцкова

Yes. (2n + 1)^2 = 4 n(n + 1) + 1 = [as n or n+1 is even => n(n+1) is even => n( n + 1) = 2m ] = 4 * 2m + 1 = 8m + 1


Ravi S Tiwari

The product of n consecutive integers is always divisible by n! [i.e. n factorial, where 0! = 1, 1! = 1, 2!= 2x1, 3!=3x2x1, 4!=4x3x2x1, and so on for positive integer n.] Now let us take the odd number under test as (2n+1) for all n>=1. .............. (Theorem)

So, if p = (2n+1)^2 ......................(1) then, p = 4n^2 + 4n + 1 .....................(2) => p = 4n(n+1) + 1 ............................(3)

Now, as n is a positive integer greater than or equal to 1, n(n+1) is the product of two consecutive integers, which by above stated theorem, will always be divisible by 2! = 2. Thus for some positive integer k , n(n+1) = 2k ........................(4)

Substituting (4) in (3), we get,

p = 4n(n+1) + 1 = 4(2k) + 1 = 8k + 1 for some positive integer k.

Thus, p = 8k+1 ..............................(5)

Hence Proved. Q.E.D.


Charles Loft

A variation is the difference of squares of any two odd numbers is always a multiple of 8.

(2r-1)^2 = 4r^2 -2r +1 (2(r+n) -1)^2 = 4r^2 +8nr =4n^2 -4r -4n +1

The difference = 4n^2 +8nr - 4n

8nr has 8 as a factor. The remaining terms 4n^2-4n = 4n(n-1) Since n or n-1 has to be even, 4n(n-1) has to to be a multiple of 8 also hence as required!

  

Charles Loft

the last equals sign in the long line of working should be a + , sorry!

Check out other puzzles:
Random  

Like this? You might also like:
What Number Is It?
Measuring Up
Bit Pair Swap
Submitted by
Heather Moore
about 4 years ago
Likes
Difficulty 4.5 ?

Tags
Math number theory proof


Back