Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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,

share|improve this question
2  
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
add comment

5 Answers 5

up vote 10 down vote accepted

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

share|improve this answer
    
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
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. –  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
add comment

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.

share|improve this answer
    
Excellent presentation. One thing I don't follow is how you equate 1/4 to -6 under mod25 arithmetic. –  bwkaplan 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
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.