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. 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. Tianzi says:

Thanks for this post. How could we prove this?

2. sakshi says:

Plz tell the answer of25^25 divided by 9 remainder

1. Abhishek Garg says:

I think answer should be 2:

1. Mayukh Biswas says:

It’s 7

2. Mayukh Biswas says:

It’s 7

2. Jael Jefina J says:

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

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

3. Aishi says:

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.

4. Ashrit says:

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

5. sandeept491 says:

6. sathish says:

I want another example. Can u able plz explain me?

7. sathish says:

Plz explain another example.

8. sathish says:

I cannot understand. Plz briefly explain another example

9. harsha says:

can not understand will you explain it briefly?????

10. Arnab says:

Good trick!! It helps a lot in olympiads….

11. aniket says:

I can not understand.can you please explain with another example in brief?

12. satish says:

Good one simple yet powerful…….