prime number

Question

Hi,
If a number less than 100 is not divisible by any prime divisor less than 10, then the number has to be prime. And, of course, the only prime divisors less than 10 are 2, 3, 5, and 7. So those are the only divisors we have to check. It's not divisible by any of those numbers, it is a prime number. So for example, here's a practice problem.

Then what about those bigger than 100, and why?

Thanks a lot in advance

EMPOWERgmatRichC · Answer

Hi arbre, When multiplying two positive integers together to get a larger, third number, there are a number of relationships that will exist. If the two numbers are EQUAL, then you have a 'perfect square' - for example (10)(10) = 100. In all other cases though, with that same result (in this case, 100), ONE of the two starting numbers will be LESS than 10 and ONE will be GREATER than 10 (for example (5)(20) or (4)(25)). The pattern that you're asking about is in regards to Prime Factorization (re: the idea that every positive integer greater than 1 is either a Prime number or the product of some Primes). Since 10^2 = 100, with any number LESS than 100, if we're looking to see whether the number is Prime or not, we'll only need to divide by 2, 3, 5 and/or 7 - since the next prime is 11 and 11^2 = 121 (which is too big - and if 11 is one of the Prime Factors in the number, then we'll find it by dividing by one of the smaller primes). For any number that is GREATER than 100, we may need to consider larger primes, but we can use perfect squares - along with this concept - to determine which, if any, additional calculations are required. For example, with 143 - and the knowledge that 11^2 = 121, we need to consider dividing by 11 (along with 2, 3, 5 and 7) to determine whether 143 is prime or not. GMAT assassins aren't born, they're made, Rich Contact Rich at: Rich.C@empowergmat.com

KarishmaB · Answer

To understand this concept, check out these two blog posts: https://anaprep.com/number-properties-f ... ct-square/ https://anaprep.com/number-properties-f ... ct-square/

ScottTargetTestPrep · Answer

Let's say the number is 101. The square root of 101 is roughly 10, so again we only need to check prime numbers less than 10. You can verify that 101 is not divisible by 2, 3, 5, and 7. Had 101 not been prime, it would have at least two prime factors. Since we know it is not divisible by 2, 3, 5, or 7, the smallest possible prime decomposition of 101 would be 11 * 11, which is already greater than 101. We know 101 cannot have a prime factor greater than 11 because that assumption would lead to a product which is even greater than 11 * 11. Similarly, 101 cannot have more than two prime factors, again we would have a product which is greater than 11 * 11. We see that the smallest possible prime decomposition of 101 is greater than 101, which means that 101 itself must be a prime number.

In general, if you know that x is not divisible by primes that are less than √x, then x itself must be prime. You can use the above reasoning to see this. If x were not prime, then it would have at least two prime factors and both of those factors would be greater than √x. Since the product of two numbers greater than √x is greater than x, x cannot have two prime factors, which means that x must be a prime number.

prime number

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