PUMaC 2019 · 个人决赛（A 组） · 第 2 题

PUMaC 2019 — Individual Finals (Division A) — Problem 2

Prove that for every positive integer m , every prime p and every positive integer j ≤ p , ( ) ( ) m m − 1 p p m p divides − . pj j

解析

Prove that for every positive integer m , every prime p and every positive integer j ≤ p , ( ) ( ) m m − 1 p p m p divides − . pj j Solution : ( ) ( ) ( ) pj − 1 m m − 1 m ∏ p p p − i = = pj j i i =1 ( ) ( ) ( ) j − 1 m − 1 m − 1 m ∏ ∏ p p − i p − i = · , j i i i =1 i ∈ I Where I = { i ∈ N | 0 < i < pj, p - i } . The second term cancels because all of the terms in both ( ) m − 1 p numerator and denominator are not divisible by p . The first term is precisely . j There’s an even number of terms in the second product whenever j · ( p − 1) is even; then we j ( p − 1) m can pair up the ones which evaluate to ( − 1) (mod p ). In those cases, we are done, j ( p − 1) since ( − 1) = 1. When j is odd and p = 2, then the binomial coefficients are negatives of m m − 1 each other mod 2 , but we are still done because both expressions are divisible by 2 (we m − 1 2 can see this because the first term is the product of and an integer). j Proposed by Alec Leng. Solution by Zhuo Qun Song.