smallest prime factor

This topic has expert replies
Master | Next Rank: 500 Posts
Posts: 109
Joined: Sun Oct 21, 2012 5:10 am
Followed by:1 members

smallest prime factor

by psm12se » Mon Mar 11, 2013 6:14 am
For every positive even integer n, the function h(n) is defined to be the product of all the even integers from 2 to n, inclusive. If p is the smallest prime factor of h(100) + 1, the p is

1. between 2 and 10
2. between 10 and 20
3. between 20 and 30
4. between 30 and 40
5. greater than 40

GMAT/MBA Expert

User avatar
GMAT Instructor
Posts: 511
Joined: Wed Aug 11, 2010 9:47 am
Location: Delhi, India
Thanked: 344 times
Followed by:86 members

by Anju@Gurome » Mon Mar 11, 2013 6:18 am
psm12se wrote:For every positive even integer n, the function h(n) is defined to be the product of all the even integers from 2 to n, inclusive. If p is the smallest prime factor of h(100) + 1, the p is

1. between 2 and 10
2. between 10 and 20
3. between 20 and 30
4. between 30 and 40
5. 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.

The correct answer is E.
Anju Agarwal
Quant Expert, Gurome

Backup Methods : General guide on plugging, estimation etc.
Wavy Curve Method : Solving complex inequalities in a matter of seconds.

§ GMAT with Gurome § Admissions with Gurome § Career Advising with Gurome §

GMAT/MBA Expert

User avatar
GMAT Instructor
Posts: 16207
Joined: Mon Dec 08, 2008 6:26 pm
Location: Vancouver, BC
Thanked: 5254 times
Followed by:1268 members
GMAT Score:770

by Brent@GMATPrepNow » Mon Mar 11, 2013 7:21 am
psm12se wrote:For every positive even integer n, the function h(n) is defined to be the product of all the even integers from 2 to n, inclusive. If p is the smallest prime factor of h(100) + 1, the p is

1. between 2 and 10
2. between 10 and 20
3. between 20 and 30
4. between 30 and 40
5. greater than 40
Important Concept: If k is a positive integer that's greater than 1, and if k is a factor (divisor) of N, then k is not a divisor of N+1
For example, since 7 is a factor of 350, we know that 7 is not a factor of (350+1)
Similarly, since 8 is a factor of 312, we know that 8 is not a factor of 313

Now let's examine h(100)
h(100) = (2)(4)(6)(8)....(96)(98)(100)
Factor to get: h(100) = 2[(1)(2)(3)(4)....(48)(49)(50)]

Since 2 is in the product of h(100), we know that 2 is a factor of h(100), which means that 2 is not a factor of h(100) +1 (based on the above rule)

Similarly, since 3 is in the product of h(100), we know that 3 is a factor of h(100), which means that 3 is not a factor of h(100) +1 (based on the above rule)

Similarly, since 5 is in the product of h(100), we know that 5 is a factor of h(100), which means that 5 is not a factor of h(100) +1 (based on the above rule)

.
.
.
.
Similarly, since 47 is in the product of h(100), we know that 47 is a factor of h(100), which means that 47 is not a factor of h(100) +1 (based on the above rule)

So, we can see that none of the primes from 2 to 47 can be factors of h(100) +1, which means the smallest prime factor of h(100)+ 1 must be greater than 47.

Answer = E

Cheers,
Brent
Brent Hanneson - Creator of GMATPrepNow.com
Image