Largest 3-digit prime factor

What is the largest 3-digit prime factor of ( 2015 1007 ) \displaystyle \binom{2015}{1007} .

You may use this List of Primes as a reference.

Image Credit: Wikimedia Hersfold .


The answer is 661.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

note that ( 2015 1007 ) = 2015 ! 1007 ! 1008 ! \binom{2015}{1007} = \frac{2015!}{1007!1008!}

let p p is prime factor of ( 2015 1007 ) \binom{2015}{1007}

imagine V p ( n ! ) V_{p} \left ( n! \right ) is the largest value of k k such that p k . m = n ! p^{k} .m = n! with G C D ( p , m ) = 1 GCD(p,m)=1 and p , k , m , n N p,k,m,n \in \mathbb{N}

we know

V p ( 2015 ! ) = k = 1 2015 p k V_{p} \left ( 2015! \right ) = \sum_{k=1}^{\infty} \left \lfloor \frac{2015}{p^{k}} \right \rfloor V p ( 1008 ! ) = k = 1 1008 p k V_{p} \left ( 1008! \right ) = \sum_{k=1}^{\infty} \left \lfloor \frac{1008}{p^{k}} \right \rfloor V p ( 1007 ! ) = k = 1 1007 p k V_{p} \left ( 1007! \right ) = \sum_{k=1}^{\infty} \left \lfloor \frac{1007}{p^{k}} \right \rfloor
V p ( ( 2015 1007 ) ) = V p ( 2015 ! ) V p ( 1008 ! ) V p ( 1007 ! ) V_{p} \left ( \binom{2015}{1007} \right ) = V_{p} \left ( 2015! \right ) - V_{p} \left ( 1008! \right ) - V_{p} \left ( 1007! \right )

so we have V p ( ( 2015 1007 ) ) = k = 1 2015 p k k = 1 1008 p k k = 1 1007 p k V_{p} \left ( \binom{2015}{1007} \right ) = \sum_{k=1}^{\infty} \left \lfloor \frac{2015}{p^{k}} \right \rfloor - \sum_{k=1}^{\infty} \left \lfloor \frac{1008}{p^{k}} \right \rfloor - \sum_{k=1}^{\infty} \left \lfloor \frac{1007}{p^{k}} \right \rfloor

WLOG for p p maximum we need to simplify that sum with only take k = 1 k =1

then V p ( ( 2015 1007 ) ) = 2015 p 1008 p 1007 p V_{p} \left ( \binom{2015}{1007} \right ) = \left \lfloor \frac{2015}{p} \right \rfloor - \left \lfloor \frac{1008}{p} \right \rfloor - \left \lfloor \frac{1007}{p} \right \rfloor

\,\,\,\,\, the other way to say that when p p is maximum V p V_{p} is minimum.

WLOG let V p = 1 V_{p} = 1

So 2015 p 1008 p 1007 p = 1 \left \lfloor \frac{2015}{p} \right \rfloor - \left \lfloor \frac{1008}{p} \right \rfloor - \left \lfloor \frac{1007}{p} \right \rfloor = 1

Try all case posible but WLOG again for

2015 p = 3 \left \lfloor \frac{2015}{p} \right \rfloor = 3 then 2015 4 < p 2015 3 503 < p 671 \left \lfloor \frac{2015}{4} \right \rfloor < p \leq \left \lfloor \frac{2015}{3} \right \rfloor \rightarrow \, 503 < p \leq 671

1008 p = 1 \left \lfloor \frac{1008}{p} \right \rfloor = 1 then 1008 2 < p 1008 504 < p 1008 \left \lfloor \frac{1008}{2} \right \rfloor < p \leq 1008 \rightarrow \, 504< p \leq 1008

1007 p = 1 \left \lfloor \frac{1007}{p} \right \rfloor = 1 then 1007 2 < p 1007 503 < p 1007 \left \lfloor \frac{1007}{2} \right \rfloor < p \leq 1007 \rightarrow \, 503 < p \leq 1007

So interval p p is 505 p 671 505 \leq p \leq 671

p p is prime , then the Largest prime for p p is p m a x = 661 p_{max} = \boxed{661}

Digi Verse
Jul 1, 2015

When written out, the number would be: (2015x2014x...x1009)/(1007!). As the answer has to be prime, its multiples have to be the one to determine whether it is divisible or not. Starting at 999, you will notice that the denominator has a 999, and the numerator will have a 999x2, which will cancel out. Therefore, for a number to be a factor of the large number, there will have to be more of it above than below. That leads you to this formula: 3x<2015. This means that there has to be 3 multiples of the answer before 2015, so that there can be 2 in the numerator and 1 in the denominator. This leads to x<671.6666..., and the largest prime number smaller than this is 661.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...