Determine the remainder

Question

Determine the remainder when $2^{2018}$ is divided by $55$

Answer 1

1-method. We will use the following congruences: $$2^6\equiv 64\equiv 9 \pmod{55};\\ 9^2\equiv 81\equiv 26 \pmod{55};\\ 26^2\equiv 676\equiv 16 \pmod{55}$$ to solve the main problem: $$2^{2018}\equiv (2^6)^{336}\cdot 2^2\equiv (9^2)^{168}\cdot 2^2\equiv (26^2)^{84}\cdot 2^2\equiv (2^6)^{56}\cdot 2^2\equiv\\ (9^2)^{28}\cdot 2^2\equiv (26^2)^{14}\cdot 2^2\equiv (2^6)^9\cdot 2^2\equiv (9^2)^4\cdot 9\cdot 2^4\equiv \\ (26^2)^2\cdot 9\cdot 2^4\equiv (2^6)^2\cdot 9\equiv 9^2\cdot 9\equiv 26\cdot 9\equiv 220+14\equiv 14\pmod{55}.$$

2-method. Based on the Euler's theorem: we have $\varphi(55)=40$ and: $$2^{\varphi(55)}\equiv 2^{40}\equiv 1 \pmod{55} \Rightarrow \\ 2^{2018}\equiv (2^{40})^{50}\cdot 2^{18}\equiv 2^{18}\equiv (2^{6})^3\equiv 9^3\equiv 9^2\cdot 9\equiv 26\cdot 9\equiv 220+14\equiv 14\pmod{55}.$$

P.S. You can learn the theorem as well as the modular arithmetic operations.

Answer 2

As Carmichael Function $\lambda(55)=20$ and $(55,2)=1$ and $2018\equiv-2\pmod{20}$

$$2^{2018}\equiv2^{-2}\pmod{55}$$

Now as $14\cdot4\equiv1\pmod{55},4^{-1}\equiv14$