Which is the fastest way to find the remainder when $2^{400}$ is divided by $400$?

Solution 1:

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}. $$

Solution 2:

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.

Solution 3:

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}$$