|
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)
My original answer:
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
|
