Determine the largest 3-digit prime factor of the integer \(\binom{2000}{1000}\).

I wrote it as (2000)!/(1000)!*(1000)! and then started finding powers of 3 digit prime factors of (2000)! and (1000)! keeping in mind that the resultant power of the prime factor in \(\binom{2000}{1000}\) should be \(\geq\)1. Doing this and a bit manipulation, I found that the largest factor should be in the range (600,700) and finally got 659 as the result. Is this correct ?

I know this method is not a standard one. Can anyone give me a standard approach to this problem ?

No vote yet

3 votes

×

Problem Loading...

Note Loading...

Set Loading...

## Comments

Sort by:

TopNewestI found out a seemingly nice and simple solution to this question in a book: We know \(\dbinom{2000}{1000} = \large \frac{(2000!)}{(1000!)^2}.\) We should now look at a prime factor which occurs more often in numerator than in the denominator so that it survives \(\dbinom{2000}{1000}\) ; since the denominator is a square, primes always occur to even power in the denominator. So we should look for a prime which occurs \(2\) times in the denominator and \(3\) times in the numerator. Any prime in the range \( 5000\) to \(\large \frac{2000}{3}\) will do and \(661\) is the largest prime in that range.

However, I fail to understand how they took out the range of the prime number. Can someone please explain?

Log in to reply

You don't really need to consider \(500\) to \(\lfloor {\frac{2000}{3}}\rfloor \).

Let \(p\) be a prime between \(1\) and \(1000\). Thus, we know that they(the primes) will occur in pairs in the denominator.

Now let us consider that the largest prime we look for has only two multiples in the numerator, that means we can cancel out the primes altogether. Since, once we will cancel out one of the primes in the numerator and denominator, we will only have one prime left in the denominator and it's multiple of \(2\) in the numerator. Here forth, again after cancelling out, we see that we have altogether lost the prime number from the expression. So we next check when the prime has \(3\) multiples of itself in the numerator.After cancellation, we will eventually be left with the prime number in the numerator. We won't check for further cases since it will yield lower primes. So you basically need to check for primes which are less than \(\lfloor \frac{2000}{3} \rfloor \).

Note: The multiples have to exists in sequence, that is to say that \(p\) cannot have a multiple of \(1\) & \(3\) but not have its multiple of \(2\). Although , it is apparent and seemingly obvious, I just clarified it. You, can also easily state that the minimum number of multiples contained in the numerator which is \(2000!\),of any number in the denominator from \(1\) to \(1000\) has to be \(2\).

Log in to reply

We know that if \(p \) is a prime and \( n \) is a non negative integer, the highest power of \( p \) that divides \( n! \) is \( [\frac{n}{p}] + [\frac{n}{p}^2] + [\frac{n}{p^3}] + ... \) [here \( [x] \) is defined as the smallest integer less than or equal to \( x \) ] (note that if \( k \) is the largest integer such that \(p^k > n \), then the terms after \( [\frac{n}{p^k}] \) will be \( 0 \) and so the calculation ends at \( [\frac{n}{p^k}] \)). Now let \( p \) be any \( 3 \) digit prime. Then we have \( p^2 > 2000 > 1000 \) [note that \( p \geq 100 \) which implies \( p^2 \geq 10000 > 2000 \)]. Hence highest power of \( p \) which divides \( 2000! \) is \( [\frac{2000}{p}] \) and the highest power of \( p \) which divides \( 1000! \) is \( [\frac{1000}{p}] \). Since \( {2000 \choose 1000} = \frac{2000!}{1000!^2}\), the highest power of \( p \) that divides \( {2000 \choose 1000} \) is \( [\frac{2000}{p}] - 2[\frac{1000}{p}] \). The largest \( 3 \) digit prime factor of the given number will be the largest possible prime value for \( p \) such that \( [\frac{2000}{p}] - 2[\frac{1000}{p}] > 0 \). Now let \( q= [\frac{2000}{3}] + 1= 667 \). Note that \( [\frac{2000}{q}] - 2[\frac{1000}{q}] = 2-2*1= 0\). Thus for \( p \) to satisfy the condition, \( p \) must be less than \( 667 \). So our answer is the largest prime \( <667 \), which is \( 661 \).

Log in to reply

Thanks for a detailed solution. I want to know what is the significance of the step q=[\(\frac{2000}{3}\)] + 1=667 and thereafter ?

Log in to reply

Nice answer Sreejato but can you explain the following and the subsequent steps that follow:

Thanks!

Log in to reply

Let \( \alpha \) be the highest power of \( p \) that divides \( 2000! \) and \( \beta \) be the highest power of \( p \) that divides \( 1000! \). So \( 2000!= m*p^\alpha \) [where \( m \) is an integer] and \( 1000!= n* p^\beta \) [where \( n \) is an integer]. Note that both \( m \) and \( n \) are co-prime to \( p \), since if they weren't co-prime to \( p \), \( p \) being prime \( p \) had to divide \( m \) and \( n \), so the highest power of \( p \) dividing \( 2000! \) and \( 1000! \) would be greater than \( \alpha \) and \( \beta \) respectively, a contradiction. Now note that \( \frac{2000!}{1000!^2} = \frac{m.p^\alpha }{(n.p^\beta)^2 } = \frac{m}{n^2} * p^{ \alpha - 2 \beta} \). We know that this is an integer since \( {2000 \choose 1000} \) has to be an integer. But as proved previously, \( gcd(m, p) = gcd(n, p)=1 \), thus \( gcd(\frac{m}{n^2}, p)= 1 \). So the highest power of \( p \) which divides \( {2000 \choose 1000} \) is \( \alpha - 2\beta \). But as proved in the original comment, \( \alpha = [\frac{2000}{p}] \) and \( \beta = [\frac{1000}{p}] \). Hence highest power of \( p \) that divides \( {2000 \choose 1000} \) is \( [\frac{2000}{p}] - 2[\frac{1000}{p}] \). Very sorry for the vagueness in the original comment.

Log in to reply

I still have one more doubt where you take q=667, I mean why and how did you bring this here? Sorry if this is a dumb question.

Log in to reply

Log in to reply

Log in to reply

Awesome problem and solution!This would have made a hell of a brilliant problem!

Log in to reply

Well, I could not understand your last exclamation "hell of a brilliant problem".

Log in to reply

Can I have some means to communicate with you? I really need some guidance and I think you'll be of great help to me.

Log in to reply

Log in to reply

This problem is very similar to 1983 AIME, Problem #8. https://www.artofproblemsolving.com/Wiki/index.php/1983

AIMEProblems/Problem_8Log in to reply