Which is the fastest way to find the remainder when $2^{400}$ is divided by $400$? 
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,
 A: HINT $\rm \ Notice\ that\ \ mod\ a\: m:\ \ a\: b\ \equiv\ \ a\ (b\ mod\ m),\ $ since $\rm\ \ a\: m\ |\ a\: (b - b\ mod\ m)\:.\ $  
$\rm So\ \ \ mod\ 16\cdot 25:\ \ 2^{400} = 16\cdot 2^{396}\ \equiv\ 16\ (2^{396}\: mod\ 25)\:.\: $ By  $\rm\ \phi(p^2) = p\:(p-1)\ $ and little Euler
$$\rm \phi(25) = 20\ \ \Rightarrow\ \ mod\ 25:\ \ 2^{20}\: \equiv\ 1\ \Rightarrow\ 2^{396}\ \equiv \frac{(2^{20})^{20}}{4^2}\ \equiv\ \left(\frac{1}{4}\right)^2\ \equiv\ (-6)^2\ \equiv\ 11\quad  $$
Thus $\rm\ a\:b\ \equiv\ a\: (b\ mod\ m)\ \equiv\ 16\cdot 11 \pmod{16\cdot 25}\:.$
NOTE $\ $ The congruence mentioned in the first line above frequently proves handy for congruence arithmetic, so it is well worth committing to memory. As remarked, one could alternatively employ $\rm\ 2^{10}\: =\ 1024\ \equiv\: -1\pmod{25}\:,\:$ but, as the proverb says, if you give a student one $\phi$ value then you feed them one answer, but teach a student how to $\phi$ and you feed them answers for a lifetime.
A: 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}.
$$
A: As a relatively fast but purely mechanical method (not a whole lot of thought involved), I'd first note that the exponent $$400_{10}=110010000_2=2^4+2^7+2^8$$ so that $$2^{400}=2^{(2^4+2^7+2^8)}=2^{2^4}\cdot2^{2^7}\cdot2^{2^8}.$$
Now, by successively squaring:
$$\begin{align}
2^{2^1}&\equiv 4\mod 400
\\
2^{2^2}\equiv 4^2&\equiv 16\mod 400\qquad(*)
\\
2^{2^3}\equiv 16^2\equiv 256&\equiv-144\mod 400
\\
2^{2^4}\equiv (-144)^2\equiv 336&\equiv-64\mod 400
\\
2^{2^5}\equiv (-64)^2&\equiv 96\mod 400
\\
2^{2^6}\equiv 96^2&\equiv 16\equiv2^{2^2}\mod 400\qquad(*)
\\
2^{2^7}\equiv2^{2^3}&\equiv-144\mod 400
\\
2^{2^8}\equiv2^{2^3}&\equiv-64\mod 400
\end{align}$$
(Because we get the same result on the two $(*)$ lines, we now have a repeating pattern.)
So, $$\begin{align}
2^{400}&\equiv2^{2^4}\cdot2^{2^7}\cdot2^{2^8}\mod400
\\
&\equiv(-64)(-144)(-64)\mod400
\\
&\equiv176\mod400.
\end{align}$$
A: Here is what gives a straightforward application of the Chinese Remainder Theorem.
We want to compute 
$$
x:=2^{400}\bmod400.
$$
We clearly have 
$$
2^{400}\equiv0\bmod16.
$$
To calculate
$$
2^{400}\bmod25,
$$
we first note 
$$
\phi(25)=20\quad\text{and}\quad400\equiv0\bmod20.
$$
This implies
$$
2^{400}\equiv1\bmod25,
$$
yielding
$$
x\equiv0\bmod16
$$
$$
x\equiv1\bmod25,
$$
and it suffices to take for $x$ the first multiple of $16$ in the sequence 
$$
1+1\cdot25,\quad1+2\cdot25,\quad1+3\cdot25,\quad\dots.
$$
This gives 
$$
x=176.
$$
A: write 2^400/400 as (16*2^396)/400 =>2^396/25 =>((2^10)^39*2^6)/25 =>((1024)^39*64)/25 =>-1^39*(14)=-14/25=11*16(taken before)= 176Ans
