BREAKING: Target Test Prep releases Brand New 2026 On Demand GMAT prep course

Redeem

Factorial and primes

This topic has expert replies
Post new topic Post Reply
Previous Topic Next Topic
Junior | Next Rank: 30 Posts
Posts: 13
Joined: Mon May 09, 2011 10:19 am
Thanked: 3 times
GMAT Score:720

Factorial and primes

by sandeeptalla450 » Fri Jul 15, 2011 11:23 am
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, 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

OA is E

How to solve this?
Top
Source: — Problem Solving |
GMAT Instructor
Posts: 23
Joined: Thu Jun 09, 2011 11:34 pm
Location: New York City
Thanked: 17 times
Followed by:6 members

by Jim@Knewton » Fri Jul 15, 2011 10:09 pm
By definition:
H(100) = (2*4*6*.....*98 *100) ----(50 even terms within the parenthesis)
= > H(100) = 2^50(1*2*3*4....*49*50) ----(factoring 2 from each of the 50 even terms)
Thus H(100) is divisible by all primes between 1 & 50
=> H(100)+1 = 2^50(1*2*3*4....*49*50) + 1
1 is not evenly divisible by any of the primes between 1 & 50 => the least prime to divide H(100) has to be greater than 50 (In terms of primes, it must be greater than the highest prime below 50 which is 47)
{Note: For any number n = a*b*c, where a, b, c are positive primes greater than 1, if you add 1 to n, the resulting (n+1) cannot be divided by a or b or c.}

So for H(100)+1 = 2^50(1*2*3*4.......*49*50) + 1
=> by adding 1 the expression [H(100)+1] becomes indivisible by any of the primes in "1*2*3*4.......*49*50"
=> because of the nature of the answer choices, it is sufficient for us to know that the no prime under 50 is a factor of H(100)+1
We do not need to test for the value of factors of H(100)+1 beyond that.
Hence [spoiler]E: "greater than 40"[/spoiler]
Hope this helps... :-)
Best, Jim
Please "thank" this post if it helps you!
https://www.knewton.com/people/jims
Top
Junior | Next Rank: 30 Posts
Posts: 29
Joined: Tue Jul 12, 2011 1:07 pm
Thanked: 8 times
Followed by:1 members

by beatthegmat.garry » Fri Jul 15, 2011 10:11 pm
**Please note that the prime factors of h(n)+1 will be greater than the largest prime factor of h(n). As any factor of h(n) when divides H(n)+1 will give a remainder of 1.

So, h(100)=100*98*96....*2
=2^50(50*49*48.....*1)

We can see that any number between 1 to 50(including all the primes) will be a factor of h(n).

So we can conclude in conjunction with above property** that the smallest prime factor will be greater than 50 which seems to coincide with option E
Top
Post new topic Post Reply
• Page 1 of 1