How to determine congruence manually

56 Views Asked by At

How is it possible to determine if the the following congruence is true manually?

$$ 2015^{53} \equiv 8 \pmod{11} $$

3

There are 3 best solutions below

0
On

$$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}$

0
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$$

0
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}$$