Quant - PS - Arithmetic

[polter]

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

[Anurag@Gurome]

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
= (2 * 1) * (2 * 2) * (2 * 3) * ... * (2 * 50)
= 2^(50) * (1 * 2 * 3 ... * 50)
Then h(100) + 1 = 2^(50) * (1 * 2 * 3 ... * 50) + 1
Now, h(100) + 1 cannot have any prime factors 50 or below, because dividing this value by any of these prime numbers will give a remainder of 1.

So, the correct answer is E.

[vineeshp]

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.

[GMATGuruNY]

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.

[polter]

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.