HMMT 二月 2017 · 冲刺赛 · 第 24 题

HMMT February 2017 — Guts Round — Problem 24

[ 12 ] At a recent math contest, Evan was asked to find 2 (mod p ) for a given prime number p with 100 < p < 500. Evan has forgotten what the prime p was, but still remembers how he solved it: • Evan first tried taking 2016 modulo p − 1, but got a value e larger than 100. 1 21 • However, Evan noted that e − ( p − 1) = 21, and then realized the answer was − 2 (mod p ). 2 What was the prime p ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . February 2017, February 18, 2017 — GUTS ROUND Organization Team Team ID# √ 3 3

解析

[ 12 ] At a recent math contest, Evan was asked to find 2 (mod p ) for a given prime number p with 100 < p < 500. Evan has forgotten what the prime p was, but still remembers how he solved it: • Evan first tried taking 2016 modulo p − 1, but got a value e larger than 100. 1 21 • However, Evan noted that e − ( p − 1) = 21, and then realized the answer was − 2 (mod p ). 2 What was the prime p ? Proposed by: Evan Chen Answer: 211 Answer is p = 211. Let p = 2 d + 1, 50 < d < 250. The information in the problem boils down to 2016 = d + 21 (mod 2 d ) . From this we can at least read off d | 1995. Now factor 1995 = 3 · 5 · 7 · 19. The values of d in this interval are 57, 95, 105, 133. The prime values of 2 d + 1 are then 191 and 211. Of these, we take 211 since (2 / 191) = +1 while (2 / 211) = − 1. Also, this is (almost) a true story: the contest in question was the PUMaC 2016 Live Round. √ 3 3