div and primes question

el_torero wrote:this question comes from the GMAT practice test software from mba.com. good luck.

dude is the answer a

the answer is E

h(n) = Product of all even integers from 2 to n, inclusive.

p = smallest prime factor of h(100) + 1. p is?

h(100) = 2*4*6*8*....*100

How many even numbers are there here? = 100/2 = 50 even numbers
Take a factor of 2 out from each of these even numbers:

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

=> h(100) + 1 = 2^50*50! + 1

Now, dividing this expression by any number from 1 to 50 will always yield a remainder of 1, since 2^50*50! is divisible by every number from 1 to 50 (since it contains 50! )

Thus, no number from 1 to 50 can be a factor of h(100) + 1.

Thus, the smallest prime factor must also be greater than 50. Pick E.

very smooth answer. thanks so much!

Here's the number property rule that's being tested with this problem:

If x is a positive integer, the only factor common to x and x+1 is 1; they share no other factors. Any factor of x (other than 1) will NOT be a factor of x+1.

Let's think about why this rule holds true.

If x is a multiple of 2, how much do we need to add to get to the next largest multiple of 2? 2. So the next largest multiple of 2 will be x+2.

If x is a multiple of 3, how much do we need to add to get to the next largest multiple of 3? 3. So the next largest multiple of 3 will be x+3.

If x is a multiple of 4, how much do we need to add to get to the next largest multiple of 4? 4. So the next largest multiple of 4 will be x+4.

Using this logic, if we add 1 to x, we get only to the next largest multiple of 1. So 1 is the only factor common to both x and x+1.

Thus, in the problem above, we know that 1 is the only factor common to h(100) and h(100) + 1. They share no other factors.

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

If from each of the 50 factors listed above we factor 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). This means that none of the prime numbers between 1 and 50 can be a factor of h(100) + 1, because h(100) and h(100) + 1 share no factors other than 1.

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

The correct answer is E.

Seriously, this is the #1 question posted on this site.

Try a search on h(100), you'll find dozens of threads, almost all of which have solutions posted by different experts.

Learn to love the search function!