Library / /42 of 68

, 2017

Number theory Difficulty 5.5 AIME, harder Prove it United States

Problem:
At a recent math contest, Evan was asked to find $2^{2016} \pmod{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} \pmod{p}$ .
What was the prime $p$ ?

Solution

Solution:
Answer is $p=211$ . Let $p=2d+1$ , $50 < d < 250$ . The information in the problem boils down to
$2016 = d + 21 \pmod{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$ .

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.