How to find the Remainder upon Division of a Very Large Number?

This is a guest post by Sudeep Shukla

The statement- “When x is divided by z, it leaves y as the remainder.” is represented in modular arithmetic as-

x=y(mod z)

It can also be interpreted as “x and y leave the same remainder when divided by z.” This is also known as the congruence relation and we can say that “x is congruent to y modulo z.”

There is a property of this relation which is very useful.

Suppose x1=y1(mod z) and x2=y2(mod z), then-

x1.x2=y1.y2(mod z)

Now, coming to the original problem, suppose you have been given the seemingly tedious task of finding the remainder when and large number x^r is divided by z. Let us tackle this problem with an example.

Suppose we want to find 3^48 divided by 11. Do we go about computing 3^48 and then dividing it by 11? It might seem possible, but what if I take r=1,000,000? You surely wont find 3 raised to the power 1,000,000!

So what we do is we find a in (3)^(2k)=a mod 11 for every 2k less than or equal to r(=48).

Hence, 3^2 = 9 (mod 11)
3^4 = 81 = 4 (mod 11)
3^8 = 3^4.3^4 = 4^2 (mod 11) = 5 (mod 11) (Realize how easy finding 3^8 mod 11 was using the property stated above!)
Similarly,
3^16 = 5^2 (mod 11) = 3 (mod 11)
3^32 = 3^2 (mod 11) = 9 (mod 11)

Now, note that 48 = 2^6 + 2^5 = 32 + 16.

So to find 3^48=a mod 11, we write a (mod 11) = 6*3 (mod 11). (Again using the property)

3^48 = 3^(16+32)
= 3^16.3^32 = 3*9 (mod 11) = 5

Hence, we can very easily find the remainder, on paper, without using supercomputers, when a large number is divided by some smaller number.

P.S.: Sudeep Shukla’s blog:¬†http://dailysciencebox.blogspot.in/

About Sudeep: He is a 3rd year student at IIT Guwahati pursuing B.Tech. in Engineering Physics.

Please follow and like us:

Vineet Patawari

Hi, I'm Vineet Patawari. I fell in love with numbers after being scared of them for quite some time. Now, I'm here to make you feel comfortable with numbers and help you get rid of Math Phobia!

12 thoughts to “How to find the Remainder upon Division of a Very Large Number?”

    1. Always remember the following Result :
      if y1 % z = x1
      y2 % z = x2
      then
      (y1*y2) % z = (x1*x2)

      According to this,
      (25*25)%9 = (25%9)*(25%9) = (7*7) = 49
      but the answer is again divisible by 9 …..(49%9) = 4
      Thus the answer is 4.

      You can use this result to any number of product of numbers. Just repeat modulo division until the remainder is less than the divisor.

  1. What will be the remainder of 30^72^87 is divided by 11?
    Using this method I got the answer as 4 ,but this answer is not present in the options. Kindly help.

  2. Similar but understandable way : easy method to solve remainder – exponent questions is to find cyclicity of remainder.
    3 ^1 divided by 11 – Remainder is 3
    3 ^2 = 3*3 Remainder when 3*3 is divided by 11 = 9
    3 ^3 =(3*3)*3 Remainder when 3*9 is divided by 11 = 5
    3 ^4 =(3*3)*(3*3) Remainder when 9*9 is divided by 11 = 4
    3 ^5= Remainder when 4*3 is divided by 11 = 1
    3^6 = Remainder when 1*3 is divided by 11 = 3

    As we see the cyclicity is 5 (repetetion- 3 is repeating after 5 cycles). In 3^48, there are 15 full cycles and other 3 cycles. So remainder when 3^3 divided by 11 =5 is our answer…
    Hope this helps..

Leave a Reply

Your email address will not be published. Required fields are marked *