Battle with Modulo

Ohh god this modulo and modular is really amazing :P

                                   "You always fear from what you don't understand" 

Modulus is an operation which is used to obtain the remainder when two numbers are divided.

Suppose a = 5 and b = 3, then 

a%b = 5%3 =2

Modulus is distributive over addition, subtraction and multiplication. 

9%6 = (4 + 5) % 6 = 4 % 6 + 5 % 6 = 4 + 5 =9

13%6 = (15 - 2) % 6 = 15 % 6 - 2 % 6 = 3 - 2 = 1

26%6 = (13 * 2) % 6 = 13 % 6 * 2 % 6 = 1 *2 = 2

But the problem comes in case of division.

Consider 4/5 in modulo 6.

i.e 4/5 != (4 % 6) / (5 % 6)                                      (1)

So here comes in picture Modular Inverse.

4/5 in modulo 6 equals 2. Ok now lets see the RHS of (1) in another form

(4 % 6)/(5 % 6) = ((4 % 6) * (5^(-1) % 6))%6        (2)

Since 5 and 6 are coprime(I will explain why is this necessary), So the inverse of 5 exists in ring of 6.

i.e. a number x such that x * 5= 1 mod 6 and that is 5. So 5^(-1)=5

Now taking eq(2) further,

(4*5)%6=20%6=2. Voila the answer is 2. Great!!.

But what if the numbers are not coprime, say 2/4. Lets take this case and solve it in this way

We need an x such that x*2=4 mod 6. 

If x=2 then 4 = 4 mod 6. Wait 5??

Yes if x =5. then 2/5=10 = 4 mod 6, So how come two inverse can exist.

Hence it is necessary that the numbers should be relatively prime (or coprime in short) to each other. Then only the uniqueness of the inverse element can be determined. 

So this leads us to an important conclusion that a number can have either one or no inverse element. The inverse of element can be a or any other integer.

Now comes the important point is how to compute this inverse. Great. Remember Euclid algorithm to compute GCD of two numbers. Yes we can use that and its called Extended Euclid Algorithm.

According to Bezout's Identity, two numbers can be expressed in the form of

                             d = ax + by
where d is the GCD of a and b.

To be continued...