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.

You may also like:

1. Find the remainder – Vedic Algebra
2. Division in Vedic Mathematics
3. Vedic Division by Nine