Not Lucas' Theorem!

What is the remainder when n = 0 2014 n 4 ( 2014 n ) \large \displaystyle \sum_{n=0}^{2014} n^4 {2014 \choose n } is divided by 819 819 ?


The answer is 299.

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.

1 solution

Discussions for this problem are now closed

Jack D'Aurizio
Apr 21, 2014

We can first write n 4 n^4 as: n 4 = 24 ( n 4 ) + 36 ( n 3 ) + 14 ( n 2 ) + ( n 1 ) n^4 = 24\binom{n}{4}+36\binom{n}{3}+14\binom{n}{2}+\binom{n}{1} in order to exploit the identity: n = 0 2014 ( n k ) ( 2014 n ) = ( 2014 k ) 2 2014 k . \sum_{n=0}^{2014}\binom{n}{k}\binom{2014}{n} = \binom{2014}{k}\cdot 2^{2014-k}. Since 819 = 3 2 7 13 819 = 3^2\cdot 7\cdot 13 , we just have to compute the residue classes ( m o d 7 , 9 , 13 ) \pmod{7,9,13} of: 24 ( 2014 4 ) 2 2010 + 36 ( 2014 3 ) 2 2011 + 14 ( 2014 2 ) 2 2012 + 2014 2 2013 . 24\binom{2014}{4}2^{2010}+36\binom{2014}{3}2^{2011}+14\binom{2014}{2}2^{2012}+2014\cdot 2^{2013}. Since ϕ ( 13 ) = 2 ϕ ( 9 ) = 2 ϕ ( 6 ) \phi(13)=2\phi(9)=2\phi(6) , this is the same as calculating the residue classes ( m o d 7 , 9 , 13 ) \pmod{7,9,13} of: 24 ( 2014 4 ) 2 6 + 36 ( 2014 3 ) 2 7 + 14 ( 2014 2 ) 2 8 + 2014 2 9 , 24\binom{2014}{4}2^{6}+36\binom{2014}{3}2^{7}+14\binom{2014}{2}2^{8}+2014\cdot 2^{9}, or: ( 2014 2013 2012 2011 ) 2 6 + 6 ( 2014 2013 2012 ) 2 7 + 7 ( 2014 2013 ) 2 8 + 2014 2 9 . (2014\cdot 2013\cdot 2012\cdot 2011)\cdot 2^{6}+6(2014\cdot 2013\cdot 2012)\cdot 2^{7}+7\cdot(2014\cdot 2013)\cdot 2^{8}+2014\cdot 2^{9}. The last sum is just 2 ( m o d 9 ) , 5 ( m o d 7 ) , 0 ( m o d 13 ) 2\pmod{9},5\pmod{7},0\pmod{13} , hence the answer is 299 299 by the chinese theorem.

Brilliant

Mahdi Al-kawaz - 7 years, 1 month ago

Dude, you have like, the best solutions of anyone I've ever seen. :O

Finn Hulse - 7 years, 1 month ago

Haha ROFL

Joshua Ong - 7 years, 1 month ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...