Common Prime Factors

[niksdoon]

Hi, can anyone pls help me get this solve?

How many integers less than 1000 have no factors(other than 1) in common with 1000 ?

a. 400
b. 399
c. 410
d. 420

[singhvikramveer]

We can neglect numbers divisible by 2,5 in this case
1000/2 = 500

1000/5 = 200

But numbers divisible by both 2 and 5 need not be removed again

1000/10 = 100

i.e 1000 - (500+200) +100
=400

Only one factor is common i.e 1 removing that as well we are left with 399

Option B

[mschwrtz]

very elegant solution singhvikramveer. Just to be sure that everyone can follow it, let me signpost it a little:

First, singhvikramveer determined that it would be easier to subtract from 1000 all the numbers 1-1000 that share at least one factor (other than 1) with 1000, than to count directly those that do not share any such factor.

Second, he recognized that the only way to share a factor (other than 1) was to share a prime factor, that is to be a multiple of 2 or 5.

Third, he determined the number of multiples of 2 (500) and the number of multiples of 5 (200). This would be trickier if the starting value weren't 1.

Fourth, he recognized that he had counted twice all those values that are multiples of both 2 and 5. That is, he had counted each of the 100 multiples of 10 twice.

Fifth, he subtracted 100 to correct for that overcounting.

Finally, he recognized that 1 does not share any factors (other than 1) with 100, even though it is a multiple of neither 2 nor 5.

[rockrock]

how is that dividing by the prime factor tells us the "number" of multiples? as opposed to the actual factor itself?

i.e. how is is that 1000/2 = 500, tells us that there are 500 multiples?

[singhvikramveer]

First, singhvikramveer determined that it would be easier to subtract from 1000 all the numbers 1-1000 that share at least one factor (other than 1) with 1000, than to count directly those that do not share any such factor.

Second, he recognized that the only way to share a factor (other than 1) was to share a prime factor, that is to be a multiple of 2 or 5.

Third, he determined the number of multiples of 2 (500) and the number of multiples of 5 (200). This would be trickier if the starting value weren't 1.

Fourth, he recognized that he had counted twice all those values that are multiples of both 2 and 5. That is, he had counted each of the 100 multiples of 10 twice.

Fifth, he subtracted 100 to correct for that overcounting.

Finally, he recognized that 1 does not share any factors (other than 1) with 100, even though it is a multiple of neither 2 nor 5.

wow !! you sure explained this in and out... Thanks.

[RonPurewal]

how is that dividing by the prime factor tells us the "number" of multiples? as opposed to the actual factor itself?

i.e. how is is that 1000/2 = 500, tells us that there are 500 multiples?

in general, the number of multiples of some number "p", from p to "N", is N/p.

for instance, the number of multiples of 3, from 3 to 21, is 21/3 = 7.

[adiagr]

very elegant solution singhvikramveer. Just to be sure that everyone can follow it, let me signpost it a little:

Finally, he recognized that 1 does not share any factors (other than 1) with 100, even though it is a multiple of neither 2 nor 5.

Why will we remove 1?

The question asks us "How many integers less than 1000 have no factors (other than 1) in common with 1000 ?

1 does satisfy this condition.

[RonPurewal]

very elegant solution singhvikramveer. Just to be sure that everyone can follow it, let me signpost it a little:

Finally, he recognized that 1 does not share any factors (other than 1) with 100, even though it is a multiple of neither 2 nor 5.

Why will we remove 1?

The question asks us "How many integers less than 1000 have no factors (other than 1) in common with 1000 ?

1 does satisfy this condition.

adiagr is correct; 1 does indeed satisfy the condition stated in the problem, so i'm not sure why the original solution excludes it.

before we analyze this problem any further, however, we need to ascertain the source of the problem.
this folder is for OFFICIAL GMAT PREP PROBLEMS ONLY. this problem is definitely not an official problem -- in fact, it's fairly clear that this problem is not even designed to be gmat practice, since it has only four answer choices (ALL gmat problems have five answer choices).

so, unfortunately, in keeping with our forum rules, we'll have to kill this thread if the original poster does not come forward with the source of the problem.
ORIGINAL source, please -- please do not cite other forums as sources.
thanks.