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