How is it possible to determine if the the following congruence is true manually?
$$ 2015^{53} \equiv 8 \pmod{11} $$
How is it possible to determine if the the following congruence is true manually?
$$ 2015^{53} \equiv 8 \pmod{11} $$
On
$2015\bmod11=5-1+0-2=2$, hence $\;2015^{53}\equiv2^{53}\mod11$. Since $11$ is prime, by Little Fermat: $$2^{53}\equiv2^{53\bmod10}=2^3$$
On
Since $2015 = 11 \cdot 183 + 2$, then $2015 \equiv 2 \pmod{11}$.
Our problem has now been reduced to showing that $2^{53} \equiv 8 \pmod{11}$.
Since $2^{53} = \left(2^5\right)^{10} \cdot 2^3 \pmod{11}$ and $2^5 = 32\equiv -1 \pmod{11}$ then $$2^{53} \equiv (-1)^{10} \cdot 2^3 \pmod{11} = 8 \pmod{11}$$
$$2015\equiv2\pmod{11}\implies2015^{53}\equiv2^{53}$$
Method $\#1:$
Now $2^5=32\equiv-1\pmod{11}$
and consequently, $2^{53}=(2^5)^{10}2^3\equiv(-1)^{10}2^3\pmod{11}$
Method $\#2:$
Using Fermat's little theorem, $2^{11-1}\equiv1\pmod{11}$ and $53\equiv3\pmod{10}$
$\implies2^{53}\equiv2^3\pmod{11}$