For every positive even integer n, the function h(n)

[Guest]

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

Can someone walk me through this one?

[dbernst]

Guest, this is definitely a difficult number properties question. Let's first consider the prime factors of h(100). According to the given function,
h(100) = 2*4*6*8*...*100

By factoring a 2 from each term of our function, h(100) can be rewritten as
2^50*(1*2*3*...*50).

Thus, all integers up to 50 - including all prime numbers up to 50 - are factors of 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, The correct answer is E.

Hope that helps
-Dan

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

[guest612]

I got stuck on this question as well. can you please tell me how 2^50 can be factored? I'm not sure I'm following the math.

Thank you!

[RonPurewal]

I got stuck on this question as well. can you please tell me how 2^50 can be factored? I'm not sure I'm following the math.

Thank you!

the number h(100) is 2 x 4 x 6 x 8 x ... x 100
which is (2 x 1) x (2 x 2) x (2 x 3) x ... x (2 x 50)

if you pull out all those 2's and send them all to the front of the expression - something you're allowed to do, because you can multiply a group of numbers in any order you please - you get 2^50 in front, because there are fifty 2's.

[guest612]

thanks, ron!

[rfernandez]

Nice job.

[Halo3]

Ron,

I'm missing something in the following step

"Thus, all integers up to 50 - including all prime numbers up to 50 - are factors of 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. "

So because h(100) can be factored by every integer up to 50 means that h(100)+1 can't have a prime factor below 50? Not quite getting this one... Please flush out.


Thanks-

[John]

Halo3,

h(100)=2^50 * 50! = 2^50 * (1*2*3*...*50)

Here h(100) is divisible by any numer between 2 and 50. Right?
So h(100)+1 can't be divisile by any number between 2 and 50. h(100)+1 will always give a reminder of 1 when u divide the no by any no between 1 to 50.

So h(100)+1 doesnot have any factor between 2 and 50. Hence h(100)+1 doesnot have any prime factor between 2 and 50.

Cheers,

[RonPurewal]

Ron,

I'm missing something in the following step

"Thus, all integers up to 50 - including all prime numbers up to 50 - are factors of 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. "

So because h(100) can be factored by every integer up to 50 means that h(100)+1 can't have a prime factor below 50? Not quite getting this one... Please flush out.


Thanks-

i'll assume you mean "flesh out", unless you want this whole thread destroyed (which you presumably don't).
heh heh

the idea is this: if a number is divisible by some prime p, then the next multiple of p will be p units bigger. for instance, 75 is divisible by 5. this means that the next greatest multiple of 5 is 80, which is 5 units away.
hopefully, this fact is clear. once you realize this, it follows that consecutive integers can't share ANY primes, because they're only 1 unit apart (too close together to work for any common factor except 1, which is trivially a factor of any integer at all, anywhere).
that's the basis for saying h(100) + 1 has no prime factors below 50. if it did, then you'd have two multiples of the same prime 1 unit apart, and that's impossible.

[Halo3]

Makes sense now - appreciate the help!

[rfernandez]

We're glad it helped.

[supratims]

nice explanation. Thanks !

[Ben Ku]

You're welcome!

[hugolinares]

Great explanation Ron, Thanks!

[anoo.anand]

Ron,

I'm missing something in the following step

"Thus, all integers up to 50 - including all prime numbers up to 50 - are factors of 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. "

So because h(100) can be factored by every integer up to 50 means that h(100)+1 can't have a prime factor below 50? Not quite getting this one... Please flush out.


Thanks-

i'll assume you mean "flesh out", unless you want this whole thread destroyed (which you presumably don't).
heh heh

the idea is this: if a number is divisible by some prime p, then the next multiple of p will be p units bigger. for instance, 75 is divisible by 5. this means that the next greatest multiple of 5 is 80, which is 5 units away.
hopefully, this fact is clear. once you realize this, it follows that consecutive integers can't share ANY primes, because they're only 1 unit apart (too close together to work for any common factor except 1, which is trivially a factor of any integer at all, anywhere).
that's the basis for saying h(100) + 1 has no prime factors below 50. if it did, then you'd have two multiples of the same prime 1 unit apart, and that's impossible.

so does this mean...that the next factor is greater than 50 ?

still not getting this :(