Let p = 2 1 6 + 1 be an odd prime. Define H n = ∑ x = 1 n n 1 . Find the remainder when
( p − 1 ) ! n = 1 ∑ p − 1 H n ⋅ 4 n ⋅ ⎝ ⎛ 2 p − 2 n p − n ⎠ ⎞
is divided by p
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.
Problem Loading...
Note Loading...
Set Loading...
We will take H n = 1 − 1 + 2 − 1 + ⋯ + n − 1 to be the sum of the multiplicative inverses of 1 , 2 , … , n in Z p . The value of the remainder computed this way will be equal to the remainder computed with non-integer values of H n because no multiple of p ever appears in the denominator of any term and ( p − 1 ) ! clears all the denominators that arise from H n .
Let s denote the value of the sum in question. To compute the remainder of s ÷ p , we can ignore the terms corresponding to n = 1 , 2 , … , 2 1 ( p − 1 ) since, for these terms, ( p − n 2 p − 2 n ) ≡ ( p − n ) ! ( 2 p − 2 n ) ( 2 p − 2 n − 1 ) ⋯ p ⋯ ( p − n + 1 ) ≡ 0 ( m o d p ) . A convenient way to sum the terms corresponding to n = 2 1 ( p + 1 ) , … , p − 1 is to reverse the convolution of H n ⋅ 4 n and ( n 2 n ) . Put m = p − n . The terms corresponding to n = 1 , … , 2 1 ( p − 1 ) are the terms we can ignore, and they are exactly those terms corresponding to m = 2 1 ( p + 1 ) , … , p − 1 . Omitting these terms shows s ≡ ( p − 1 ) ! m = 1 ∑ 2 1 ( p − 1 ) H p − m ⋅ 4 p − m ⋅ ( m 2 m ) ( m o d p ) . By Wilson's theorem, ( p − 1 ) ! ≡ − 1 ( m o d p ) , and by Fermat's little theorem, 4 p − m ≡ 4 ⋅ 4 − m ( m o d p ) , so we have s ≡ − 4 m = 1 ∑ 2 1 ( p − 1 ) H p − m ⋅ 4 − m ⋅ ( m 2 m ) ( m o d p ) . ( 1 )
By Wolstenholme's theorem, H p − 1 ≡ 0 ( m o d p ) , and for 1 ≤ m ≤ p − 1 , H p − m − 1 ≡ H p − m − ( p − m ) − 1 ( m o d p ) . Also, ( 1 2 ) ≡ 2 ( m o d p ) , and one can show that ( m + 1 2 m + 2 ) ≡ ( 2 m + 2 ) ( 2 m + 1 ) ( m + 1 ) − 2 ( m 2 m ) ( m o d p ) . Using the previous four congruences, we can compute H p − m and ( m 2 m ) for each term on the right side of ( 1 ) recursively. To find multiplicative inverses, we can apply Fermat's little theorem again, which states a − 1 ≡ a p − 2 ( m o d p ) , a = 1 , 2 , … , p − 1 . The script below computes the summands one by one and takes the residues of the partial sums. Using this script, we obtain the result s ≡ − 1 m = 1 ∑ 2 1 ( p − 1 ) H p − m 4 − m ( m 2 m ) ≡ 3 2 7 6 1 ( m o d p ) .