PUMaC 2015 · 数论（A 组） · 第 5 题
PUMaC 2015 — Number Theory (Division A) — Problem 5
题目详情
- [ 5 ] Given that there are 24 primes between 3 and 100, inclusive, what is the number of ordered pairs ( p, a ) with p prime, 3 ≤ p < 100, and 1 ≤ a < p such that the sum 2 3 ( p − 2)! a + a + a + · · · + a is not divisible by p ?
解析
- [ 5 ] Given that there are 24 primes between 3 and 100, inclusive, what is the number of ordered pairs ( p, a ) with p prime, 3 ≤ p < 100, and 1 ≤ a < p such that the sum 2 3 ( p − 2)! a + a + a + · · · + a 1 is not divisible by p ? Solution: If a = 1, then the sum just becomes ( p − 2)!, which is never divisible by p . So since there are 24 odd primes between 2 and 100, there are 24 solutions of the form ( p, 1). Next, suppose a 6 = 1. The sum can then be written as ( p − 2)! a − 1 a 2 ( p − 2)! ( p − 2)! a + a + · · · + a = a = · ( a − 1) . a − 1 a − 1 Since 1 < a < p , the term a/ ( a − 1) does not contribute to whether the sum is divisible by p . ( p − 2)! So it suffices to consider the term a − 1. Now look at the following cases. (a) If p = 3, then the sum is just a which isn’t divisible by p . So (3 , 2) is a valid solution. (b) If p = 5, then the sum is just a a 6 2 · ( a − 1) ≡ · ( a − 1) ≡ a ( a + 1) (mod p ) a − 1 a − 1 by Fermat’s Little Theorem. Plugging in a = 2 , 3 , 4 shows that (5 , 2) and (5 , 3) are the only solutions here. (c) If p > 5, then 2 6 = ( p − 1) / 2. Moreover, we also have 2 | ( p − 2)! and ( p − 1) / 2 | ( p − 2)! / 2 since 1 < 2 , ( p − 1) / 2 < p − 2. Thus ( p − 1) | ( p − 2)!, so by Fermat’s Little Theorem ( p − 2)! a − 1 ≡ 0 (mod p ). Thus the sum is always divisible by p in this case, and there are no solutions here. Thus there is a total of 27 solutions. Author: Steven Kwon