Competition problem — Number theory

Library / /560 of 860

Number theory Difficulty 5.3 AIME, harder Find the answer

At a recent math contest, Evan was asked to find $2^{2016}(\bmod 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. - However, Evan noted that $e-\frac{1}{2}(p-1)=21$ , and then realized the answer was $-2^{21}(\bmod p)$ . What was the prime $p$ ?

Your answer

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Answer is $p=211$ . Let $p=2d+1,50<d<250$ . The information in the problem boils down to $2016=d+21 \quad(\bmod 2d)$ . From this we can at least read off $d \mid 1995$ . Now factor $1995=3 \cdot 5 \cdot 7 \cdot 19$ . The values of $d$ in this interval are $57,95,105,133$ . The prime values of $2d+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.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.