Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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


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


share|cite|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
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
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|cite|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. – Apoorv Khurasia 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|cite|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
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
No, I mean, did you actually try lhf's method, and succeed in finding the answer much faster than 1-2 minutes? – Gerry Myerson Oct 22 '12 at 21:52

Your Answer


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.