Waste less time on Facebook — follow Brilliant.
×

Largest 3-digit Prime Factor

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 ?

Note by Nishant Sharma
4 years, 2 months ago

No vote yet
3 votes

Comments

Sort by:

Top Newest

I 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? Vikram Waradpande · 4 years, 2 months ago

Log in to reply

@Vikram Waradpande 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\). Aditya Parson · 4 years, 2 months ago

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 \). Sreejato Bhattacharya · 4 years, 2 months ago

Log in to reply

@Sreejato Bhattacharya Thanks for a detailed solution. I want to know what is the significance of the step q=[\(\frac{2000}{3}\)] + 1=667 and thereafter ? Nishant Sharma · 4 years, 2 months ago

Log in to reply

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

Since \( \binom{2000}{1000}=\frac{2000!}{1000!^2} \), the highest power of \( p\) that divides \(\binom{2000}{1000} \) is.....

Thanks! Pranav Arora · 4 years, 2 months ago

Log in to reply

@Pranav Arora 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. Sreejato Bhattacharya · 4 years, 2 months ago

Log in to reply

@Sreejato Bhattacharya Many thanks Sreejato, got to learn something new. :)

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. Pranav Arora · 4 years, 2 months ago

Log in to reply

@Pranav Arora Let \( \alpha = [\frac{2000}{q}] \) and \( \beta= [\frac{1000}{q}] \) where \( q \) is any \( 3 \) digit positive integer. We look to find the maximum possible value of \( q \) such that \( \alpha - 2\beta= 1 \), so our answer will be the largest prime \( \leq q \) (because the highest power of any prime greater than \( q \) in \( { 2000 \choose 1000 } \) will be zero since \( q \) is the largest integer satisfying \( \alpha - 2\beta= 1 \) and for all larger integers \( \alpha - 2\beta= 0 \) ). Note that \( 100 \leq q \leq 999 \), so \( 2 \leq \alpha \leq 20 \) and \( 1 \leq \beta \leq 10 \). Note that the larger \( q \) is, the smaller the values of \( \alpha \) and \( \beta \) are. Also note that when \( \alpha= 3 \) and \( \beta= 1 \), \( \alpha - 2\beta= 1 \). This is the minimum possible value of \( (\alpha, \beta) \) which satisfies the conditions. As mentioned previously, the smaller the values of \( \alpha \) and \( \beta \) are, the larger will be the possible value of \( q \). Now we should see if such a \( q \) exists that \( \alpha= 3 \), \( \beta= 1\). If it does, then the maximum possible value of \( q \) will be the largest 3 digit integer satisfying the given condition. Note that the largest value of \( q \) which satisfies \( [\frac{2000}{q}]= 3\) is \( [\frac{2000}{3}]= 666 \). Also note that \( [\frac{1000}{[\frac{2*1000}{3}]}] = 1 \). So such a \( q \) exists and its maximum value is \( 666 \). If \( q>666 \), i.e. \( q \geq 667 \) then \( \alpha - 2\beta= 0 \). This result was directly stated in the original answer. These steps should not have been omitted in the original answer, very sorry for that. Sreejato Bhattacharya · 4 years, 2 months ago

Log in to reply

@Sreejato Bhattacharya Ok. Got that. And once again thank you for your simple explanations. I know it would have taken you pains to write so much( it would have taken me pains to do so much). But TY again........ Nishant Sharma · 4 years, 2 months ago

Log in to reply

Awesome problem and solution!This would have made a hell of a brilliant problem! Thaddeus Abiy · 4 years, 2 months ago

Log in to reply

@Thaddeus Abiy Well, I could not understand your last exclamation "hell of a brilliant problem". Nishant Sharma · 4 years, 2 months ago

Log in to reply

@Nishant Sharma 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. Vikram Waradpande · 4 years, 2 months ago

Log in to reply

@Vikram Waradpande oh the guidance boy Superman Son · 4 years, 2 months ago

Log in to reply

This problem is very similar to 1983 AIME, Problem #8. https://www.artofproblemsolving.com/Wiki/index.php/1983AIMEProblems/Problem_8 Michael Tang · 3 years, 11 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...