Prime Number Test - Proof please?

Question

Found this in a Advanced GMAT Quant book....

Havent seen this anywhere else and would be interested in the proof for it if anyone can supply...

For all Prime numbers, p > 5

p^2 -1 is divisible by 24

GMATLA · Answer

I have also never seen this formula before, but as we all know, prime numbers have some very creative tricks and rules associated with them. Since the number resulting from this formula will always be a factor of 24 then that means that the answer to (P^2)-1 will always have 3 factors of 2 and 1 factor of 3 (aka 3 * 2^3).

Prime numbers will always be odd, and a prime number ^2 will also always be odd. So to subtract one from that number will always give you an even number. Since the prime number has be to greater than 5, then the lowest number this formula will yield is 48. Any even number great than 4 that does not have 2 and a prime number as its only factor will always have at least 3 factors of 2. So the last number that has to be dealt with to explain this formula is the last factor of 3. As you can see below, every number is divisible by 3 which explains this. Unfortunately, I can not figure out why this formula will always yield a number divisible by 3. Does anyone else have any insight? Very interesting one.

7^2 = 49 - 1 = 48
11^2 = 121 - 1 = 120
13^2 = 169 - 1 = 168
17^2 = 289 - 1 = 288
19^2 = 361 - 1 = 360
23^2 = 529 - 1 = 528
29^2 = 841 - 1 = 840

To me, this formula is just one of the "it is what it is" type formulas. The proof could be very complicated, and in fact be no real help to you on test day. My advice is to commit this formula to memory, and if you see anything to do with this on test day, you will be golden. Most likely you will not see anything referring to this formula, but the more tricks, tips, patterns, and secrets like these you know, the more time you can save and the higher score you can achieve.

walker · Answer

S = p^2-1 = (p-1)*(p+1)

1) if p is a prime number and p>5, p is an odd number and both p-1 and p+1 are even integers and one of them is divisible by 4. So, S is divisible by 2*4=8

2) if we have 3 consecutive integers: (p-1), p, (p+1), one of them must be divisible by 3. p can't be divisible by 3 as it's a prime integer and greater than 5. Therefore, one of (p-1) or (p+1) is divisible by 3 and S is divisible by 3.

3) from 1&2 S is divisible by 3*8=24.

GMATLA · Answer

Well done walker! You are correct... I guess this is why I got a measly Q48 :oops:

Great insight

KarishmaB · Answer

A prime number greater than 3 is always of the form (6n+1) or (6n - 1) where n is a positive integer. Mind you, every number of the form (6n+1) or (6n - 1) is not prime but every prime (greater than 3) is of one of these forms. e.g. 5 = 6*1 - 1; 7 = 6*1+1; 11 = 6*2 - 1 etc

p^2 - 1 = (p-1)(p+1)

Since p is odd, (p is prime greater than 5), both (p-1) and (p+1) are even. Since (p-1) and (p+1) are consecutive even numbers, one of them will be divisible by 4. So (p-1)(p+1) has 8 as a factor. 
Since p is of the form (6n+1) or (6n - 1), one of (p-1) and (p+1) must be of the form 6n i.e. it must be divisible by 6.
Hence, (p-1)(p+1) has 3 as a factor.

Therefore, (p-1)(p+1) has 8*3 = 24 as a factor.

These are not important rules/formulas. You can deduce these from other things you know but then there are unlimited properties you can deduce. So just focus on learning the basics.

vdbhamare · Answer

Walker respect man!!!!1

Have one question though can negative number be prime? like -5, -3?

walker · Answer

No.

A prime number (or a prime) is a natural number  greater than 1  that has no positive divisors other than 1 and itself.

Prime Number Test - Proof please?

Prep Toolkit

Top 5 GMAT Debrief Videos

615 to 715 in 15 Days (Ria's Strategies)

More than Quant/Verbal Abilities: Speed vs. Accuracy

745 with Only Self-Prep and GMAT Club

From 555 to 765: 210-point Improvement

Perfect 805 Score Debrief by Julia

My Rewards