How to calculate modulo of high power of 2 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!
 A: $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}$
A: $645=3\cdot 5\cdot 43$
$2^{731}\equiv -1^{731}\equiv -1 \equiv 2 \equiv (2+3+3) \equiv 8 \pmod {3}$

$\implies \left(2^{731}-8\right) \equiv 0  \pmod 3$

$2^{731}=2.2^{730}=2.4^{365}\equiv 2 \times -1^{365} \equiv -2 \equiv 3 \equiv (3+5) \equiv 8\pmod {5}$

$\implies \left(2^{731}-8\right) \equiv 0  \pmod 5$

$2^{731}=8^.\left(2^{7}\right)^{104}\equiv 8 \times -1^{104} \equiv 8\pmod {43}$

$\implies \left(2^{731}-8\right) \equiv 0  \pmod {43}$

Therefore,

$\left(2^{731}-8\right) \equiv 0  \pmod {LCM(3,5,43)}$
$\implies \left(2^{731}-8\right) \equiv 0  \pmod {645}$
$\implies 2^{731} \equiv 8  \pmod {645}$

