Prime Numbers

Question

Hi Mike,

In this blog post, you wrote that there is no general rule as to finding prime numbers.
I know that 6n-1 and 6n+1 are rules to find prime numbers of 5 and above.

I would like to know what your take to that is....

Thanks

https://magoosh.com/gmat/2013/gmat-quant ... -problems/

mikemcgarry · Answer

Dear ronr34 , I'm happy to respond. :-)

I assume when you say " of 5 and above ", you mean that n is greater than or equal to five. Let's play with this a little. When n = 5, 6n - 1 = 29, and 6n + 1 = 31, both prime. When n = 6, 6n - 1 = 35, and 6n + 1 = 37, one prime, one not. When n = 7, 6n - 1 = 41, and 6n + 1 = 43, both prime. When n = 8, 6n - 1 = 47, and 6n + 1 = 49, one prime, one not. When n = 9, 6n - 1 = 53, and 6n + 1 = 55, one prime, one not. When n = 10, 6n - 1 = 59, and 6n + 1 = 61, both prime. When n = 11, 6n - 1 = 65, and 6n + 1 = 67, one prime, one not. Let's skip ahead: When n = 20, 6n - 1 = 119 = 7*17, and 6n + 1 = 121 = 11^2, neither of which is prime. That's the lowest entry of the "neither" case. As n gets bigger, the "two prime" case will become much rarer, and the "neither" case will become the most common in the long run. For example, between n = 150 (6n = 900) and n = 200 (6n = 1200), I count 14 cases of the "neither", 32 cases of the "one of each", and only 5 cases of the "both prime." As n goes into the thousands and millions, the "two prime" case will virtually disappear, the "one of each" case will become rare, and the "neither" case will become the norm. Primes get very very spread out when we get into higher and higher numbers. As I said in that blog, the pattern of prime numbers is the single hardest unsolved question in mathematics. It's connected to a very sophisticated mathematical theorem known as the Riemann Hypothesis . All of this is leagues beyond the GMAT, leagues beyond anything anyone would study in an undergraduate mathematics program. Suffice it to say, if some brilliant person actually figures out a pattern for predicting prime numbers, he would win the Fields Medal (the "Nobel Prize" of Mathematics) and would be the world's most famous mathematician. No simple formula that we can right with first-year algebra is going to cut it. I don't know exactly what the GMAT CLUB MATH BOOK says, but if it says that (6n + 1) and (6n - 1) are always prime, that's just dead wrong. Does all this make sense? Mike :-)

ronr34 · Answer

Yes thanks a lot!

mikemcgarry · Answer

To ronr34 and all,

I just want to emphasize, this 6n +/- 1 rule is useless.

Another GC user wrote

Quote:

....So I think the rule is correct for prime less than 100 for certain. Not an expert though but whenever I have seen questions on GMAT there are more likely to go with Primes less than 100 and sometimes may ask you to calculate no. primes between 2 given big nos but nothing beyond this....

I would say the best way to hunt for primes is the following ----
Suppose we are looking for the primes between, say 80 and 90. Well, immediately we know all even numbers larger than 2 can't be prime (2 is the only even prime number) and anything divisible by 5 (i.e. anything with 5 or 0 in the one's digit) is not prime. That leaves us with

{81, 83, 87, 89}

So the first rule, eliminate multiples of 2 and 5. Now, for multiples of 3, there's the great divisibility trick:
https://magoosh.com/gmat/2012/gmat-divis ... shortcuts/
If the digits add up to a multiple of 3, the number is divisible by 3.
You may know that 81 = 9^2, but if you don't see that, 8+1 = 9, and 9 is divisible by 3, so 81 must be divisible by 3.
For 83, 8 + 3 = 11, not divisible by 3, so 83 can't be divisible by 3.
For 87, 8 + 7 = 15, divisible by 3, so 87 must be divisible by 3.
For 89, 8 + 3 = 17, not divisible by 3, so 89 can't be divisible by 3.

That's leaves us with {83, 89}

So, step two was: use the divisibility rule to check for multiples of 3.

Finally, we have to eliminate multiples of 7. I would say, for a variety of reasons, it's very useful to know the multiples of 7 up to 100: the largest would be 7*14 = 98. If you know the multiples of 7, you know they include {... 77, 84, 91, ...} so the multiples of 7 pass through the 80s and do not land on either 83 or 89.

Once we have checked 2, 5, 3 and 7, then we have checked every prime number less than 10. That means, for any number less than a hundred, if it is not divisible by one of the prime factors less than 10, then the number must be a prime number. Therefore, 83 & 89 must be prime, and they are.

Again, the steps are:
1) Look at the last digit --- if it even or a multiple of 5, it's not prime.
2) Use the digits divisibility trick to check if the number is divisible y 3
3) Check divisibility by 7 (again, it's very handy to have the multiples of 7 memorized)
If a number less than 100 is not divisible by any of those, then its prime.

It would be exceedingly rare that the GMAT would ask you to determine whether a number greater than 100 is prime. If the number is between 100 and 200, follow those three steps, but then you would also have to check divisibility by 11 and 13 --- if a number less than 200 is not divisible by {2, 3, 5, 7, 11, 13}, then it is prime.

In case anyone is curious, the deeper logic here is: if we are trying to determine whether N is prime, we only have to check prime factors up to the square root of N. The square root of N is the "geometric mean" of all factors pairs of N --- for each factor of N less than the square-root of N, there must be a corresponding factor greater than the square root of N: these two would form a factor pair. If you check every prime factor up to the square-root of N, and none of these go evenly into N, then you have eliminated all possible factor pairs, and N must be prime. Here, for numbers less than 100, I suggest checking the single-digit primes, i.e. the primes up to 10, because sqrt(100) = 10, and for numbers less than 200, I suggest checking the primes up to 14, because sqrt(200) = sqrt(2)*10 ~= 14.14.

BTW, sometimes for factoring very big numbers, say 1599 or 8051, it's helpful to know some advanced factoring techniques.
https://magoosh.com/gmat/2012/advanced-n ... -the-gmat/
1599 = 1600 - 1 = (40)^2 - 1^2 = (40 - 1)(40 + 1) = 39*41 = 3*13*41 = complete prime factorization
8051 = 8100 - 49 = (90)^2 - (7^2) = (90 - 7)(90 + 7) = 83*97 = complete prime factorization

This three-step procedure above is a simplified version of what is sometimes called the Sieve of Archimedes. That three-step method I outline above is the best way to determine on the GMAT whether something is prime. Forget the 6n +/- 1 formula: it's totally useless.

Does all this make sense?
Mike :-)

Prime Numbers

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