MathDB

24

Part of 2017 Harvard-MIT Mathematics Tournament

Problems(1)

2017 Guts #24: How to find 2^2016 mod p?

Source:

2/21/2017
At a recent math contest, Evan was asked to find 22016(modp)2^{2016} \pmod{p} for a given prime number pp with 100<p<500100 < p < 500. Evan has forgotten what the prime pp was, but still remembers how he solved it:
[*] Evan first tried taking 20162016 modulo p−1p - 1, but got a value ee larger than 100100. [*] However, Evan noted that e−12(p−1)=21e - \frac{1}{2}(p - 1) = 21, and then realized the answer was −221(modp)-2^{21} \pmod{p}.
What was the prime pp?
number theory