Largest 3-digit Prime Factor

Determine the largest 3-digit prime factor of the integer (20001000)\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 (20001000)\binom{2000}{1000} should be \geq1. 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

No vote yet
3 votes

  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.

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

[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"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

I found out a seemingly nice and simple solution to this question in a book: We know (20001000)=(2000!)(1000!)2.\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 (20001000)\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 22 times in the denominator and 33 times in the numerator. Any prime in the range 5000 5000 to 20003\large \frac{2000}{3} will do and 661661 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 - 6 years, 4 months ago

Log in to reply

You don't really need to consider 500500 to 20003\lfloor {\frac{2000}{3}}\rfloor .

Let pp be a prime between 11 and 10001000. 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 22 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 33 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 20003\lfloor \frac{2000}{3} \rfloor .

Note: The multiples have to exists in sequence, that is to say that pp cannot have a multiple of 11 & 33 but not have its multiple of 22. 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!2000!,of any number in the denominator from 11 to 10001000 has to be 22.

Aditya Parson - 6 years, 4 months ago

Log in to reply

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

Sreejato Bhattacharya - 6 years, 4 months ago

Log in to reply

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

Nishant Sharma - 6 years, 4 months ago

Log in to reply

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

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

Thanks!

Pranav Arora - 6 years, 4 months ago

Log in to reply

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

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

Log in to reply

@Pranav Arora Let α=[2000q] \alpha = [\frac{2000}{q}] and β=[1000q] \beta= [\frac{1000}{q}] where q q is any 3 3 digit positive integer. We look to find the maximum possible value of q q such that α2β=1 \alpha - 2\beta= 1 , so our answer will be the largest prime q \leq q (because the highest power of any prime greater than q q in (20001000) { 2000 \choose 1000 } will be zero since q q is the largest integer satisfying α2β=1 \alpha - 2\beta= 1 and for all larger integers α2β=0 \alpha - 2\beta= 0 ). Note that 100q999 100 \leq q \leq 999 , so 2α20 2 \leq \alpha \leq 20 and 1β10 1 \leq \beta \leq 10 . Note that the larger q q is, the smaller the values of α \alpha and β \beta are. Also note that when α=3 \alpha= 3 and β=1 \beta= 1 , α2β=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 q . Now we should see if such a q q exists that α=3 \alpha= 3 , β=1 \beta= 1. If it does, then the maximum possible value of q q will be the largest 3 digit integer satisfying the given condition. Note that the largest value of q q which satisfies [2000q]=3 [\frac{2000}{q}]= 3 is [20003]=666 [\frac{2000}{3}]= 666 . Also note that [1000[210003]]=1 [\frac{1000}{[\frac{2*1000}{3}]}] = 1 . So such a q q exists and its maximum value is 666 666 . If q>666 q>666 , i.e. q667 q \geq 667 then α2β=0 \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 - 6 years, 4 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 - 6 years, 4 months ago

Log in to reply

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

Thaddeus Abiy - 6 years, 4 months ago

Log in to reply

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

Nishant Sharma - 6 years, 4 months ago

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.

Vikram Waradpande - 6 years, 4 months ago

Log in to reply

@Vikram Waradpande oh the guidance boy

superman son - 6 years, 4 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 - 6 years, 1 month ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...