Calculate remainder when $2^{403}$ is divided by 22

Question

Find $2^{403}$ mod $22$.

I tried using FLT but since 22 is not prime then I can't, so I'm stuck on how to break down $2^{403}$ so its easier to compute the remainder.

Answer 1

If $2^{403}=r+22 q$ with $q,r\in \mathbb{Z}$ then $r$ is even and $2^{402}=r'+11 q$, where $r=2r'$.

Now note that $11$ is prime and by Fermat's little theorem $2^{402}=2^{10\cdot 40}4\equiv 4$ mod $11$.

Therefore $2^{403} \equiv 2\cdot 4\equiv 8$ mod $22$.

Answer 2

$2^{403} \equiv 0$ mod $2$, and $2^{403}=2^{10 \times 40} 2^{3} \equiv 8$ mod $11$, by Fermats little theorem. By the Chinese remainder theorem, $2^{403} \equiv 8$ mod $22$.

Answer 3

Well, if the Chinese Remainder Theorem slipped your mind. You can always reason:

$2^{403} = 22k + r$ and as $22$ and $2^{403}$ are even then $r$ is even.

$2^{403} = 22k + 2s$ so $2^{402} = 11k + s$. Now you can use $FLT$.

$2^{10}\equiv 1 \mod 11$ so $2^{402} \equiv 2^2 \equiv 4 \mod 11$.

So $s =4$ and $r = 8$.

... But as others have pointed out CRT theorem addresses just this problem.