# Thread: A Couple of Hard Questions from a CAT Exam Originally Posted by Md. Minuddin Just a small correction.
It (red 2) will be 250
yeah!! Thanks for the correction.I corrected it.   Reply With Quote

2. Originally Posted by finsisher take simple eg,,, h(100) = 2 *4*8*10......100 so ,= 2^50(1.2.3......25)= 2^50*2*2^2*2^3*2^4( 1.3.5.6.7.9.10.11.12.13.14.15.17.18.19.20.21.22.23 .24.25) and so on h(100)+1 will have a smallest prime no greater than 50 hence E  Reply With Quote

3. Here is my step by step approach to deal with this problem:

1. From the question we know that h(n) = the product of all even number from 2 to n.

So h(2) = 2 ; h(4) = 2 * 4 ; h(10) = 2 * 4 *6 * 8 * 10 and so on.

So h(100) = 2 * 4 * 6 * 8 * 10 * 12 *.........*100

h(100) +1 = (2 * 4 * 6 * 8 * 10 * 12 *.........*100) + 1

From the question: we want to find p which is the smallest prime factor for h(100) + 1
First we try to reduce the problem by using more simple case and c whether we can learn something from that:
Let's try

h(10) + 1 and find the smallest prime factor for h(10)

h(10) + 1 = (2 * 4 * 6 * 8 * 10) + 1

Prime factor means the prime number that can be divided from h(10) + 1 with out the remainder To give you a clearer picture let's try to divide h(10) + 1 with some prime numbers like 2, 3 and see what are the results.

(h(10) + 1) / 2 = h(10)/2 + 1/2
= (2 * 4 * 6 * 8 * 10)/2 + 1/2
from the first term (2 can be cancelled from 2 as 2 is factor of 2 itself)
= (4 * 6 * 8 * 10) + 0.5
= ( Integer ) + ( decimal)

So the answer gonna be Integer + decimal that means there is a remainder if we try to divide h(10) + 1 by 2
So, 2 is not a prime factor for h(10) + 1

Now let's try divide h(10) + 1 by 3
= (2 * 4 * 6 * 8 * 10)/3 + 1/3
= (2 * 4 * 2 * 8 * 10) + 1/3
(6 can be cancelled from the equation as 3 is a factor of 6)
so divide h(10) by 3 will give you (2 * 4 * 2 *8 * 10)
again it ends up with (integer) + (decimal)
which means 3 is not a prime factor for h(10) + 1

Consider those 2 examples again: at term h(10) which is (2 * 4 * 6 * 8 * 10)/p + 1/p
we learn from those 2 examples that if prime factor is a factor of any number in the first terms (h(10))
We will end up h(n)/p + 1/p with the decimal number every time as h(10)/p will be integer but 1/p is the decimal number.
So, we can conclude that any prime number that is a factor of h(10) is not a prime factor for the whole term h(10) + 1
since h(n)/p = Integer but 1/p is a decimal:
h(n)/p + 1/p won't be a whole number

That means 2, 3, 5, will not be a prime factor for this h(10) + 1 for sure as 2 is a factor of 2, and 3 is factor of 6, and 5 is factor of 10:

To find the exact smallest prime factor you might consume a plenty of time but if the the question give you the answer choices in the range of the number it will
be easy for you once you know the idea from h(10) case

Now let's go back to the original problem h(100) + 1

h(100) +1 = h(2 * 4 * 6 * 8 * 10 * 12 *.......*100) + 1

From the knowledge we learnt from h(10) we know that any prime number which is a factor of any number in first term (h(100))
will give you a decimal number in the end because
h(100)/p ---> integer but 1/p ----> decimal
so h(100) +1 is not a whole integer number which means that such a prime number is not a factor of h(100) + 1.

To find the smallest prime factor we should eliminate those prime factor that is divisible to h(100) first

h(100) = (2 *4 * 6 * 8 * 10 * ...* 100)

Let check at the multiple choice:

1. Between 2-10
Prime factor for 2-10 are (2, 3, 5, 7)
Give you some second to think about it you will found out that all of these prime factors are actually a factor of some number in the h(100)
To prove it you might try to multiply each of (2,3,5,7) by 2 (that will give you a set of 4 even number)
you will get (4, 6, 10, 14) respectively which are obviously appeared in the h(100)

So, divide h(100) + 1 with (2, 3 ,5 ,7) will give you (Integer) + (Decimal) which prove that these prime numbers are not a factor of h(100) + 1 for sure

2. Between 10-20
Let's consider the same way (11, 13, 17, 19) Just simply multiply each of them by 2
(Let's pick from the highest prime number between 10-20, which is 19)
Then you will c that even 19*2 = 38 which is still appeared in the h(100) there is no reason to multiply the rest of the list by 2 and find out whether they gonna appear in the h(100) since
All (11, 13, 17) each multiply by 2 will be the even number < 38 which is absolutely filled in the h(100)
so eliminate this choice.

3. Between 20-30
Let's consider the same way Try pick the largest prime factor in this range which is 29 then multiply by 2 that will give you 58.
As 58 is also appeared in the h(100) = h(2 * 4 * 6 * 8 * 10...l.. * 58....* 100)
So again eliminate this choice

4. Between 30-40
Pick the largest prime number in this range which is 37: 37 * 2 = 74 which is still appeared in the h(100) that means even 37 is still divisible to h(100)
and it will end up with h(100)/37 + 1/37 : Integer + decimal not a whole number again:
Eliminate this choice

5. Greater than 40
As we have eliminated all the choice above, so the smallest prime factor is supposed to be greater than 40 That's why this is the right answer.

I'm sorry for the long explanation since I tried to go step by step.
I hope this solution might give you another idea on how to attack this kind of problem in the exam.

To deal with any number properties problem, Trial and error, sometime, might be a key to get through it,
I recommend you trying to reduce your problem by simulate the similar case in the least complicate term
eg. h(100) to h(10) and apply the solution back to the original one.

This approach will allow you to conduct a trial and error approach in simpler way by dealing with smaller number of trail sets.
Believe me, if you are not too lazy to give yourself a try through that reduced term,
just a few second later u will find out the approach that can be applied to the original term.

Hope this is help, Vip  Reply With Quote

4. 1. I first tried to find the largest prime factor for h(100) because my logic was that the largest prime factor for h(100) would be pretty darn close to the largest prime factor for h(100)+1 AND because we were given ranges for the primes (I just needed to be in the ball park).

Listing out the integers of h(100) and its corresponding prime factors in parenthesis: h(100) = 2 (2) * 4 (2*2) * 6 (2*3)....98 (2*47) * 100 (2*5*5)

I saw from the list above that 98 had a prime factor of 47, and this was the highest from the list. Therefore, whatever I add to h(100), whether it's 1 or 100, the prime factor is greater than 47, or as the one of the solution states, greater than 40.

So E is the correct answer.  Reply With Quote

5. ## i wish to understand how can we take 2^50??

hmm.. b/n between? I didn't get it. h(n) = 2 x 4 x .....n
h(100) = 2 x 4 x ...100
h(100) + 1 = (2 x 4 x ...100 + 1) = 2 (1 x 2 x...50) +1

if we divide this any number below 50;
1 would be the remainder. So that the smallest prime factor would be greater than 50.

Ans (E)
Just a small correction.
It (red 2) will be 250

how can we take 2^50 as a common term?? in my opinion it was correctly used as 2 in the first place
because (2.4.6.......100) = 2(1.2.3.....50)
if u take 2^2(0.5 . 1 . 1.5 ....... 25)... hence 2^50 is incorrect..

Correct me if i am wrong,m a newbie to GMAT...hope my math is not that bad!   Reply With Quote

6. Hi,

(2 + 4 + 6 +....+100) = 2(1 +2 +3 +.... + 50)
But that is not the case for multiplication

(2*4*6*...100) is not equal to 2(1*2 *3...*50)

Instead it is (2*4*6*...100)/2 so it will equal to (1*4*6*...*100)

if you look carefully (2*4*6*...100) is actually [(2*1) * (2*2) * (2*3) * ....(2*50)]

So there are 50 terms of h(100) factors that contain with multiple of 2. And of course you can defactor this term to

[(2^50)*(1*2*3*4*5*6*.....50)] or you can rewrite it in the factorial form as h(100) = [(2^50)*(50!)]

From the question you just add this term by 1 :
Therefore h(100) +1 = [(2^50)*(50!)] + 1

The smallest prime factor will be greater than 50 as all the prime number less than 50 will not divisible to the whole term.

To prove this, Let p be any prime factor:

(h(100) +1)/p must give the result with integer. or we can rewrite it as follows:

[h(100)/p + 1/p] must be an integer, and
therefore
the result of [(2^50)*(50!)]/p + 1/p must be an integer and leave no remainder if p is the factor of the whole term.

Because any prime number less than 50 is certainly divisible by the first term [(2^50)*(50!)]
for example 2, 3, 5, 7, 37, 41 etc. are all factors of (50!) that will make this term become integer
and leave the last term (1/p) as a decimal eg. 1/37

[(2^50)*(50!)]/p + 1/p
Integer + 1/37 --> will not be an integer

that's why any number less than or equal to 50 can't be the
factor of h(100) + 1 and so it is the case for prime factor <50.

So the answer is E Greater than 40

I hope this can help..  Reply With Quote

7. Originally Posted by Md. Minuddin Just a small correction.
It (red 2) will be 250
That is correct.

2*4*6 = 2*2*2*2*3 = (2^3)*(1*2*3)  Reply With Quote

8. ## Re: A Couple of Hard Questions from a CAT Exam

The no. h(100) = (2^100)*(50!)+1
let this no. be p
Now, p^2-1 = (2^200)*(50!)^2+2*(2^100)*(50!)
This is obviously divisible by 24.
Therefore, p has to be a prime no. as this is the property of all prime numbers only.
So, h(100) has its smallest prime factor as itself which is obviously > 40  Reply With Quote

9. ## Re: A Couple of Hard Questions from a CAT Exam

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.

Cheers,
Brent  Reply With Quote