BREAKING: Target Test Prep releases Brand New 2026 On Demand GMAT prep course

Redeem

Prime Numbers

This topic has expert replies
Post new topic Post Reply
Previous Topic Next Topic
Senior | Next Rank: 100 Posts
Posts: 54
Joined: Sun Jan 01, 2012 4:24 am

Prime Numbers

by ChessWriter » Tue Feb 28, 2012 12:05 pm
I came across an interesting way to test whether a number is prime or not. The method can only be used limitedly as I have explained in the last paragraph.

If you are given a prime number(n), then n squared minus 1 is always a multiple of 12

Example. To test 13
Step 1: Square 13 = 169
Step 2: Substract 1 = 169-1 = 168
Step 3: Check if this is a multiple of 12. 168 is indeed a multiple of 12. Therefore 13 is a prime number.

I can myself square even large numbers in my head and divide them by 12. But if you are not able to do so, you can use this method a little differently.

Say you are given a large 6 digit prime number. You cannot first square it, substract 1 and then test it for divisibility by 12. That will take too long. But the method can still be useful because once you've determined the last two digits of a number(the units and the tens digit), then you can test it for divisibility by 4.

If the number is not divisible by 4, then it cannot be divisible by 12 and the number being tested is not a prime number.

I will give an example of this:

Example. To test 113
Step 1: Determine the last two digits you would get on squaring 113. These digits are 69 (if you square 113 you get 12769)
Step 2: Substract 1 = 69-1 = 68
Step 3: Check if this is a multiple of 4. 68 is indeed a multiple of . Therefore you should square 113 completely and test for divisibility by 3.
Last edited by ChessWriter on Tue Feb 28, 2012 2:34 pm, edited 1 time in total.
Top
Source: — Problem Solving |
Senior | Next Rank: 100 Posts
Posts: 54
Joined: Sun Jan 01, 2012 4:24 am

by ChessWriter » Tue Feb 28, 2012 12:07 pm
If you like this post above. Please let me know(by thanking me), I will then keep posting such little nuggets that I discover as I prepare further for my GMAT.
Top
Senior | Next Rank: 100 Posts
Posts: 54
Joined: Sun Jan 01, 2012 4:24 am

by ChessWriter » Tue Feb 28, 2012 12:09 pm
Any Experts reading this, please validate the method I've described above. Your word will give it the credibility that I cannot.
Top
User avatar
Master | Next Rank: 500 Posts
Posts: 143
Joined: Mon Mar 14, 2011 3:13 am
Thanked: 34 times
Followed by:5 members

by krusta80 » Tue Feb 28, 2012 2:46 pm
A few notes...

1. Obviously, this doesn't work for 2 and 3.

2. Therefore, any prime numbers that your formula applies to can neither be divisible by three nor by four:

[p mod 4 = 1] OR [p mod 4 = 3]
[p mod 3 = 1] OR [p mod 3 = 2]


3. Squaring p and then modding by 4 gives two possibilities:

[p mod 4] * [p mod 4] = 1 * 1 = 1
OR
[p mod 4] * [p mod 4] = 3 * 3 = 9 mod 4 = 1

Clearly, therefore, p^2 - 1 will always be evenly divisible by 4.


4. Squaring p and then modding by 3 gives two possibilities:

[p mod 3] * [p mod 3] = 1 * 1 = 1
OR
[p mod 3] * [p mod 3] = 2 * 2 = 4 mod 3 = 1

Clearly, therefore, p^2 - 1 will always be evenly divisible by 3 as well.


Therefore, your formula does hold for any prime number greater than 3. Nicely done.


5. The PROBLEM, however, is that the formula also works for any NON prime number whose prime factors do NOT include 2 or 3. For example, 25.

25^2 = 625
625 - 1 = 624
624 / 12 = 52

:/
Top
Senior | Next Rank: 100 Posts
Posts: 54
Joined: Sun Jan 01, 2012 4:24 am

by ChessWriter » Wed Feb 29, 2012 8:57 am
5. The PROBLEM, however, is that the formula also works for any NON prime number whose prime factors do NOT include 2 or 3. For example, 25.

25^2 = 625
625 - 1 = 624
624 / 12 = 52
Thanks. That is a good observation, it makes the formula usable with the addition of one more step(checking divisibility by 2 and 3 before squaring it).

Just to give forum members the modified method. Here are the steps :-

Suppose you are given a number, say 29 to test
Step 1: Check whether 29 is a multiple of 2 - Since its last digit is not 0,2,4,6 or 8, It is not divisible by 2
Step 2: Check whether 29 is a multiple of 3 - Adding up the digits 2+9=11 which is not a multiple of 3, therefore 29 is not a multiple of 3
Step 3: Now square 29. We get 841
Step 4: Substract 1 from 841 = 840
Step 5: Is 840 divisible by 12. Yes it is, therefore 29 is a prime number.
Top
User avatar
Master | Next Rank: 500 Posts
Posts: 143
Joined: Mon Mar 14, 2011 3:13 am
Thanked: 34 times
Followed by:5 members

by krusta80 » Wed Feb 29, 2012 12:51 pm
ChessWriter wrote:
5. The PROBLEM, however, is that the formula also works for any NON prime number whose prime factors do NOT include 2 or 3. For example, 25.

25^2 = 625
625 - 1 = 624
624 / 12 = 52
Thanks. That is a good observation, it makes the formula usable with the addition of one more step(checking divisibility by 2 and 3 before squaring it).

Just to give forum members the modified method. Here are the steps :-

Suppose you are given a number, say 29 to test
Step 1: Check whether 29 is a multiple of 2 - Since its last digit is not 0,2,4,6 or 8, It is not divisible by 2
Step 2: Check whether 29 is a multiple of 3 - Adding up the digits 2+9=11 which is not a multiple of 3, therefore 29 is not a multiple of 3
Step 3: Now square 29. We get 841
Step 4: Substract 1 from 841 = 840
Step 5: Is 840 divisible by 12. Yes it is, therefore 29 is a prime number.
I'm not sure how your added check stops 25 from being identified falsely as a prime number?
Top

GMAT/MBA Expert

User avatar
GMAT Instructor
Posts: 16207
Joined: Mon Dec 08, 2008 6:26 pm
Location: Vancouver, BC
Thanked: 5254 times
Followed by:1268 members
GMAT Score:770

by Brent@GMATPrepNow » Thu Mar 01, 2012 6:34 am
Let's take a closer look at the rule:

If n is a prime number greater than 3, then n^2 - 1 is a multiple of 12

To prove that this rule is true, we get to see several nice integer properties rules in action.

First, saying that n^2 - 1 is a multiple of 12, is the same as saying n^2 - 1 is divisible by 12, and this is the same as saying that the prime factorization of n^2 - 1 includes two 2's and one 3 (since 12=2x2x3)

So, let's prove that the prime factorization of n^2 - 1 includes two 2's and one 3.

Proof:
Notice that n^2 - 1 = (n-1)(n+1)
Also notice that n-1, n, n+1 are three consecutive integers.
Now, since we know that n is a prime number greater than 3, we know that n must be odd.
Since n-1 is the integer before n, we know that n-1 is even.
In other words, n-1 is divisible by 2.

Similarly, since n+1 is the integer after n, we know that n+1 is even. In other words, n+1 is divisible by 2.

Finally, there's a nice rule that says: If we have x consecutive integers, then 1 of those numbers must be divisible by x

Well, n-1, n, n+1 are three consecutive integers, so one of them MUST be divisible by 3. Since n is a prime number greater than 3, we know that n is not divisible by 3. So, it most be the case that either n-1 or n+1 is divisible by 3.

Okay, so here's what we know:
n-1 is divisible by 2
n+1 is divisible by 2
Either n-1 or n+1 is divisible by 3.
n^2 - 1 = (n-1)(n+1)
From this we can conclude that the prime factorization of n^2 - 1 includes two 2's and one 3.
In other words, n^2 - 1 is a multiple of 12.

Cheers,
Brent
Brent Hanneson - Creator of GMATPrepNow.com
Image
Top
User avatar
Master | Next Rank: 500 Posts
Posts: 143
Joined: Mon Mar 14, 2011 3:13 am
Thanked: 34 times
Followed by:5 members

by krusta80 » Thu Mar 01, 2012 6:55 am
Brent@GMATPrepNow wrote:Let's take a closer look at the rule:

If n is a prime number greater than 3, then n^2 - 1 is a multiple of 12

To prove that this rule is true, we get to see several nice integer properties rules in action.

First, saying that n^2 - 1 is a multiple of 12, is the same as saying n^2 - 1 is divisible by 12, and this is the same as saying that the prime factorization of n^2 - 1 includes two 2's and one 3 (since 12=2x2x3)

So, let's prove that the prime factorization of n^2 - 1 includes two 2's and one 3.

Proof:
Notice that n^2 - 1 = (n-1)(n+1)
Also notice that n-1, n, n+1 are three consecutive integers.
Now, since we know that n is a prime number greater than 3, we know that n must be odd.
Since n-1 is the integer before n, we know that n-1 is even.
In other words, n-1 is divisible by 2.

Similarly, since n+1 is the integer after n, we know that n+1 is even. In other words, n+1 is divisible by 2.

Finally, there's a nice rule that says: If we have x consecutive integers, then 1 of those numbers must be divisible by x

Well, n-1, n, n+1 are three consecutive integers, so one of them MUST be divisible by 3. Since n is a prime number greater than 3, we know that n is not divisible by 3. So, it most be the case that either n-1 or n+1 is divisible by 3.

Okay, so here's what we know:
n-1 is divisible by 2
n+1 is divisible by 2
Either n-1 or n+1 is divisible by 3.
n^2 - 1 = (n-1)(n+1)
From this we can conclude that the prime factorization of n^2 - 1 includes two 2's and one 3.
In other words, n^2 - 1 is a multiple of 12.

Cheers,
Brent
Brent, thank you for reproving my proof in a different way, but I would appreciate it if someone with your status would reiterate that n NEED NOT be prime for n^2 - 1 to be divisible by 12.

The original poster seems to be strongly implying that checking n^2-1 for divisibility by 12 is a way of determining whether n is prime, which is NOT correct.

In other words...

A -> B does NOT always indicate B -> A
Top

GMAT/MBA Expert

User avatar
GMAT Instructor
Posts: 16207
Joined: Mon Dec 08, 2008 6:26 pm
Location: Vancouver, BC
Thanked: 5254 times
Followed by:1268 members
GMAT Score:770

by Brent@GMATPrepNow » Thu Mar 01, 2012 7:17 am
krusta80 wrote: The original poster seems to be strongly implying that checking n^2-1 for divisibility by 12 is a way of determining whether n is prime, which is NOT correct.

In other words...
A -> B does NOT always indicate B -> A
You're absolutely right. The original poster suggested that if n^2 - 1 is divisible by 12 then n is prime, and this is NOT correct.

Examples:
25^2 - 1 is divisible by 12, but 25 is not prime
35^2 - 1 is divisible by 12, but 35 is not prime
49^2 - 1 is divisible by 12, but 49 is not prime
77^2 - 1 is divisible by 12, but 77 is not prime
etc.

So, we can use the rule (If n is a prime number greater than 3, then n^2 - 1 is a multiple of 12) to help us determine whether a number is divisible by 12, but we cannot reverse the rule to determine whether or not a number is prime.

Cheers,
Brent
Brent Hanneson - Creator of GMATPrepNow.com
Image
Top
Senior | Next Rank: 100 Posts
Posts: 54
Joined: Sun Jan 01, 2012 4:24 am

by ChessWriter » Thu Mar 01, 2012 7:25 am
Brent@GMATPrepNow wrote:
krusta80 wrote: The original poster seems to be strongly implying that checking n^2-1 for divisibility by 12 is a way of determining whether n is prime, which is NOT correct.

In other words...
A -> B does NOT always indicate B -> A
You're absolutely right. The original poster suggested that if n^2 - 1 is divisible by 12 then n is prime, and this is NOT correct.

Examples:
25^2 - 1 is divisible by 12, but 25 is not prime
35^2 - 1 is divisible by 12, but 35 is not prime
49^2 - 1 is divisible by 12, but 49 is not prime
77^2 - 1 is divisible by 12, but 77 is not prime
etc.

So, we can use the rule (If n is a prime number greater than 3, then n^2 - 1 is a multiple of 12) to help us determine whether a number is divisible by 12, but we cannot reverse the rule to determine whether or not a number is prime.

Cheers,
Brent

Thanks for the analysis Brent. You are right.

But what if I write the rule differently:

If a number(n) is such that n^2-1 is not a multiple of 12, then it cannot be a prime number.

Will the rule be correct now?
Top
User avatar
Master | Next Rank: 500 Posts
Posts: 143
Joined: Mon Mar 14, 2011 3:13 am
Thanked: 34 times
Followed by:5 members

by krusta80 » Thu Mar 01, 2012 7:49 am
ChessWriter wrote:
Brent@GMATPrepNow wrote:
krusta80 wrote: The original poster seems to be strongly implying that checking n^2-1 for divisibility by 12 is a way of determining whether n is prime, which is NOT correct.

In other words...
A -> B does NOT always indicate B -> A
You're absolutely right. The original poster suggested that if n^2 - 1 is divisible by 12 then n is prime, and this is NOT correct.

Examples:
25^2 - 1 is divisible by 12, but 25 is not prime
35^2 - 1 is divisible by 12, but 35 is not prime
49^2 - 1 is divisible by 12, but 49 is not prime
77^2 - 1 is divisible by 12, but 77 is not prime
etc.

So, we can use the rule (If n is a prime number greater than 3, then n^2 - 1 is a multiple of 12) to help us determine whether a number is divisible by 12, but we cannot reverse the rule to determine whether or not a number is prime.

Cheers,
Brent

Thanks for the analysis Brent. You are right.

But what if I write the rule differently:

If a number(n) is such that n^2-1 is not a multiple of 12, then it cannot be a prime number.

Will the rule be correct now?
YES, that is correct. :)

if A -> B, then ~B -> ~A
Top

GMAT/MBA Expert

User avatar
GMAT Instructor
Posts: 16207
Joined: Mon Dec 08, 2008 6:26 pm
Location: Vancouver, BC
Thanked: 5254 times
Followed by:1268 members
GMAT Score:770

by Brent@GMATPrepNow » Thu Mar 01, 2012 7:51 am
ChessWriter wrote:
But what if I write the rule differently:

If a number(n) is such that n^2-1 is not a multiple of 12, then it cannot be a prime number.

Will the rule be correct now?
I'm not sure what you mean by "it" (as in "it cannot be a prime number")
Do you mean, "n cannot by a prime number"?
If so, then this is true.
In fact, this demonstrates something known as the contrapositive: If A -> B then we know that if ~B -> ~A (if ~B -> ~A is the contrapositive)

Warning: At this point, we're moving into some very esoteric territory. First of all, you don't need to know anything about contrapositives for the GMAT (the LSAT yes, but not the GMAT). Second, although the statement If integer n is such that n^2-1 is not a multiple of 12, then n cannot be a prime number is true, it might not be very useful in answering GMAT questions.

Cheers,
Brent
Brent Hanneson - Creator of GMATPrepNow.com
Image
Top
Senior | Next Rank: 100 Posts
Posts: 54
Joined: Sun Jan 01, 2012 4:24 am

by ChessWriter » Thu Mar 01, 2012 8:14 am
Thank you Brent.
By saying "It", I did mean n.

Your analysis and explanation has really stitched the whole thing nicely.
Top
Post new topic Post Reply
• Page 1 of 1