# 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,

-
The powers of 2 mod 400 cycle with the same period as mod 25. – lhf Jan 21 '12 at 12:55
...and by Euler's Thm. that period is length $\phi(25) = 20$, so a good place to jump in is perhaps $2^{10}=1024$ which is $-176 \mod 400$. Work out $2^{20} \mod 400$ and the final result will be evident. – hardmath Jan 21 '12 at 13:47

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

-
This is the correct answer, but I don't see how to justify your last line together without appealing to CRT. MaX asks if there's a method faster than CRT. – hardmath Jan 21 '12 at 14:15
The last line relies of the fact that if $a=b\pmod{c}$ then $da=db\pmod{dc}$. (Proof: if $a=b+nc$ then $da=db+n(dc)$. End of the proof.) No CRT in there. – Did Jan 21 '12 at 14:23
@Didier What you mention in the above comment is the key step in the solution, so why obfuscate your answer by hiding this key step in a comment? – Bill Dubuque Jan 21 '12 at 17:29
@hardmath It's not hard math. Such inferences can be expressed functionally in a very convenient manner that is worth remembering - see my answer. – Bill Dubuque Jan 21 '12 at 17:29

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.

-
Excellent presentation. One thing I don't follow is how you equate 1/4 to -6 under mod25 arithmetic. – user4536 Jan 21 '12 at 17:01
@bwkaplan $\rm\ mod\ 25\!:\ (-6)\ 4\ \equiv -24\ \equiv 1\:.\:$ Generally $\rm\:mod\ m\:$ it's easy to invert factors $\rm\:c\:$ of $\rm\ m\pm1\$ since $\rm\ c\ d\ =\ m\pm 1\ \Rightarrow\ c\ d\ \equiv \pm1\pmod{m}\$ so $\rm\ 1/c\ \equiv \pm\: d\pmod{m}\:.\:$ Above is the special case $\rm\ m = 25,\ c = 4\:.$ – Bill Dubuque Jan 21 '12 at 17:08

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

-

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}

-

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

-