Remainder of $2^{100} (\mod\ 89)$

Question

I am having trouble coming to the answer on this question:

Find the remainder when $2^{100}$ is divided by $89$. (Hint: Simplify $2^{10} \pmod{89}$ first.)

So I went with the hint and found $2^{10} = 45 \pmod{89}$, but I don't think I would want to follow that logic to ${2^{10}}^{10} = 45^{10} \pmod{89}$ and that's all I can think to do. All of the problems I've come across so far have been more straightforward, as far as simplifying to find a remainder with $\pm1$ and then playing with the equation from there.

Any help is appreciated!

Since $2^{10}\equiv 45$ then $2^{11} \equiv 90 \equiv 1$ – Winther May 16 '16 at 15:34 — Winther, May 16 '16 at 15:34
Hint: $45\times 2=1 \pmod{89}$ – Ben Grossmann May 16 '16 at 15:36 — Ben Grossmann, May 16 '16 at 15:36

score 6 · Answer 1 · answered May 16 '16 at 15:34

6

Since $89$ is a prime number,

$$2^{89} \equiv 2 \pmod{89}$$

by Fermat's Little Theorem.

Now you only need to multiply in the remainder of $2^{11} = 2^{10}\cdot 2$.

answered May 16 '16 at 15:34

Yiyuan Lee

14,435

score 4 · Accepted Answer · answered May 16 '16 at 15:34

4

Use little Fermat or the repeated squaring algorithm to compute $$ 2^{100}\equiv 2\bmod 89. $$ We have $2^{89}\equiv 2\bmod 89$ and $2^{11}\equiv 1\bmod 89$. Then multiply these congruences.

answered May 16 '16 at 15:34

Dietrich Burde

130,978

Well, this seems painfully obvious now. Thank you so much! I really have trouble seeing these things sometimes. – Carolyn May 16 '16 at 15:39

score 1 · Answer 3 · answered May 16 '16 at 15:41

1

Since $89$ is a prime so $2^{88}\equiv1\pmod {89}$ also (by brute force) $2^{12}\equiv2\pmod {89}$

So $2^{100}\equiv 2^{12}\equiv 2 \pmod{89}$

answered May 16 '16 at 15:41

Kushal Bhuyan

7,110

Remainder of $2^{100} (\mod\ 89)$

3 Answers3