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

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

Thanks for this post. How could we prove this?

Plz tell the answer of25^25 divided by 9 remainder

I think answer should be 2:

It’s 7

It’s 7

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.

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.

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

Thank you Sudeep.It is helpfull.

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

Plz explain another example.

I cannot understand. Plz briefly explain another example

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

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

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

Good one simple yet powerful…….