PUMaC 2016 · 数论（A 组） · 第 6 题

PUMaC 2016 — Number Theory (Division A) — Problem 6

解析

For convenience let x = 2016 and P ( x ) = x − 1. Let Φ( x ) = x + x + · · · + x + 1. Then P ( x ) = ( x − 1)Φ( x ) = 2015Φ( x ) = 5 · 13 · 31 · Φ( x ). Now suppose p is a prime divisor of Φ( x ). 239 We have p | Φ( x ) ⇒ p | P ( x ) ⇒ x ≡ 1 (mod p ). Since by Fermat’s Little Theorem we have p − 1 g x ≡ 1 (mod p ), we get that x ≡ 1 (mod p ) where g = gcd(239 , p − 1). Suppose g = 1. Then we get that x ≡ 1 (mod p ) which simultaneously implies p | 2015 (since x = 2016) and p | 239 (since Φ(1) ≡ 239 ≡ 0 (mod p)), a contradiction. Therefore g = 239, and so p ≡ 1 (mod 239). We note that 239 + 1 = 240 is not prime but 2 · 239 + 1 = 479 is the smallest prime that could 239 239 478 possibly divide Φ( x ). Checking, we have P ( x ) ≡ 2016 − 1 ≡ 100 − 1 ≡ 10 − 1 ≡ 1 − 1 ≡ 0 (mod 479). Therefore the four smallest prime divisors of P ( x ) are 5, 13, 31 and 479, whose sum is 528 . Problem written by Mel Shu. 2