Modular power with Fermat

Question

Compute $2^{30}\bmod 31$ using Fermat’s little theorem.

Solution

$31$ is prime and $\mathrm{mcd}(2,31)=1$, so Fermat’s little theorem gives $2^{31-1} = 2^{30} \equiv \boxed{1} \pmod{31}.$ The result is immediate: the exponent $30 = p-1$ is exactly the one for which the theorem guarantees the value $1$.

Links

Topics: Probability distributions
Concepts: Modular arithmetic
Methods: Modular arithmetic
Skills: Computing
People: Pierre de Fermat
Exercise type: Expression evaluation