Problem Solving

lukemacdougall wrote:Hey guys - would someone mind helping explain the solution for the below problem? Thanks in advance!

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

Important Concept: If k is a positive integer that's greater than 1, and if 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)
Factor to get: h(100) = 2[(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.

Answer = E

Cheers,
Brent

ygdrasil24 wrote:@Brent: Got your point. Can we not generalise it further to say.
For any K being divisor of N, K will not be divisor for N , N+1, N+2....N+(k-1).

Ex: say 105 is divisible by 5, so 106,107,108,019 will also be not divisible, so a period of (divisor-1). Pls confirm it.

Thanks

That's a great (and true) generalization. Nice work.

Cheers,
Brent