返回题库

PUMaC 2023 · 个人决赛（A 组） · 第 1 题

PUMaC 2023 — Individual Finals (Division A) — Problem 1

专题
Discrete Math / 离散数学
难度
L3
来源
PUMaC

题目详情

  1. Let p > 3 be a prime and k ≥ 0 an integer. Find the multiplicity of X − 1 in the factorization of k k 3 p − 1 3 p − 2 f ( X ) = X + X + · · · + X + 1 r modulo p ; in other words, find the unique non-negative integer r such that ( X − 1) divides r +1 f ( X ) modulo p , but ( X − 1) does not divide f ( X ) modulo p .
解析
  1. Let p > 3 be a prime and k ≥ 0 an integer. Find the multiplicity of X − 1 in the factorization of k k 3 p − 1 3 p − 2 f ( X ) = X + X + · · · + X + 1 r modulo p ; in other words, find the unique non-negative integer r such that ( X − 1) divides r +1 f ( X ) modulo p , but ( X − 1) does not divide f ( X ) modulo p . Proposed by Michael Cheng and Steven Wang Solution: First note k 3 p X − 1 f ( X ) = . X − 1 The key trick is to make the substitution X = Y + 1, so we are instead looking for the multiplicity of Y in k 3 p ( Y + 1) − 1 f ( Y ) = . Y Now k 3 p k X k 3 p 3 p ℓ ( Y + 1) = Y , ℓ ℓ =0 k 3 p k and we claim the coefficient is divisible by p unless p | ℓ . ℓ We use the notation k k +1 v ( n ) = { k ∈ Z : p | n and p ∤ n } . p ≥ 0 It is well-known that ∞ X n v ( n !) = . p r p r =0 Therefore ∞ k k k k X 3 p (3 p )! 3 p ℓ 3 p − ℓ v = v = − − . p p k r r r ℓ ℓ !(3 p − ℓ )! p p p r =0 | {z } S r We have three cases depending on r : • r > k : then all three floor functions are 0 (here we used the assumption that p > 3), so S = 0. r r k r • r ≤ k : then p | 3 p , so S ≥ 0. More careful analysis shows that S = 0 iff p | ℓ . r r k 3 p k Therefore, v = 0 iff p | ℓ . Thus, modulo p , we have p ℓ k 3 p ( Y + 1) − 1 f ( Y ) = Y   k 3 p k X 1 3 p ℓ   = Y − 1 Y ℓ ℓ =0 k k k k k 1 3 p 3 p 3 p 2 p p ≡ Y + AY + AY A = = k k Y 2 p p k k k 3 p − 1 2 p − 1 p − 1 = Y + AY + AY , 1 k and p ∤ A , so the answer is p − 1 . Remark. The X = Y + 1 trick can be used to prove the cyclotomic polynomial Φ k ( X ) = p p − 1 X + · · · + X + 1 is irreducible over Z . In fact, one can check that Φ k ( Y + 1) satisfies p the Eisenstein criterion. 2