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

Redeem

GMATPrep : Find the smallest prime factor

This topic has expert replies
Post new topic Post Reply
Previous Topic Next Topic
Junior | Next Rank: 30 Posts
Posts: 27
Joined: Tue Nov 10, 2009 2:29 pm
Thanked: 1 times

GMATPrep : Find the smallest prime factor

by anirban_lax » Thu Sep 09, 2010 3:01 pm
Hi

Please help me understand the solution to this problem that I encountered in GMATPrep Practice Test 1.

For every positive even integer n there is a function h(n) which is defined as a product of all even integers from 2 to n. What is the smallest prime factor of h(100) + 1?

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

O.A. 5

Thanks in advance.
Top
Source: — Problem Solving |
User avatar
GMAT Instructor
Posts: 1031
Joined: Thu Jul 03, 2008 1:23 pm
Location: Malibu, CA
Thanked: 716 times
Followed by:255 members
GMAT Score:750

by Brian@VeritasPrep » Thu Sep 09, 2010 4:39 pm
Hey anirban:

I love this question, and if you learn to love it, too, this thread - https://www.beatthegmat.com/prime-number ... tml#278895 - will give you a similar one for reinforcement.

When you're asked about divisibility, you can get a long way toward the answer by thinking in terms of prime factors. The set of numbers 2*4*6*8...*100 is one in which you can pull the 2s out of each even number to get:

2^50 * (1*2*3*4*5...*50)

Doing that allows you to see the real structure of the numbers you're working with. It's a bunch of 2s multiplied by 50!

Now let's consider the number 50!, since that's the number that will have all of the unique prime factors. 50! is a huge, huge number, but if we're only thinking in terms of prime factor divisibility, we know that 50! is divisible by:

2, 3, 5, 7...47 (all of the prime factors contained within 50!)

Now if we look at prime factors, let's start with few small ones:

Every SECOND number is a multiple of 2. 2, 4, 6, 8, 10... If we add 1 to any of those numbers, we break that every-second cycle, and the number is no longer divisible by 2 (2+1 = 3; 8+1 = 9; etc.)

Every THIRD number is a multiple of 3: 3, 6, 9, 12... If we add 1 to any of those, we're off of that every-third cycle and the number is no longer divisible by 3.


Essentially, if you take a number and add 1 to it, it's no longer divisible by any of its previous prime factors, because you've knocked it off of the cycle of each factor. Adding 1 to 50! means that it's no longer even, no longer ends in 0, etc. - we've changed over all its priime factors.

Therefore, the answer has to be E - 50! + 1 won't be divisible by any prime factors less than 50.
Brian Galvin
GMAT Instructor
Chief Academic Officer
Veritas Prep

Looking for GMAT practice questions? Try out the Veritas Prep Question Bank. Learn More.
Top
User avatar
GMAT Instructor
Posts: 3225
Joined: Tue Jan 08, 2008 2:40 pm
Location: Toronto
Thanked: 1710 times
Followed by:614 members
GMAT Score:800

by Stuart@KaplanGMAT » Thu Sep 09, 2010 5:17 pm
anirban_lax wrote:Hi

Please help me understand the solution to this problem that I encountered in GMATPrep Practice Test 1.

For every positive even integer n there is a function h(n) which is defined as a product of all even integers from 2 to n. What is the smallest prime factor of h(100) + 1?

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

O.A. 5

Thanks in advance.
Hi! This is THE most frequently question posted on the forum (in fact, it was just posted a day or two ago) - if you do a search on h(100) you'll find dozens of solutions.
Image

Stuart Kovinsky | Kaplan GMAT Faculty | Toronto

Kaplan Exclusive: The Official Test Day Experience | Ready to Take a Free Practice Test? | Kaplan/Beat the GMAT Member Discount
BTG100 for $100 off a full course
Top
Junior | Next Rank: 30 Posts
Posts: 27
Joined: Tue Nov 10, 2009 2:29 pm
Thanked: 1 times

by anirban_lax » Thu Sep 09, 2010 6:16 pm
Great explanation Brian! Can't thank you enough!

Stuart - thank you. That is surely an useful bit of info...I can check on a few alternative ways of tackling this problem.

Appreciate your help guys!

regards
Anirban
Top
Post new topic Post Reply
• Page 1 of 1