x is the smallest integer greater than 1000 that is not prim

Question

x is the smallest integer greater than 1000 that is not prime and that has only one factor in common with 30!. What is x?

A. 1009
B. 1021
C. 1147
D. 1273
E. 50! + 1

Good question found this on veritas prep
Kudos me if you like the post

Bunuel · Accepted Answer

Note that we are told that x is not prime.

Next, x and 30! have only one factor in common means that this factor must be 1 (any two integers have 1 as a common factor). Thus no other factor of 30! is a factor of x. So, the least prime of x can be 31 (30! has all primes less than 30).

x cannot be 31*31 = 961 because it's less than 1,000.

The next prime is 37: 31*37 = 1147 > 1,000.

Answer: C.

arindamsur · Answer

What is the logic behind jumping from 31*31 to 31*37?

I started to solving the problem in same way. But I choose little long way 31*32 then 31*33 and so on..............

Bunuel · Answer

The least prime of x can be 31.

32, 33, 34, 35, and 36 are not primes. So, x cannot be 31*32, 31*33, 31*34, 31*35 or 31*36, because all these numbers have primes smaller than 31. The next prime after 31 is 37, hence we should check 31*37 after 31*31.

Hope it's clear.

sunny3011 · Answer

Not getting The Logic behind it ? any more elaboration please ?

Bunuel · Answer

Please read the stem carefully: x is the smallest integer greater than 1000   that is not prime  .

bhatiavai · Answer

We know that x is not Prime and that it should not share any factor with 30! other than 1. Please note that we are also asked to find the smallest Number Greater than 1000. Hence we pick a Prime number greater then 30 ie 31. But 31*31 is 961 < 1000.
we then use the next prime number which is 37. 31*37 = 1147. Please note that we are looking for the smallest prime greater than 30 as we are told that x should not have any factor of 30! other than 1.

KarishmaB · Answer

Certainly one of our tricky questions with a great takeaway!

If we start with the options, the way we often do when dealing with prime/composite numbers, we would get stuck. We are looking for a non-prime number so quite probably some of the options would be prime. Much as we might try, we will not find a factor for them and hence waste a lot of precious time.

Here, we do need to start from the question stem only. 
We need an integer that has nothing other than 1 in common with 30!. Which is the smallest such integer? It is 31, the next prime number. 
Similarly, if you were looking for the smallest number with no factor other than 1 in common with 31!, you would skip to 37. All integers between 31 and 37 are composite and hence would have factors lying between 1 and 31. Note that every composite number is made of prime factors. All composites less than 37 will be made up of 2 or more prime numbers less than 37.

32 = 2*2*2*2*2
33 = 3*11
34 = 2*17
35 = 5*7
36 = 2*2*3*3

This concept is extremely important.

If you want to make a composite number which has no primes till 30, you must use two or more primes greater than 30. The smallest prime greater than 30 is 31.

If you use two of them, you get 31*31 = 961 (not more than 1000)
So the two primes should be 31*37 = 1147 (greater than 1000)

Answer (C)

Bunuel · Answer

VERITAS PREP OFFICIAL SOLUTION:

Every positive integer has 1 as a factor, so 1 must be the common factor between 30! and x. Since x isn't prime, it must have at least two prime factors, neither of which is a factor of 30!. The smallest prime that isn't a factor of 30! is 31, so x is a multiple of 31. The smallest multiple of 31 that isn't prime and doesn't share any prime factors with 30! is 31 * 31, but that isn't big enough: 31 * 31 = 961. The next smallest multiple of two primes is 31 times the next prime, or 31 * 37 = 1147.

bumpbot · Answer

Automated notice from GMAT Club BumpBot: 

A member just gave Kudos to this thread, showing it’s still useful. I’ve bumped it to the top so more people can benefit. Feel free to add your own questions or solutions.

 This post was generated automatically.

x is the smallest integer greater than 1000 that is not prim

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

GMAT Problem Solving (PS) Questions

x is the smallest integer greater than 1000 that is not prim

Prep Toolkit

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