Problem Solving

For every positive 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

Answer: e


I find functions quite difficult, so if you know of any good excercises or have any tips, I would be glad to hear it.

Thanks!
André

h(100) = 2*4*6*...*100
take all of the 2 common then
h(100) = (2*2*...50 times) * (1*2*3*...*50) = 2^50*(1*2*3*...*50).

Hence, all integers up to 50 are factors of h(100).

Now if h(100) + 1 is divided by any integers from 1 to 50 will have a remainder 1 as h(100) is divisible by all integers below 50.

So the least prime factor will be definitely > 50

IMO E

shovan85 wrote:h(100) = 2*4*6*...*100
take all of the 2 common then
h(100) = (2*2*...50 times) * (1*2*3*...*50) = 2^50*(1*2*3*...*50).

Hence, all integers up to 50 are factors of h(100).

Now if h(100) + 1 is divided by any integers from 1 to 50 will have a remainder 1 as h(100) is divisible by all integers below 50.

So the least prime factor will be definitely > 50

IMO E

I don't really understand why 2 or 3 cannot be the smallest prime factor. Ii it because you add 1 at the end? What affect does the 1 have? Is this equation the same as the smallest prime of 100! + 1 ?

Thanks for your answer

andre.heggli wrote:

shovan85 wrote:h(100) = 2*4*6*...*100
take all of the 2 common then
h(100) = (2*2*...50 times) * (1*2*3*...*50) = 2^50*(1*2*3*...*50).

Hence, all integers up to 50 are factors of h(100).

Now if h(100) + 1 is divided by any integers from 1 to 50 will have a remainder 1 as h(100) is divisible by all integers below 50.

So the least prime factor will be definitely > 50

IMO E

I don't really understand why 2 or 3 cannot be the smallest prime factor. Ii it because you add 1 at the end? What affect does the 1 have? Is this equation the same as the smallest prime of 100! + 1 ?

Thanks for your answer

What is the question asking.... smallest prime number as the factor of h(100)+1.
What I proved (from my prev post).... from 1 to 50 (including all primes) are not a factor of h(100) +1 (as the remainder will be 1).

Now tell me if you get remainder as 1 when u divide this h(100)+1 by 2 or 3 or 7 or 11 or .... 41 are they factors of h(100) +1 .

Obviously no as whatever prime below 50 u divide with h(100)+1 you will get a remainder and so those are not factors of h(100)+1.

The addition of 1 makes the primes below 50 not divisible.

yes it is kind of same to the logic 100! + 1. Here if you see we get 50! which says all the primes below 50 is a factor of h(100) n0t (h100) +1

shovan85 wrote:h(100) = 2*4*6*...*100
take all of the 2 common then
h(100) = (2*2*...50 times) * (1*2*3*...*50) = 2^50*(1*2*3*...*50).

Hence, all integers up to 50 are factors of h(100).

Now if h(100) + 1 is divided by any integers from 1 to 50 will have a remainder 1 as h(100) is divisible by all integers below 50.

So the least prime factor will be definitely > 50

IMO E

Luckily i got it right,
Even i have taken 2 common from all the terms but that was just one 2 not 2^50.

Thanks for making the point. Clear

andre.heggli wrote:For every positive 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

Answer: e


I find functions quite difficult, so if you know of any good excercises or have any tips, I would be glad to hear it.

Thanks!
André

Here is the rule that is being tested with this problem:

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.

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.