Answer to Puzzle #15 Prime Squared Minus 1 Multiple of 24

Why is that if p is a prime number bigger than 3, then p2-1 is always divisible by 24 with no remainder?

Right this one took me a while, it's kind of mathematical compared to the rest, but here goes...

Since I first posted this question I have found a more eloquent answer. My original answer is at the bottom of the page.

The solution relies on showing that p2 - 1 is a multiple of 2x2x2x3

First expand p2 - 1 to give:

p2 - 1 = (p - 1) x (p + 1)

Then consider the terms on the right hand side, firstly since we know that p must be odd, so p - 1 and p + 1 must be even. we have two of the factors we require.

Additionally since p - 1 and p + 1 effectively form 2 consecutive even numbers one of them must be a multiple of 4 thus we have another of our factors of 2. So far we have 2x2x2, now to get the factor of 3

p - 1, p & p + 1 form three consecutive numbers. in any three consecutive numbers one will be a multiple of 3, we know it is not p which is a multiple of 3, as this is prime, hence either p - 1 or p + 1 is a multiple. Therefore p2 - 1 has the factors 2, 2, 2 & 3 hence:

p2 - 1 = 24n

(Why must p be greater than 3? 3 is the only number which is both a multiple of 3 and prime)

If p is prime then it is not a multiple of 3 or indeed not a multiple of 8, or for that matter it is not a multiple of anything; but 3 and 8 are the most interesting as in our attempt to prove p2-1 = 24n if we can prove that p2-1is always divisible by 3 and 8 with no remainder then we have necessarily proven that it is also divisible by 24 with no remainder... (take a moment to make sure you understand this)

If p is not a multiple of 3 then p must = 3k + 1 or 3k + 2 where k is any positive integer.

If p is not a multiple of 8 then p must = 8k + 1,  8k + 2, 8k + 3....  ....8k + 7 where k is any positive integer.

For each of these expressions for p we must consider p2-1 and see if it is a multiple of 3 and 8 respectively.

 p p2-1 Multipl of... 3k + 1 9k2 + 6k 3 3k + 2 9k2 + 12k 3 8k + 1 64k2 + 16k 8 8k + 2 all terms of p even therefore not prime 8k + 3 64k2 + 48k + 8 8 8k + 4 all terms of p even therefore not prime 8k + 5 64k2 + 80k + 24 8 8k + 6 all terms of p even therefore not prime 8k + 7 64k2 + 112k + 48 8

I essence we see that for all values of p, p2-1 is a multiple of 3 & 8 and therefore 24. Simple.

BACK

© Nigel Coldwell 2013 - The questions on this site may be reproduced without further permission, I do not claim copyright over them. The answers are mine and may not be reproduced without my expressed prior consent. Please enquire using the link at the top of the page.