-1
$\begingroup$

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!!

$\endgroup$

closed as off-topic by Did, zhoraster, Gabriel Romon, mfl, Andrew D. Hwang Dec 3 '16 at 22:18

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Did, zhoraster, Gabriel Romon, Andrew D. Hwang
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Are you looking for hints or answers? $\endgroup$ – DAS Dec 3 '16 at 8:22
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks!! That was quite helpful... $\endgroup$ – SirXYZ Dec 3 '16 at 8:35
4
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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?

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.