[Math] How to calculate modulo of high power of 2

Question

I know there are other such topics but I really can't figure how to calculate the following equation: 2^731 mod 645.
Obviously I can't use the little theorem of Fermat since 645 is not a prime number and I can't also do the step by step rising of powers(multiplying by 2) since the numbers are still really big. Is there any way to do calculate the result in a normal way (without the enormous numbers) ? Thanks in advance!

Answer 1

$645 = 15\cdot 43\,$ so we can compute $\,2^{\large 731}\!$ mod $15$ and $43,\,$ then combine them (by CRT or lcm).

${\rm mod}\ 15\!:\,\ 2^{\large\color{#c00} 4}\equiv 1\,\Rightarrow\, 2^{\large{731}}\equiv 2^{\large 3}\,$ by $\,731\equiv 3\pmod{\!\color{#c00}4}$

${\rm mod}\ 43\!:\,\ 2^{\large 7}\equiv -1\,\Rightarrow\,2^{\large\color{#c00}{14}}\equiv 1$ so $\,2^{\large 731}\equiv 2^{\large 3}\,$ by $\,731\equiv 3\pmod{\!\color{#c00}{14}}$

So $2^{\large 731}\!-2^{\large 3}$ is divisible by $15,43\,$ so also by their lcm = product $= 645,\,$ i.e. $\,2^{\large 731}\!\equiv 2^{\large 3}\!\pmod{\!645}$