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

Plz tell the answer of25^25 divided by 9 remainder

I think answer should be 2:

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