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
6 years, 4 months ago

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.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

• bulleted
• list

1. numbered
2. list

1. numbered
2. 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

> 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"
MathAppears 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}$

Sort by:

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?

- 6 years, 4 months 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$.

- 6 years, 4 months ago

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$.

- 6 years, 4 months 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 ?

- 6 years, 4 months 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!

- 6 years, 4 months 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.

- 6 years, 4 months ago

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.

- 6 years, 4 months ago

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.

- 6 years, 4 months ago

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........

- 6 years, 4 months ago

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

- 6 years, 4 months ago

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

- 6 years, 4 months 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.

- 6 years, 4 months ago

oh the guidance boy

- 6 years, 4 months ago

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

- 6 years, 1 month ago