show that the remainder of $\frac{2^{100}}{23}$ is $2$

Question

As stated in the title, I'm supposed to show that $$2^{100}\equiv 2 \pmod {23}$$

I can't really wrap my head around this. At first I thought the book said that $a \equiv a^x$ no matter the exponent, but this doesn't seem to hold true since $2^1, 2^2, 2^3$ etc all seem to have different remainders when divided by 23.

So how "do" you arrive at this conclusion?

Thanks in advance!

Answer 1

Hint: $2^{100}\equiv 2 \bmod {23}$ iff $2^{99}\equiv 1 \bmod {23}$. So try $2^k \bmod {23}$ for $k=1,9,11$, the proper divisors of $99$.

Answer 2

You can do it with Fermat's theorem.

You can also easily do it by hand in the following manner:

if you do the repeated product of $2$ modulo $23$ you get

$1,2,4,8,16,9,18,13,3,6,12$

and next $2 \times 12 = 24 \equiv 1 \mod 23.$

As you see, the powers of 2 form a cyclic group of order 11. Then you have to see that $100 \mod 11 = 1$, because $100 = 9 \times 11 +1$.

This means that $2^{100} = 2^1 = 2.$

Answer 3

Here's a trick without using Fermat's Little Theorem that can arrive at the answer you need quickly (commonly done in computer science for optimization):

We have $100 = 64 + 32 + 4$.

$$ 2^{2}\equiv 4 \bmod 23 $$ $$ 2^{4}\equiv 4^2 \equiv 16 \bmod 23 $$ $$ 2^{8}\equiv 16^2 \equiv 3 \bmod 23 $$ $$ 2^{16}\equiv 3^2 \equiv 9 \bmod 23 $$ $$ 2^{32}\equiv 9^2 \equiv 12 \bmod 23 $$ $$ 2^{64}\equiv 12^2 \equiv 6\bmod 23 $$ Therefore:

$$ 2^{100}\equiv 2^4\times2^{32}\times2^{64} \equiv 16\times12\times6 \equiv 2\bmod 23 $$

Answer 4

Hint $\bmod 23\!:\ 2\equiv 5^{\large 2}\overset{(\ \ )^{\LARGE 11}\!\!\!\!}\Longrightarrow\ 2^{\large 11}\!\equiv \overbrace{5^{\large 22}\equiv 1}^{\rm Fermat}\,$ $\overset{(\ \ )^{\LARGE 9}\!\!}\Longrightarrow\, 2^{\large 99}\equiv 1\overset{\large \times\ 2\ }\Longrightarrow\ 2^{\large 100}\equiv 2$

Edit $ $ Comments reveal little Fermat is unknown. Instead $ \ 1\equiv 3(2^{\large 3}) \overset{(\ \ )^{\LARGE 3}\!\!}\Longrightarrow\ 1\equiv 4(2^{\large 9})\equiv 2^{\large 11}$

Alternatively We can enumerate small powers of $,2\,$ by successively doubling, starting with $\,2^4\equiv 16,\,$ then $\,\ 2(16)\equiv 32\equiv \color{#0a0}9,\ $ $\, 2(9)\equiv 18\equiv \color{#90f}{-5},\,\ldots$

$$\!\!\begin{array}{|r|r|} \hline n & 4&5&6&7&8&9&10&\color{#c00}{11}\\ \hline 2^{\large n}\bmod 23 &16&\color{#0a0}9&\color{#90f}{-5}&-10&3&6&12&\color{#c00}1\\ \hline \end{array}\qquad$$

Answer 5

There's a trick you can use to evaluate any large power $\ a^b\ $, say, modulo a moderately sized one $\ c\ $, say, reasonably easily. The trick is to write $\ b\ $ in binary form, $\ b = 2^{b_1} + 2^{b_2} + \dots + 2^{b_r}\ $, say, with $\ b_1 < b_2 < \dots < b_r\ $, compute the values $\ a^2\ (\mbox{mod } c), a^{2^2} (\mbox{mod } c), \dots, a^{2^{b_r}} (\mbox{mod } c)\ $ by successively squaring $\ a\ (\mbox{mod }c)\ $, then computing $\ a^b\ (\mbox{mod } c) = a^{2^{b_1}}a^{2^{b_2}} \dots a^{2^{b_r}} (\mbox{mod } c)\ $. For your problem, $\ a=2, b=100\ $ and $\ c=23\ $, and $\ 100 = 2^2 + 2^5 + 2^6\ $, so you only have to compute $6$ successive squares of $\ 2\ (\mbox{mod } 23)\ $, which are $\ 4, 16, 3, 9, 12\ $ and $\ 6\ (\mbox{mod }23)\ $, and multiply the second, fifth and sixth of these together: $16\cdot12\cdot6 \ (\mbox{mod }23)\ $, which should give you the result you're looking for.

Answer 6

Using Euler Totient (or Fermat’s Little Theorem), we see that $$2^{\phi(23)}=2^{22}\equiv1\pmod(23)$$

Hence, $$2^{100}=(2^{22})^4\cdot2^{12}\equiv1^4\cdot2^{12}\pmod{23}$$ $$=(2^6)^2=64^2\equiv(-5)^2=25\equiv2\pmod{23}$$

Answer 7

As $$2^{11}=32^2\cdot2\equiv9^2\cdot2\equiv12\cdot2\equiv1\pmod{23}$$

We see that $$2^{100}=(2^{11})^9\cdot2\equiv1^9\cdot2=2\pmod{23}$$