Remainder when $2^{108}$ is divided by $11$?

Question

What is the remainder obtained when $2^{108}$ is divided by $11$?

I tried bringing in $11$ in the given no. such as in

$(11-3)^{36}$

and then using binomial expansion...but its not helping. Any clues??

Thanks in advance!!

Answer 1

Without using knowledge about $11$ being prime, you can think about multiples of $11$ and powers of $2$ and see if you can identify some that are close to each other. $33$ is close to $32$. Mod $11$, you have that $2^5\equiv-1$.

So $$2^{108}\equiv\left(2^{5}\right)^{21}2^3\equiv(-1)^{21}8\equiv-8\equiv3$$

Answer 2

Fermat's little theorem states that if $p$ is prime, then $a^{p-1} \equiv 1 \mod p $

Hence $2^{10} \equiv 1 \mod 11$

(if you are not familiar with Fermat's result, notice that $2^5=32=33-1= 3 \times 11 -1$, hence $2^5 \equiv -1 \mod 11$, and hence $2^{10} \equiv 1 \mod 11$.)

$$2^{108} \equiv 2^{10 \times 10 +8} \equiv 2^8(2^{10})^{10} \equiv 2^8 \equiv 256 \equiv 3 \mod 11$$

Answer 3

I'm assuming you are not familiar with modular arithmetic. For integers $a$ and $b$ we write $$a \equiv b \pmod{11}$$ if and only if $a-b$ is divisible by $11$. Show that if $a,b,c,d$ are integers, $a \equiv b \pmod{11}$ and $c \equiv d \pmod{11}$ then $a \times c \equiv b \times d \pmod{11}$.

If you show this then you can calculate $2^{10}$ as follows: $$ 2^4 = 16 \equiv 5 \pmod{11} $$ $$2^8 = 2^4 \times 2^4 \equiv 5 \times 5 \pmod{11} \equiv 25 \pmod{11} \equiv 3 \pmod{11}$$ $$2^{10} = 2^8 \times 2^2 \equiv 3 \times 2^2 \pmod{11} \equiv 12 \pmod{11} \equiv 1 \pmod{11}$$ Now you have $2^{10} \equiv 1 \pmod{11}$ and you know that if $a \equiv b \pmod{11}$ and $c \equiv d \pmod{11}$ then $a \times c \equiv b \times d \pmod{11}$, can you find the answer?