How to find remainder when $2^{2018}$ is divided by 43?

Question

What is the remainder when $2^{2018}$ is divided by $43$?

I know that this has something to do with one of Fermat's Theorems. I am almost at a loss as to how to solve for the remainder or why it has anything to do with Fermat's Theorem

Here is Fermat's Theorem:

If $p$ is prime and $a$ is not divisible by $p$, then $$a^{p-1}\equiv 1( \text{mod }p)$$ If $a$ is divisible by $p$, then $$a^{p}\equiv a(\text{mod } p) $$

Answer 1

Is $43$ a prime? Yes.

Is $2$ divisible by $43$? No.

By Fermat's little theorem $2^{42} \equiv 1 \pmod {43}$.

Notice $2018$ is close to $2100$, we find $2018 = 2100 - 84 + 2 = 48*42+2$, so $$2^{2018} = 2^{48(42)+2} = (2^{42})^{48} 4 \equiv 1^{48} 4 \equiv 4 \pmod {43}$$

All these can be done in one's head.

Answer 2

Doing arithmetic modulo $\;43\;$ all along:

$$2^{2018}=\left(2^{43}\right)^{47}\cdot2^{-3}=2^{47}\cdot2^{-3}=2^{44}=2^{43}\cdot2=2\cdot2=4$$

Answer 3

I would do Fermat's little theorem too.

But here is a slight variation.

$$2^5 = 32 \equiv -11 \pmod{43}$$ $$2^7=2^2\cdot (-11)\equiv -44 \equiv -1\pmod{43}$$

$$2018 = 288(7)+2$$

Hence $$2^{2018}=2^2(2^7)^{288}\equiv 4(-1)^{288}\equiv 4 \pmod{43}$$

Answer 4

Without using Fermat's Little Theorem,

$$2^7\equiv-1\pmod{43}\implies2^{14}\equiv(-1)^2$$

Now $2018\equiv2\pmod{14}\implies2^{2018}\equiv2^2\pmod{43}$