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.

I have tried for almost more than an hour to find the remainder of the following

$$\frac{128^{1000}}{153}$$

I applied remainder theorem to get the answer but could not succeed. Any suggestion or help is appreciated.

Thanks.

share|improve this question
    
@Christian Ivicevic: Can you please how did you add the formatted text in title? –  Rain Oct 22 '12 at 11:04
    
Since $153 = 9\times 17$, $\phi(153) = 96$. So $128^{1000} \equiv 2^{88} \equiv 2^{-8} \equiv 103^{-1}$. Does this help? –  ronno Oct 22 '12 at 11:09
    
@ronno: I did not get you. Can you please explain how the information provided by can be used to find the remainder? –  Rain Oct 22 '12 at 11:09
2  
How much of modular arithmetic do you know? Does Euler's totient function sound familiar? –  ronno Oct 22 '12 at 11:13
    
I don't know about Euler's totient. –  Rain Oct 22 '12 at 11:15

2 Answers 2

up vote 4 down vote accepted

The main observation is that the powers $a^n$ of an integer $a$ must repeat modulo $m$ because there are only $m$ possible remainders. Once it does repeat, it repeats periodically. The period may be less than $m$.

Since $153 = 9\times 17$, consider the powers of 2 modulo 9 and 17.

Modulo 9, the powers of 2 repeat with period 6.

Modulo 17, the powers of 2 repeat with period 8.

Therefore, modulo 153 the powers of 2 repeat with period $\hbox{lcm}(6,8)=24$.

Finally, note that $128^{1000}= 2^{7000}$ and $7000 \equiv 16 \bmod 24$.

Hence, $128^{1000} \equiv 2^{16} \equiv 52 \bmod 153$.

share|improve this answer
    
Thanks lhf. Can you please give me a link where this way of finding remainder is defined? –  Rain Oct 22 '12 at 11:35
    
I think this post serves as that link --there is no magic involved, the post follows a logical structure. –  Monster Truck Oct 22 '12 at 11:41
    
The post serves the purpose, but I want to know the whole theory. Is there anything bad in knowing something something more other than only the answer? –  Rain Oct 22 '12 at 12:21
    
Rain, every introductory Number Theory textbook will tell you about factoring, about computing remainders on division by $mn$ by analyzing the divisions by $m$ and $n$ separately and then rejoining them, about the way powers repeat, and about the lcm. –  Gerry Myerson Oct 22 '12 at 12:30

You can raise a number $x$ to the power 1000 by the following steps: square it, multiply by $x$, square, multiply by $x$, square, multiply by $x$, square, multiply by $x$, square, square, multiply by $x$, square, square, square. All told, 14 operations. After each operation, replace what you have by the remainder upon division by 153 --- that way, you never have to deal with numbers more than 5 digits long. So, after 14 multiplications, and 14 divisions-with-remainder by 153, no calculation involving a number of over 5 digits, you should get your answer.

share|improve this answer
    
Thanks, but this will take long time to do. This was a question in a competitive exam where we get max 1-2 minutes of time to solve a question. –  Rain Oct 22 '12 at 12:18
1  
Then you had better smuggle a computer into the exam, because even the answer by @lhf is going to take longer than that. Good luck! By the way, in the future it would be a good idea to include important information like that in the statement of the question, so people don't waste their time and yours writing answers that won't suit your needs. –  Gerry Myerson Oct 22 '12 at 12:27
    
I am sure by lhf's method this can be solved much faster. –  Rain Oct 22 '12 at 12:37
    
Much faster than 1-2 minutes? Did you actually try it? –  Gerry Myerson Oct 22 '12 at 12:46
    
Yes. I wanted to calculate the remainder in a short cut way. Calculating it by evaluating 128 to the power 1000 is a lengthy process and kind not practical in pen and paper. I have tried it with remainder theorem, but could not reach the end. Anyway, thanks for your time and answer. –  Rain Oct 22 '12 at 12:53

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.