this question comes from the GMAT practice test software from mba.com. good luck.
div and primes question
This topic has expert replies
- albatross86
- Master | Next Rank: 500 Posts
- Posts: 392
- Joined: Sun May 16, 2010 2:42 am
- Location: Bangalore, India
- Thanked: 116 times
- Followed by:10 members
- GMAT Score:770
h(n) = Product of all even integers from 2 to n, inclusive.
p = smallest prime factor of h(100) + 1. p is?
h(100) = 2*4*6*8*....*100
How many even numbers are there here? = 100/2 = 50 even numbers
Take a factor of 2 out from each of these even numbers:
h(100) = 2^50 * (1*2*3*4*....*50) = 2^50*50!
=> h(100) + 1 = 2^50*50! + 1
Now, dividing this expression by any number from 1 to 50 will always yield a remainder of 1, since 2^50*50! is divisible by every number from 1 to 50 (since it contains 50! )
Thus, no number from 1 to 50 can be a factor of h(100) + 1.
Thus, the smallest prime factor must also be greater than 50. Pick E.
p = smallest prime factor of h(100) + 1. p is?
h(100) = 2*4*6*8*....*100
How many even numbers are there here? = 100/2 = 50 even numbers
Take a factor of 2 out from each of these even numbers:
h(100) = 2^50 * (1*2*3*4*....*50) = 2^50*50!
=> h(100) + 1 = 2^50*50! + 1
Now, dividing this expression by any number from 1 to 50 will always yield a remainder of 1, since 2^50*50! is divisible by every number from 1 to 50 (since it contains 50! )
Thus, no number from 1 to 50 can be a factor of h(100) + 1.
Thus, the smallest prime factor must also be greater than 50. Pick E.
~Abhay
Believe those who are seeking the truth. Doubt those who find it. -- Andre Gide
Believe those who are seeking the truth. Doubt those who find it. -- Andre Gide
- GMATGuruNY
- GMAT Instructor
- Posts: 15539
- Joined: Tue May 25, 2010 12:04 pm
- Location: New York, NY
- Thanked: 13060 times
- Followed by:1906 members
- GMAT Score:790
Here's the number property rule that's being tested with this problem:
If x is a positive integer, the only factor common to x and x+1 is 1; they share no other factors. Any factor of x (other than 1) will NOT be a factor of x+1.
Let's think about why this rule holds true.
If x is a multiple of 2, how much do we need to add to get to the next largest multiple of 2? 2. So the next largest multiple of 2 will be x+2.
If x is a multiple of 3, how much do we need to add to get to the next largest multiple of 3? 3. So the next largest multiple of 3 will be x+3.
If x is a multiple of 4, how much do we need to add to get to the next largest multiple of 4? 4. So the next largest multiple of 4 will be x+4.
Using this logic, if we add 1 to x, we get only to the next largest multiple of 1. So 1 is the only factor common to both x and x+1.
Thus, in the problem above, we know that 1 is the only factor common to h(100) and h(100) + 1. They share no other factors.
h(100) = 2 * 4 * 6 *....* 94 * 96 * 98 * 100
If from each of the 50 factors listed above we factor out 2, we get:
h(100) = 2^50 (1 * 2 * 3 *... * 47 * 48 * 49 * 50)
Looking at the set of parentheses on the right, we can see that every prime number between 1 and 50 is a factor of h(100). This means that none of the prime numbers between 1 and 50 can be a factor of h(100) + 1, because h(100) and h(100) + 1 share no factors other than 1.
So the smallest prime factor of h(100) + 1 must be greater than 50.
The correct answer is E.
If x is a positive integer, the only factor common to x and x+1 is 1; they share no other factors. Any factor of x (other than 1) will NOT be a factor of x+1.
Let's think about why this rule holds true.
If x is a multiple of 2, how much do we need to add to get to the next largest multiple of 2? 2. So the next largest multiple of 2 will be x+2.
If x is a multiple of 3, how much do we need to add to get to the next largest multiple of 3? 3. So the next largest multiple of 3 will be x+3.
If x is a multiple of 4, how much do we need to add to get to the next largest multiple of 4? 4. So the next largest multiple of 4 will be x+4.
Using this logic, if we add 1 to x, we get only to the next largest multiple of 1. So 1 is the only factor common to both x and x+1.
Thus, in the problem above, we know that 1 is the only factor common to h(100) and h(100) + 1. They share no other factors.
h(100) = 2 * 4 * 6 *....* 94 * 96 * 98 * 100
If from each of the 50 factors listed above we factor out 2, we get:
h(100) = 2^50 (1 * 2 * 3 *... * 47 * 48 * 49 * 50)
Looking at the set of parentheses on the right, we can see that every prime number between 1 and 50 is a factor of h(100). This means that none of the prime numbers between 1 and 50 can be a factor of h(100) + 1, because h(100) and h(100) + 1 share no factors other than 1.
So the smallest prime factor of h(100) + 1 must be greater than 50.
The correct answer is E.
Private tutor exclusively for the GMAT and GRE, with over 20 years of experience.
Followed here and elsewhere by over 1900 test-takers.
I have worked with students based in the US, Australia, Taiwan, China, Tajikistan, Kuwait, Saudi Arabia -- a long list of countries.
My students have been admitted to HBS, CBS, Tuck, Yale, Stern, Fuqua -- a long list of top programs.
As a tutor, I don't simply teach you how I would approach problems.
I unlock the best way for YOU to solve problems.
For more information, please email me (Mitch Hunt) at [email protected].
Student Review #1
Student Review #2
Student Review #3
Followed here and elsewhere by over 1900 test-takers.
I have worked with students based in the US, Australia, Taiwan, China, Tajikistan, Kuwait, Saudi Arabia -- a long list of countries.
My students have been admitted to HBS, CBS, Tuck, Yale, Stern, Fuqua -- a long list of top programs.
As a tutor, I don't simply teach you how I would approach problems.
I unlock the best way for YOU to solve problems.
For more information, please email me (Mitch Hunt) at [email protected].
Student Review #1
Student Review #2
Student Review #3
- Stuart@KaplanGMAT
- GMAT Instructor
- Posts: 3225
- Joined: Tue Jan 08, 2008 2:40 pm
- Location: Toronto
- Thanked: 1710 times
- Followed by:614 members
- GMAT Score:800
Seriously, this is the #1 question posted on this site.
Try a search on h(100), you'll find dozens of threads, almost all of which have solutions posted by different experts.
Learn to love the search function!
Try a search on h(100), you'll find dozens of threads, almost all of which have solutions posted by different experts.
Learn to love the search function!
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