Largest Divisor of n n that divides ( n r ) \binom{n}{r}

Find the largest divisor of 8778 8778 that divides ( 8778 1105 ) \dbinom{8778}{1105} .

Notation: ( M N ) = M ! N ! ( M N ) ! \dbinom MN = \dfrac {M!}{N! (M-N)!} denotes the binomial coefficient .


The answer is 8778.

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

Hermite's First Divisibility Property for Binomial Coefficient ( n r ) \binom{n}{r} states, for n , r 1 n,r \geq 1 ,

n g c d ( n , r ) ( n r ) \frac{n}{gcd(n,r)} | \binom{n}{r}

Here g c d ( 8778 , 1105 ) = 1 gcd(8778,1105)=1 , so 8778 ( 8778 1105 ) 8778| \binom{8778}{1105} . As the largest divisor of 8778 8778 is 8778 8778 itself, the answer is 8778 8778 .

This is my argument. But I believe there must be some better argument, even just by using Hermite's First Divisibility Property . I'm still working on that.

Abhishek Alva
Nov 30, 2016

the solution is very simple . the factors of 8778 are 2,3,7,11,19 .after substitution we see that the numerator has 8778 factorial which already contains 8778 . thus the largest divisor of 8778 that divides 8778 factorial is 8778.

Then 10 10 divides ( 10 2 ) \binom{10}{2} ?

Muhammad Rasel Parvej - 4 years, 6 months ago

Log in to reply

ya because there is a 10 factorial in the numerator

abhishek alva - 4 years, 6 months ago

Log in to reply

Nope. ( 10 2 ) = 45 \binom{10}{2}= 45 , not divisible by 10 10 .

Muhammad Rasel Parvej - 4 years, 6 months ago

Log in to reply

@Muhammad Rasel Parvej thanks to clear my doubt

abhishek alva - 4 years, 6 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...