Which is the fastest way to find the remainder when $2^{400}$ is divided by $400$?
My approach is to break up $400$ as $16 \times 25$ and then apply CRT, I was wondering if there is any other approach that gives the result faster than using CRT.
Thanks,
Best Answer
Since $2^{10}=1024=-1\pmod{25}$ and $396=39\times10+6$, $$ 2^{396}=(-1)^{39}\times2^6=-64=11\pmod{25}. $$ Since $25\times16=400$ and $2^{396}\times16=2^{400}$, $$ 2^{400}=16\times2^{396}=16\times11=176\pmod{400}. $$