Range of prime factor for even number + 1?

[skgmat]

Hi All,

I'd like to ask for help in understanding how to solve the below problem.

For every positive integer n, the function h(n) is defined to be the product of all the even integers from 2 to n, inclusive.If p is the smallest prime factor of h(100) + 1, then p is:

1) between 2 and 10
2) between 10 and 20
3) between 20 and 30
4) between 30 and 40
5) greater than 40

Also, please explain the core concept that is tested here so that I can solve other such problems.

Thank you.

[[email protected]]

Hi skgmat,

The main idea behind this prompt is:

"The ONLY number that will divide into X and (X+1) is 1."

In other words, NONE of the factors of X will be factors of X+1, EXCEPT for the number 1.

Here are some examples:
X = 2
X+1 = 3
Factors of 2: 1 and 2
Factors of 3: 1 and 3
ONLY the number 1 is a factor of both.

X = 9
X+1 = 10
Factors of 9: 1, 3 and 9
Factors of 10: 1, 2, 5 and 10
ONLY the number 1 is a factor of both.
Etc.

Since the H(100) is (100)(98)(96)....(4)(2)....we can deduce....
1) This product will have LOTS of different factors
2) NONE of those factors will divide into H(100) + 1.

H(100) contains all of the primes from 2 through 47, inclusive (the 47 can be "found" in the "94"), so NONE of those will be in H(100) + 1. We don't even have to calculate which prime factor is smallest in H(100) + 1; we know that it MUST be a prime greater than 47....and there's only one answer that fits.

Final Answer: E

GMAT assassins aren't born, they're made,
Rich

[skgmat]

Hi Rich,

Thanks for the reply.

Now, I got the concept that is tested in this question.

If you could please explain to the me the process of how you arrived at the conclusion that it should be a prime number more than 40? Is it by listing the primes mentioned in the ranges given in the answer choices and then figuring it out?

[[email protected]]

Hi skgmat,

The answer choices are VERY useful in answering this question (since I don't actually want to try to figure out the smallest prime factor of that gigantic number).

Since the h(100) is (2)(4)(6)(8)....(98)(100), we know that we're dealing with a gigantic number that has lots of factors. Since each of the 'pieces' of that product is EVEN, each can be broken down into '2' and an integer.

eg.
2 = (2)(1)
4 = (2)(2)
6 = (2)(3)
8 = (2)(4)
...
98 = (2)(49)
100 = (2)(50)

From this, we can see that EVERY positive integer from 1 to 50, inclusive, WILL be a factor of h(100); that includes ALL of the prime numbers in that range. Thus, the smallest prime number MUST be greater than 50 (and there's only one answer choices that matches this information).

GMAT assassins aren't born, they're made,
Rich

[Brent@GMATPrepNow]

For every positive even integer n, the function h(n) is defined to be the product of all even integers from 2 to n, inclusive. If p is the smallest prime factor of h(100) + 1, the p is

A: Between 2 & 10
B: Between 10 & 20
C: Between 20 & 30
D: Between 30 & 40
E: Greater than 40

Important Concept: If integer k is greater than 1, and k is a factor (divisor) of N, then k is not a divisor of N+1
For example, since 7 is a factor of 350, we know that 7 is not a factor of (350+1)
Similarly, since 8 is a factor of 312, we know that 8 is not a factor of 313

Now let's examine h(100)
h(100) = (2)(4)(6)(8)....(96)(98)(100)
= (2x1)(2x2)(2x3)(2x4)....(2x48)(2x49)(2x50)
Factor out all of the 2's to get: h(100) = [2^50][(1)(2)(3)(4)....(48)(49)(50)]

Since 2 is in the product of h(100), we know that 2 is a factor of h(100), which means that 2 is not a factor of h(100)+1 (based on the above rule)

Similarly, since 3 is in the product of h(100), we know that 3 is a factor of h(100), which means that 3 is not a factor of h(100)+1 (based on the above rule)

Similarly, since 5 is in the product of h(100), we know that 5 is a factor of h(100), which means that 5 is not a factor of h(100)+1 (based on the above rule)

.
.
.
.
Similarly, since 47 is in the product of h(100), we know that 47 is a factor of h(100), which means that 47 is not a factor of h(100)+1 (based on the above rule)

So, we can see that none of the primes from 2 to 47 can be factors of h(100)+1, which means the smallest prime factor of h(100)+1 must be greater than 47.

Answer = E

Cheers,
Brent

[Brent@GMATPrepNow]

Oops - double post

[skgmat]

Hi Rich & Brent,

Thank you both for the detailed explanation. That really helped!