PUMaC 2015 · 个人决赛（B 组） · 第 3 题

PUMaC 2015 — Individual Finals (Division B) — Problem 3

For an odd prime number p , let S denote the following sum taken modulo p : p − 1 2 ∑ 1 1 1 1 S ≡ + + . . . + ≡ (mod p ) 1 · 2 3 · 4 ( p − 2) · ( p − 1) (2 i − 1) · 2 i i =1 2 p Prove that p | 2 − 2 if and only if S ≡ 0 (mod p ). 1

解析

For an odd prime number p , let S denote the following sum taken modulo p : p − 1 2 ∑ 1 1 1 1 S ≡ + + . . . + ≡ (mod p ) . 1 · 2 3 · 4 ( p − 2) · ( p − 1) (2 i − 1) · 2 i i =1 1 2 p Prove that p | 2 − 2 if and only if S ≡ 0 (mod p ). Solution: Notice that the binomial coefficients satisfy the following basic properties: ( ) ( ) p p p − 1 = n n n − 1 ( ) p − 1 ( p − 1)( p − 2) . . . ( p − n + 1) ( − 1)( − 2) . . . ( − n + 1) n − 1 = ≡ = ( − 1) mod p n − 1 1 · 2 · 3 . . . ( n − 1) 1 · 2 . . . ( n − 1) Therefore we know that p − 1 ( ) ( ) ( ) p − 1 p − 1 p − 1 p − 1 2 p p p i − 1 i − 1 p − 1 p ∑ ∑ ∑ ∑ ∑ ( − 1) 1 ( − 1) ( − 1) 2 − 2 i i i S ≡ = = ( ) = · ( ) ≡ = mod p p − 1 p − 1 (2 i − 1) · 2 i i p p p p · i − 1 i − 1 i =1 i =1 i =1 i =1 i =1 p ( ) i where is always viewed as an integer rather than a division in mod p. p 2 p Therefore, p | 2 − 2 if and only if S = 0 mod p . Author: Xiaoyu Xu 2