Is there an easy way to find $2^p \pmod p$?

148 Views Asked by At

I'm working on a number theory problem, and was able to simplify an expression down to a quadradic in $2^p \pmod p$? Is there an easy way to compute that, or must I work it out in $O(p)$ complexity?

2

There are 2 best solutions below

0
On BEST ANSWER

If $p=2$, then of course $2^p\equiv 0\pmod p$.If $p\neq 2$, then, by Fermat little theorem, we find that $2^p\equiv 2\pmod p$.

0
On

It's congruent to 2 mod p by Fermat's little theorem.