9
$\begingroup$

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,

  • 2
    The powers of 2 mod 400 cycle with the same period as mod 25.2012-01-21
  • 0
    ...and by [Euler's Thm.](http://en.wikipedia.org/wiki/Euler%27s_theorem) 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.2012-01-21

5 Answers 5

10

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

  • 0
    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.2012-01-21
  • 2
    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.2012-01-21
  • 0
    @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?2012-01-21
  • 1
    @hardmath It's not *hard math*. Such inferences can be expressed *functionally* in a very convenient manner that is worth remembering - see my answer.2012-01-21
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.

  • 1
    Excellent presentation. One thing I don't follow is how you equate 1/4 to -6 under mod25 arithmetic.2012-01-21
  • 0
    @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\:.$2012-01-21
1

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

0

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

0

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