Problem Solving

Hey guys,

I would just like to share this one:

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

I got it right, but I would like to see how you solve this one.
So, please no "IMO XYZ" .

btw. it was the third question ^^

Excellent explanation look at this post

https://www.manhattangmat.com/forums/for ... t1152.html

mowie wrote:Hey guys,

I would just like to share this one:

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

I got it right, but I would like to see how you solve this one.
So, please no "IMO XYZ" .

btw. it was the third question ^^

n = 2, 4, 6, 8, even

h(2) = 2

h(4) = 2*4 = 8

h(6) = 2*4*6 = 48

h(100) = 2*4*6...*100 = x (large EVEN number)

h(100)+1 = large ODD number

p = smallest prime factor of h(100)+1

p = ?

E) ?

Large odd number?

How about 300000000000000003 ?
one clever edit:
how about 20000000..........................000000000000000000000000001?
It is sure that there are large numbers which are divisible by 3 or 7 with an 1 at the end. There could a lot of other prime factors like 17, 23...

I argued like that

2 4 6 8 10......92 94 96 98 100

2
2*2
2*3
2*2*2
2* 5
...
2 * 46 = 2 * 2 * 23
2 * 47 = 2 * 47 (PRIME!)
2 * 49 = 2 * 7 * 7
2 * 50 = 2 * 2 * 5 * 5

or like written in the linked post

the factor is equal to 2^50 * (1*2*3*4*5*6*...*47*48*49*50).

So the facot NEED to include every prime number smaller than 50 AT LEAST ONCE.
So this factor is divisible by all off these primefactors.
Adding 1 to it changes this problem.
1 is NOT divisible by any primefactor. The sum is only divisible by a prime factor if both are divisible by the prime factor or MAYBE if both are not.

So, we know that there is no prime factor under 47 that could be a divisor.

=> E

I just hoped that there is any kind of "easy" solution. Maybe you could give me some further hints. The linked explanation is based on the same thoughts.

mowie wrote:Hey guys,

I would just like to share this one:

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

I got it right, but I would like to see how you solve this one.
So, please no "IMO XYZ" .

btw. it was the third question ^^

take this an example and work

h(10) = 2 * 4 * 6 * 8 * 10
h(10) = 2^5 ( 1 * 2 * 3 * 4 * 5)
All integers upto 5 are factors of h(10)

Therefore h(10) + 1 cannot have any prime factors below 5,since dividing this value by any of these prime numbers will yield a remainder of 1.


apply this to h(100)
Therefore, h(100) + 1 cannot have any prime factors 50 or below, since dividing this value by any of these prime numbers will yield a remainder of 1.

Since the smallest prime number that can be a factor of h(100) + 1 has to be greater than 50

E wins !!

The solution on MGMAT states "No consecutive integers share the same prime factors".

In fact, can I also say "No consecutive integers share the same factor, irregardless if its prime or non prime, except 1" ?

Can someone confirm?

Consider 12 and 13:

***12***| ***13**
2|Divisible|Not divisible
3|Divisible|Not divisible
4|Divisible|Not divisible
6|Divisible|Not divisible
12|Divisible|Not divisible
Note: 12 is divisible by 2, hence 13 is not divisible by 2.
Apply the same logic:

**H(100)*|***H(100)+1
2|Divisible|Not divisible
3|Divisible|Not divisible
4|Divisible|Not divisible
....
50|Divisible|Not divisible

Though this does not give us the exact value, it indicates that the first factot must be greater than 50.

Jijil Ramakrishnan
The Princeton Review - Bangalore
+91-80 41211705 /706

mowie wrote:Hey guys,

I would just like to share this one:

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

I got it right, but I would like to see how you solve this one.
So, please no "IMO XYZ" .

btw. it was the third question ^^

valleeny wrote:The solution on MGMAT states "No consecutive integers share the same prime factors".

In fact, can I also say "No consecutive integers share the same factor, irregardless if its prime or non prime, except 1" ?

Can someone confirm?

Yes. Consecutive integers are co-primes: they share no factors other than 1. Here is my explanation:

If x is a positive integer, the only factor common both to x and to x+1 is 1. They share no other factors.

Let's examine why:

If x is a multiple of 2, the next largest multiple of 2 is x+2.
If x is a multiple of 3, the next largest multiple of 3 is x+3.

Using this logic, if we go from x to x+1, we get only to the next largest multiple of 1. So 1 is the only factor common both to x and to x+1. They share no other factors. (As noted above, integers that share no factors other than 1 are called coprimes.)

Thus, in the problem above, we know that 1 is the only factor common both to h(100) and to h(100) + 1. They share no other factors.

h(100) = 2 * 4 * 6 *....* 94 * 96 * 98 * 100

Factoring 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 is 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.

Great answer, GMATGuru! It took me forever to understand the theory behind this one, but the definition of coprimes is really all you need to know! (And a little advanced distribution finesse...)

Wow! Awesome way to solve Mitch! Thanks!