What is the remainder of $2^{4000}$ divided by 99?

Question

Can someone guide me on how to find solution to such problems within a minute as that is the amount of time I will be given during my exams. also share what answer you get as I got different answers for same question with different methods

Answer 1

Mod 99:

$2^{10} ≡ 1024 ≡ 100*10 + 24 ≡ 10+24 ≡ 34$
$2^{20} ≡ 34*34 ≡ 1156 ≡ 11+56 ≡ 67$
$2^{30} ≡ 67*34 ≡ 2278 ≡ 22+78 ≡ 100 ≡ 1$

$2^{4000} ≡ 2^{133*30+10} ≡ 2^{10} ≡ 34 \text{ (mod 99)}$

---

Second way, if we know order(2,99) divides $\phi(99)$

$\phi(99) = \phi(3^2*11)= 99({2\over3})({10\over11}) = 60$

$2^{4000} ≡ 2^{66*60+40} ≡ 2^{40} ≡ 67^2 ≡ 4489 ≡ 44+89 ≡ 34 \text{ (mod 99)}$

Answer 2

$2^5\equiv-1\mod 11$ and $2^3\equiv-1\mod 9,$ so $2^{15}\equiv-1\mod 11$ and $\mod 9,$

so therefore $2^{15}\equiv-1\mod 99$ and $2^{30}\equiv1\mod99,$ so $2^{4000}= 2^{3990}2^{10}\equiv2^{10}\mod 99$.

Now $2^{10} \equiv1\mod 11$ and $2^{10}\equiv2^92\equiv(-1)^32\equiv-2\equiv7\mod9$.

Use the Chinese Remainder theorem to conclude $2^{10}\equiv34\mod99$.

Answer 3

Even knowing what to do, it took me $40.95$ seconds (according to my smartphone's stopwatch) to arrive at the answer. Here's what I thought (in text) and what I wrote down (in displayed equations):

$99$ is $9$ times $11$, and $2^{10}$ is $1$ mod $11$, so $2^{4000}$ is

$$\equiv1\,(11)$$

$2^3$ is $-1$ mod $9$, so $2^6$ is $1$ mod $9$ so $2^{4000}$ is $2^4$ mod $9$ since $3996$ is divisible by $2$ and $3$, so $2^{4000}$ is

$$\equiv16\,(9)$$ $$\equiv7\,(9)$$

so I'm looking for something that's $1$ more than a multiple of $11$ in

$$7,16,25,34,\ldots$$

Aha, $34=33+1$. So that's the answer.

(Remark: I didn't actually write down the comma-dot-dot-dot after the $34$, but I did add some underlining to indicate I'd found the answer. I only added the ellipsis in the display to indicate I was prepared to keep going.)

I could have saved a few seconds if I hadn't bothered going backwards from $16$ to $7$, and another few seconds, maybe, if I had simply remembered that $\phi(9)$ is $6$. However, the $40.95$ does not count the time I spent thinking about what I was going to have to do while I was getting my phone out of my pocket. I'd be interested in how long it takes others to carry out the requisite calculations.