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 elementequivalent 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 completeresidue class modulo p .
(b) ( 25 ) Show that there exists an n ≤ p such that the n th row of Pascal’s triangle forms a complete 2
residue class modulo p .
解析
英文解析
- [ 45 ] Let p be a prime. A complete residue class modulo p is a set containing at least one elementequivalent 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 completeresidue class modulo p .
(b) ( 25 ) Show that there exists an n ≤ p such that the n th row of Pascal’s triangle forms a complete 2
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 andn n − 1 0
b = b b . . . b respectively, where 0 ≤ a , b ≤ p − 1 for 0 ≤ i ≤ n , we havepn n − 1 0 i i
( ) ( )pn
∏
a ai = (mod p ) .
b bii =0
Now, let n = ( p − 1) × p + ( p − 2) = p − 2. For k = pq + r with 0 ≤ q, r ≤ p − 1, applying Lucas’s 2
theorem gives
( ) ( )( )
n p − 1 p − 2
≡ (mod p ) .
k q r
Note that
( )
∏qp − 1 p − i = ≡ ( − 1) (mod p ) ,qq ii =1
( )andr
∏
p − 2 p − 1 − i ( r + 1)!
r r = ≡ ( − 1) = ( − 1) ( r + 1) (mod p ) .
r i r !
i =1
( )
So for 2 ≤ i ≤ p we can take k = ( p + 1)( i − 1) and obtain ≡ i (mod p ), while for i = 1 we cannktake k = 0. Thus this row satisfies the desired property.