Given:
f(n) is the number of integers that:
1) is less than n
2) has no factors in common with n
Question: f(p) where p is a prime number.
If p is an even number, then half the numbers less than it would share a common factor (namely the number 2). However, the question is asking for prime numbers.
The answer is that NO number less than than a prime number share a factor as the prime number, by definition. Therefore, EVERY integer less than p has no factors and should be counted. This is how you get:
A) f(p) = p - 1 since you are not counting p itself.
Part of the trick is that you need to count 1 also. I thought about not counting this when looking at f(2) = count of (1)
Also, let's look at some other wording:
-if you are asking f(even number): All even numbers share the factor 2. Then you could also share certain odd numbers (example, 6 contains 3 as a factor, therefore, 1 and 5 are the only numbers less than 6 to count)
-if you are asking f(odd number): You need to determine if it shares with odds (15 would not count 5 and 3. I also shares a factor with 10 and 6, because they share the factor 5 and 3 respectively. however 8 is 2^3 so there is no common there)
- f(prime) is the special case of odd numbers (and the number 2) as described above, but easier to figure out.
gmat prep f(n)
This topic has expert replies
Source: Beat The GMAT — Problem Solving |
