Problem Solving

From one of the the Prep materials: I am unable to solve this. Can someone please explain? I will reveal the solution once I have a few answers, else it will kill the thrill.

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
Options:
A: Between 2 & 10
B: Between 10 & 20
C: Between 20 & 30
D: Between 30 & 40
E: Greater than 40

h(100) = 2 * 4 * 6 .... * 100
h(100) = 2*1 * 2*2 2*3 ...2 * 50.

This means h(100) has all numbers from 1 to 50 as a factor. So h(100) + 1 cannot have any of these numbers as its factor. So any factor of h(100)+1 is greater than 50. hence greater than 40.

So my answer is E.

polter wrote:From one of the the Prep materials: I am unable to solve this. Can someone please explain? I will reveal the solution once I have a few answers, else it will kill the thrill.

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
Options:
A: Between 2 & 10
B: Between 10 & 20
C: Between 20 & 30
D: Between 30 & 40
E: Greater than 40

Since the difference between them is 1, h(100) and h(100)+1 are consecutive integers. Consecutive integers are co-primes: they share no factors other than 1.

Let's examine why:

If x is a multiple of 2, the next largest multiple of 2 is x+2.
If x is a multiple of 3, the next largest multiple of 3 is x+3.

Using this logic, if we go from x to x+1, we get only to the next largest multiple of 1. So 1 is the only factor common both to x and to x+1. Integers that share no factors other than 1 are called coprimes.

Thus, in the problem above, h(100) and h(100)+1 are coprimes. They share no factors other than 1.

h(100) = 2 * 4 * 6 *....* 94 * 96 * 98 * 100

Factoring out 2, we get:

h(100) = 2^50 (1 * 2 * 3 *... * 47 * 48 * 49 * 50)

Looking at the set of parentheses on the right, we can see that every prime number between 1 and 50 is a factor of h(100). Since h(100) and h(100)+1 are coprimes, none of the prime numbers between 1 and 50 can be a factor of h(100)+1.

Thus, the smallest prime factor of h(100) + 1 must be greater than 50.

The correct answer is E.

Loved your explanations, esp. The concept of prime factors for co-primes. I wasn't aware of this.
The answer is indeed E, as you correctly stated.
I didn't even think in similar lines. This was my first diagnostic test.