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,

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

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

  • 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