0

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.

Norbert
  • 56,803
Rain
  • 105
  • @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
  • Do you mean chinese remainder theorem when you say you applied remainder theorem? Btw, the answer is 52. – ronno Oct 22 '12 at 11:18
  • @Rain: One can add LaTeX code between dollar signs. If you know how to write LaTeX code you will profit here ;) – Christian Ivicevic Oct 22 '12 at 11:24

2 Answers2

4

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

lhf
  • 216,483
  • 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 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
1

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.

Gerry Myerson
  • 179,216
  • 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
  • 1
    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