When Does 2027 Divide This Binomial Expression?
Find the smallest positive integer k for which n = 0 ∑ 1 0 1 3 ( n 2 n ) k n is divisible by the prime 2027.
The answer is 507.
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
As I was feeling too stupid to do it analytically, I threw the question at Sage which provided the answer in a matter of a few seconds.
The answer is 4 2 0 2 7 + 1 = 5 0 7 , I found it by checking the trivial cases 3 , 7 , 1 1 , so I have no proof of this fact, I was only lucky...
Given that: j = 0 ∑ n ( j 2 j ) ( n − j 2 n − 2 j ) = 4 n due to the Vandermonde convolution of central binomial coefficients, and: ∀ n ∈ [ 1 0 1 4 , 2 0 2 6 ] , ( n 2 n ) ≡ 0 ( m o d 2 0 2 7 ) , we have: ( j = 0 ∑ 1 0 1 3 ( j 2 j ) k j ) 2 ≡ j = 0 ∑ 2 0 2 6 ( 4 k ) j ( m o d 2 0 2 7 ) . If 4 k ≡ 1 ( m o d 2 0 2 7 ) the last sum is zero ( m o d 2 0 2 7 ) , otherwise it is one ( m o d 2 0 2 7 ) , since: j = 0 ∑ 2 0 2 6 ( 4 k ) j = 4 k − 1 ( 4 k ) 2 0 2 7 − 1 ≡ 4 k − 1 4 k − 1 ≡ 1 ( m o d 2 0 2 7 ) , due to a p ≡ a ( m o d p ) . This gives that in order to have the initial sum equal to zero, we must have 4 k ≡ 1 ( m o d 2 0 2 7 ) , id est k ≡ 5 0 7 ( m o d 2 0 2 7 ) .
Log in to reply
A slightly more direct approach which uses the ideas that you presented here, is to show that
( n 2 n ) ≡ ( − 4 ) n ( n 1 0 1 3 ) ( m o d 2 0 2 7 )
Hence,
n = 0 ∑ 1 0 1 3 ( n 2 n ) k n = n = 0 ∑ 1 0 1 3 ( n 1 0 1 3 ) ( − 4 k ) n = ( 1 − 4 k ) 1 0 1 3 ( m o d 2 0 2 7 )
Hence, we must have 1 − 4 k ≡ 0 ( m o d 2 0 2 7 ) .
Hint: Evaluate ( n 2 n ) ( m o d 2 0 2 7 ) , into a form such that you can manipulate the expression using the Binomial Theorem. Namely, ( n 2 n ) ≡ α n ( n β ) for some fixed α , β .
Hint: Using the Binomial Theorem, show that ∑ n = 0 1 0 1 3 ( n 2 n ) k n ≡ a b ( m o d 2 0 2 7 ) for some a and b .
What do these hints suggest about the values of β and b ?
What is a in terms of α ?
What does Emmanuel's solution suggest about the value of α ?
Hence show that 2 0 2 7 ∣ a , which you can use to determine the smallest value of k .
Another solution:
Recall that 1 − 4 x 1 = i = 0 ∑ ∞ ( i 2 i ) x i
How do we relate this to the expression in the problem?