Problem involving prime factors

This topic has expert replies
Newbie | Next Rank: 10 Posts
Posts: 8
Joined: Wed Feb 07, 2007 6:32 pm
Thanked: 1 times

Problem involving prime factors

by wlvoh » Sat Feb 10, 2007 12:23 pm
The following is a doozy of a PS problem from a practice test on the Official GMAT Prep Software from GMAC. If anyone can help explain how to solve this one, I'd greatly appreciate it.

"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, 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 official answer is: E

(highlight to see the OA)

Thanks.

wlvoh

User avatar
Legendary Member
Posts: 2469
Joined: Thu Apr 20, 2006 12:09 pm
Location: BtG Underground
Thanked: 85 times
Followed by:14 members

Re: Problem involving prime factors

by aim-wsc » Sat Feb 10, 2007 1:12 pm
difficult indeed.
or maybe i lost number properties basics. :?

User avatar
Community Manager
Posts: 789
Joined: Sun Jan 28, 2007 3:51 pm
Location: Silicon valley, California
Thanked: 30 times
Followed by:1 members

by jayhawk2001 » Sat Feb 10, 2007 1:20 pm
I posted this on an earlier thread. Hope this helps.

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

2*50! can be expressed as a multiple of X (2 <= X <= 50) and so
(2*50! + 1) cannot be a multiple of of that same number X.

Since p is a factor of h(100) +1, p should be > X and so option
"E" looks like the correct answer.

User avatar
Legendary Member
Posts: 2469
Joined: Thu Apr 20, 2006 12:09 pm
Location: BtG Underground
Thanked: 85 times
Followed by:14 members

by aim-wsc » Sat Feb 10, 2007 1:36 pm
yeah thanks for the quick reply.
i knew that answer is E.

but i started thinking of the value of p :roll:
yeah! now thats really a wrong approach for GMAT i know... & i still fall in the trap. :(
it doesnt expect the value but the answer choice.... same applies for DS.... :?

thanks once again.
the value of p by the way would be far much higher than 40 for sure.

Newbie | Next Rank: 10 Posts
Posts: 8
Joined: Wed Feb 07, 2007 6:32 pm
Thanked: 1 times

Follow Up

by wlvoh » Mon Feb 12, 2007 5:16 am
jayhawk2001 wrote:I posted this on an earlier thread. Hope this helps.

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

2*50! can be expressed as a multiple of X (2 <= X <= 50) and so
(2*50! + 1) cannot be a multiple of of that same number X.

Since p is a factor of h(100) +1, p should be > X and so option
"E" looks like the correct answer.
Thanks for the help. But, in your explanation, one thing isn't quite right. The product 2*4*6*...*100 cannot be expressed as 2*50! It isn't a sum, so you can't simply factor out a single 2. Instead, you must factor out 2 from each element in the sum. So, actually, 2*4*6*...*100 is equal to:

(2^50) * 50!

I'm not sure if this makes any difference in the reasoning. Any thoughts?

Thanks.

wlvoh

User avatar
Community Manager
Posts: 789
Joined: Sun Jan 28, 2007 3:51 pm
Location: Silicon valley, California
Thanked: 30 times
Followed by:1 members

by jayhawk2001 » Tue Feb 13, 2007 10:36 pm
wlvoh, Yes, that is correct. The value is (2^50 * 50!) not 2*50!.

In anycase, the element to focus on is 50! and the rest of the logic should
follow as before.

Thanks.

GMAT/MBA Expert

User avatar
GMAT Instructor
Posts: 7223
Joined: Sat Apr 25, 2015 10:56 am
Location: Los Angeles, CA
Thanked: 43 times
Followed by:29 members

by Scott@TargetTestPrep » Wed Jun 20, 2018 4:27 pm
wlvoh wrote:The following is a doozy of a PS problem from a practice test on the Official GMAT Prep Software from GMAC. If anyone can help explain how to solve this one, I'd greatly appreciate it.

"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, 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
We are given that h(n) is defined to be the product of all the even integers from 2 to n, inclusive. For example, h(8) = 2 x 4 x 6 x 8.

We need to determine the smallest prime factor of h(100) + 1. Before determining the smallest prime factor of h(100) + 1, we must recognize that h(100) and h(100) + 1 are consecutive integers, and consecutive integers will never share the same prime factors.

Thus, h(100) and h(100) + 1 must have different prime factors. However, rather than determining all the prime factors of h(100), let's determine the largest prime factor of h(100). Since h(100) is the product of the even integers from 2 to 100 inclusive, let's find the largest even integer less than 100 that is the product of 2 and a prime number.

That even integer is 94 since since 2 x 47 = 94, which is less than 100. That means the largest prime factor of h(100) is 47. Notice that the next prime after 47 is 53, and 2 x 53 = 106, which is greater than 100.

Since 47 is the largest prime number that is a factor of h(100), all prime numbers from 2 to 47 are included in the prime factorization of h(100). Since we have mentioned that h(100) + 1 will not have any of the prime factors of h(100), all the prime factors in h(100) + 1, including the smallest one, must be greater than 47. Looking at the answer choices, only choice E can be the correct answer.

Answer: E

Scott Woodbury-Stewart
Founder and CEO
[email protected]

Image

See why Target Test Prep is rated 5 out of 5 stars on BEAT the GMAT. Read our reviews

ImageImage

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 » Wed Jun 20, 2018 4:33 pm
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

A: Between 2 & 10
B: Between 10 & 20
C: Between 20 & 30
D: Between 30 & 40
E: Greater than 40
Important Concept: If integer k is greater than 1, and 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)
= (2x1)(2x2)(2x3)(2x4)....(2x48)(2x49)(2x50)
Factor out all of the 2's to get: h(100) = [2^50][(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