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 ?

#MathProblem

Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 2	paragraph 1 paragraph 2
`[example link](https://brilliant.org)`	example link
`> This is a quote`	This is a quote
# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"	# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"

Math	Appears as
Remember to wrap math in `$` ... `$` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

Comments

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 - 8 years ago

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 - 8 years ago

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 - 8 years ago

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 - 8 years ago

@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 - 8 years ago

@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 - 8 years ago

@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 - 8 years ago

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 - 8 years ago

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 - 8 years ago

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

Thaddeus Abiy - 8 years ago

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

Nishant Sharma - 8 years ago

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 - 8 years ago

@Vikram Waradpande – oh the guidance boy

superman son - 8 years ago

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

Michael Tang - 7 years, 9 months ago

Math	Appears as
Remember to wrap math in `\(` ... `\)` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$