For every positive integer n, the function h(n) is defined

[Borcho]

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

A. between 2 and 10

B. between 10 and 20

C. between 20 and 30

D. between 30 and 40

E. greater than 40

The answer is E. Could you please walk me through the solution?

[hdorai]

As per definition, the value h(100) = 2 x 4 x 6 x 8 x ....... x 100

This can be simplified as:

h(100) = 2 x [1 x 2 x 3 x .......50] = 2 x 50!

If you add 1 to the above number we will get 2 x 50! + 1 which is an odd number. If you look at the expression 2 x (50!), the largest prime number factor of this number is 47 (because 47 is the largest prime factor that is less than 50). So if you add 1 to the above expression, then I think its prime factor has to be greater than 47. So the answer is (E).

I am not sure about the above explanation. Requesting a better explanation from other members.

[Guest]

As per definition, the value h(100) = 2 x 4 x 6 x 8 x ....... x 100

This can be simplified as:

h(100) = 2 x [1 x 2 x 3 x .......50] = 2 x 50!

If you add 1 to the above number we will get 2 x 50! + 1 which is an odd number. If you look at the expression 2 x (50!), the largest prime number factor of this number is 47 (because 47 is the largest prime factor that is less than 50). So if you add 1 to the above expression, then I think its prime factor has to be greater than 47. So the answer is (E).

I am not sure about the above explanation. Requesting a better explanation from other members.

I think that hdorai's solution is perfectly correct. The last sentence (that any prime factor of H= h(100)+1 = [(2 x 50! )+1] must be greater than 47 can be proven using the "ab absurdo" method: first, assume that the reverse is true, then show that will lead us to an absurd result, so the reverse cannot be true and must be wrong.

Let's assume that there is a prime factor p of H, such that 1 < p <= 47: H = p x N N = positive integer.
Then p is a factor of 50! , and H can be written as: H = 2 x (p x M) + 1, for some positive integer M.

So: p x N = 2 (p x M) + 1
p (N - 2M) = 1 with p > 1, and N, M = positive integer, which is clearly not possible, q.e.d.

[StaceyKoprince]

Yep, you guys have got it! That's a really hard question, by the way.

[GMAT 2007]

Stacey,

Could you please explain the solution of the above problem, also how to approach the problem like this? I am not aware about 'ab absurdo' method. I am sure we haven't covered it in MGMAT Strategy guides too.

Thanks
GMAT 2007

[GMAT 2007]

Stacey/Dan?

GMAT 2007

[anadi]

SO n*p = 2^50 * p * m +1

p(n-2^50 * m) = 1

Which is not possible.

[StaceyKoprince]

This is a really rare question type, so I wouldn't worry about this too much. Any one person is extremely unlikely to see something like this on the test and, even if you do, it will be given as one of those impossible problems that the test expects you to either get wrong or spend way too much time on (and, frankly, probably both).

We can rewrite h(100) as 2 x [1 x 2 x 3 x .......50] = 2 x 50! and this will let us lay out the prime factors - that is, all of the prime numbers between 2 and 50 are prime factors of h(100).

2, for example, is a prime factor of h(100). Using logic, we can see that h(100) + 1 cannot have 2 as a prime factor as long as h(100) has 2 as a prime factor, because I've only added 1. I'd need to add 2 to maintain 2 as a factor. By the same logic, if 3 is a prime factor of h(100) then it cannot be a prime factor of h(100) + 1. Again, I've only added 1 and would need to add 3 to maintain 3 as a factor. Etc.

I can do that all the way up to 47, the largest prime factor of h(100). So, at the least, the smallest possible prime factor of h(100)+1 is larger than 47 and only one answer choice fits this criterion - E.

[Guest]

Although this piece of information does not affect our solution - it may be good to note that the factoring will produce:

2^50x50!
not 2x50!

since we're factoring a product of numbers (2 is taken from each number) and not a sum.

[puneet124]

This is a really rare question type, so I wouldn't worry about this too much. Any one person is extremely unlikely to see something like this on the test and, even if you do, it will be given as one of those impossible problems that the test expects you to either get wrong or spend way too much time on (and, frankly, probably both).

We can rewrite h(100) as 2 x [1 x 2 x 3 x .......50] = 2 x 50! and this will let us lay out the prime factors - that is, all of the prime numbers between 2 and 50 are prime factors of h(100).

2, for example, is a prime factor of h(100). Using logic, we can see that h(100) + 1 cannot have 2 as a prime factor as long as h(100) has 2 as a prime factor, because I've only added 1. I'd need to add 2 to maintain 2 as a factor. By the same logic, if 3 is a prime factor of h(100) then it cannot be a prime factor of h(100) + 1. Again, I've only added 1 and would need to add 3 to maintain 3 as a factor. Etc.

I can do that all the way up to 47, the largest prime factor of h(100). So, at the least, the smallest possible prime factor of h(100)+1 is larger than 47 and only one answer choice fits this criterion - E.

Dear Stacey
we can not rewrite the function like this
for ex h(10) = 2 x 4 x 6 x 8 x 10 =3480
if we could rewrite it as you said then it would be
h(10) = 2[1 x 2 x 3 x 4 x 5]
= 2[120]=240
which is absolutely wrong
please tell me am i correct or not
waiting for your reply
Regards
puneet

[pilkhanenilesh]

This is a really rare question type, so I wouldn't worry about this too much. Any one person is extremely unlikely to see something like this on the test and, even if you do, it will be given as one of those impossible problems that the test expects you to either get wrong or spend way too much time on (and, frankly, probably both).

We can rewrite h(100) as 2 x [1 x 2 x 3 x .......50] = 2 x 50! and this will let us lay out the prime factors - that is, all of the prime numbers between 2 and 50 are prime factors of h(100).

2, for example, is a prime factor of h(100). Using logic, we can see that h(100) + 1 cannot have 2 as a prime factor as long as h(100) has 2 as a prime factor, because I've only added 1. I'd need to add 2 to maintain 2 as a factor. By the same logic, if 3 is a prime factor of h(100) then it cannot be a prime factor of h(100) + 1. Again, I've only added 1 and would need to add 3 to maintain 3 as a factor. Etc.

I can do that all the way up to 47, the largest prime factor of h(100). So, at the least, the smallest possible prime factor of h(100)+1 is larger than 47 and only one answer choice fits this criterion - E.

Dear Stacey
we can not rewrite the function like this
for ex h(10) = 2 x 4 x 6 x 8 x 10 =3480
if we could rewrite it as you said then it would be
h(10) = 2[1 x 2 x 3 x 4 x 5]
= 2[120]=240
which is absolutely wrong
please tell me am i correct or not
waiting for your reply
Regards
puneet

It is [ 2* 2*2* 2*3* 2*4* 2*5]
= 2^5 [1*2*3*4*5]
=32*120 = 3480

[mschwrtz]

Nice catch pilkhanenilesh. puneet124, 2* 2*2* 2*3* 2*4* 2*5 is a single term (no addition or subtraction). You only factor if you have multiple terms. When you factor, you take the factor out of each term in the expression.

Now, let's never speak of this question again.

[desert.rose]

Hi,
h(n)= 2x4x6x...100=(2x1)x(2x2)x(2x3)x(2x4)x(2x5)......(2x50)=2^50 (1x2x3x...50)= 2^50 (50!)
I don't understand why everyone has written h(n)= 2(50!)

Have I done something wrong up there or every body else ?

[gokul_nair1984]

I don't understand why everyone has written h(n)= 2(50!)

@ Desert Rose:

The function h(n) is defined as 2*4*6*......*n

Therefore, h(100)=2*4*6*.....*100

Taking 2 common, h(100)= 2[1*2*3*.........*50]----(1)

But we know, 50*49*......*1 =50!; because n!=n(n-1)*(n-2) *...*1

Hence, (1) can be rewritten as h(100)=2*(50!)

[RonPurewal]

@ Desert Rose:

The function h(n) is defined as 2*4*6*......*n

Therefore, h(100)=2*4*6*.....*100

Taking 2 common, h(100)= 2[1*2*3*.........*50]----(1)

whoa, no. there's no such thing as a "common factor" in multiplication!

if you're going to try to invent and/or verify rules like this one, you should check them first, with very easy numbers; if you've invented "rules" that are actually incorrect, you should be able to find this out fairly quickly by plugging in some numbers.

for instance,
(2x1) x (2x2) x (2x3) is 48.
2 x (1x2x3) is 12, which is not equal to 48.
so this "rule" doesn't work.

--

in this case you are just rearranging a whole bunch of numbers that are all multiplied together, so you need to keep all of the 2's:
(2x1) x (2x2) x (2x3) x ... x (2x50)
= (2x2x2x2x2x...x2) x (1x2x3x...x49x50)

so desert rose is correct.