HMMT 二月 2017 · 团队赛 · 第 7 题

HMMT February 2017 — Team Round — Problem 7

[ 45 ] Let p be a prime. A complete residue class modulo p is a set containing at least one element equivalent to k (mod p ) for all k . (a) ( 20 ) Show that there exists an n such that the n th row of Pascal’s triangle forms a complete residue class modulo p . 2 (b) ( 25 ) Show that there exists an n ≤ p such that the n th row of Pascal’s triangle forms a complete residue class modulo p .

解析

[ 45 ] Let p be a prime. A complete residue class modulo p is a set containing at least one element equivalent to k (mod p ) for all k . (a) ( 20 ) Show that there exists an n such that the n th row of Pascal’s triangle forms a complete residue class modulo p . 2 (b) ( 25 ) Show that there exists an n ≤ p such that the n th row of Pascal’s triangle forms a complete residue class modulo p . Proposed by: Alexander Katz We use the following theorem of Lucas: Theorem. Given a prime p and nonnegative integers a, b written in base p as a = a a . . . a and n n − 1 0 p b = b b . . . b respectively, where 0 ≤ a , b ≤ p − 1 for 0 ≤ i ≤ n , we have n n − 1 0 i i p ( ) ( ) n ∏ a a i = (mod p ) . b b i i =0 2 Now, let n = ( p − 1) × p + ( p − 2) = p − 2. For k = pq + r with 0 ≤ q, r ≤ p − 1, applying Lucas’s theorem gives ( ) ( )( ) n p − 1 p − 2 ≡ (mod p ) . k q r Note that ( ) q ∏ p − 1 p − i q = ≡ ( − 1) (mod p ) , q i i =1 and ( ) r ∏ p − 2 p − 1 − i ( r + 1)! r r = ≡ ( − 1) = ( − 1) ( r + 1) (mod p ) . r i r ! i =1 ( ) n So for 2 ≤ i ≤ p we can take k = ( p + 1)( i − 1) and obtain ≡ i (mod p ), while for i = 1 we can k take k = 0. Thus this row satisfies the desired property.