solving modulo equations

Now that we have some idea about GCD. We can proceed to bit more involved topics.
Yes you may find it a bit long but a bit of reflection will show that in reality we haven't covered very many topics.





So we start with solving an equation in modulo arithmetic.

If a,n are some integers and x is an unknown integers.(Yes this unknown 'x' keeps on haunting us since we were kids)

Then how do we solve

the equation ax=1 (mod n)

Say I want to know 5x=1 (mod 13)



For some x when multiplied with 5 we must get a number which leaves remainder 1 when divided by 13.

This means we must be able to express 5x as a multiple of 13 plus 1

So we must find x such that

5x = 13*N+1

Where N is some integer. You can also think of N as quotient when 5x is divided by 13 and 1 as the remainder.



5x = 13*N+1

So with this equation as our guiding star we can venture out to get a solution.

One way to solve this will be to keep on trying some values of N 1,2,3,4…. before we get a number in RHS which is divisible by 5.

And once we get it then we can divide RHS by 5 and get our solution.Simple.

If you think a bit and if you recall the multiplication table of 13.In effect we are looking for a candidate from that table which ends in 9 or 4.As a multiple of 5 must end in 0 or 5.Therefore a multiple of 5 minus one must end in 4 or 9.

And we know that 13*3 =39 which ends with 9

So with N = 3 we get in the RHS 39+1 =40

Therefore 5x =40 and we get x=8 as a solution.

If x= 8 is a solution then we can be sure that.8+13z is also a solution.Where z is a integer.

However when solving such equations we concentrate on mod 13 and look for integers which are less than 13 as our solutions.



So we solved it and answer is 8.



But sometimes we are not so lucky and we do not have recourse to multiplication tables stored in our head.



So let us return to our Guiding Star equation and try to find a better way.



We have 5x=13*N+1



We can write it as 5x -13 N =1

Or 5x+13*(-N)=1



Does that rings a bell.



In the LHS we have two integers multiplied by some numbers x and -N.And in RHS what we have got is the GCD of 13 and 5 which in this case is 1.



In my previous mail I mentioned a famous theorem called Bezout Theorem

Which states that

xa+yb =GCD(a,b)

That is GCD can be expressed as sum of the integers a,b multiplied by some integer coefficients. And I also gave you a hint why this must be and how to go about finding these x and y.



If you superpose our guiding star equation and the Bezout equation then you can see that

What we are looking for is really the x from the Bezout equation.

Here a corresponds to 5 ,y corresponds to N and b corresponds with 13.

We really don't give a damn what N is but we are really sorely interested in x.



So we try to find x with x*5+y*13=1



So how do we go about it .Now I told the key lies in Euclid's Algorithm.



We have

When 13 is divided by 5



13=5*2+3 …………..(1)



When 5 is divided by 3



5=3*1 +2 ………………(2)



When 3 is divided by 2



3=2*1 +1 ……………….(3)



When 2 is divided by 1



2=1*2 ……………………(4)



So 1 must be the GCD.



We start from equation (1) and reach equation (3) where our GCD 1 first made its appearance.

What we plan to do is somehow get keep 13 and 5 multiplied by some integers on RHS and somehow manipulate our way down till GCD keeping the structure intact.



So we start with 1,2,3 in order.



1) 13=5*2+3 => 13 – 5*2 = 3



2) 5=3*1 +2 => 5-3*1=2 =>5- (13-5*2)*1=2=>-13+3*5=2 Replacing 3 by (13-5*2) from previous equation.



3) 3= 2*1 +1 =>1=3-2*1=>1=(13 – 5*2 )-(-13+3*5)*1=> 1=2*13-5*5

In the last equation I replaced 3 by 13 – 5*2 and 2 by -13+3*5 from (1) and (2)



So at each stage bring the remainder on one side.

And replace the coefficients from previous equations. Remember from third step onwards you will need to replace coefficients from previous two equations.



So we did it!!!



We have expressed 1 as combination of 13 and 5.



1=2*13-5*5



So what do we have for x it's -5 .

And -5 is the solution.

You can check it

5x=1 (mod 13) => 5*(-5)=1 (mod 13) =>-25=1 (mod 13) which is correct

As -25-1=-26 is divisible by 13 so last equation is correct.

And we can add a multiple of 13 to it as well to get a positive result.

So -5+13 gives 8.

So we get back what we got last time.



What is even more interesting we also solved another equation.

And that is 13x=1 (mod 5)

Yes we need 13x= 1+5*Z where Z is an integer

Or 1= 5*Z+13x

A multiple of 5 plus 1

And we already have seen 1=13*2 +(–5)*5

And so x=2 is a solution .

So to solve such equations find the corresponding Bezout's Equation via Euclid's Algorithm.

Whew !!!





Supposing we get more adventurous and now demand that.

We solve ax=b (mod n)

This time we don't have 1 on the LHS.

That is we must have

ax = n*Z+b or b =ax-n*Z where Z is an integer.

But we already know that.



GCD(a,n) = p*a+q*n for some integers p and q



Compare this with b =ax+ n*(-Z)



Now we have two equations relating a and n. They must be identical.

If b is not some multiple of GCD it is impossible for second equation to hold.

This is because the two equations should be some multiple of each other.

And b/GCD(a,n) = x/p= (-Z)/q must hold.



So we must have GCD(a,n) | b or else we cannot have any solutions.



Say if we demand that



13x=3 (mod 5)

Yes we can solve it as GCD(13,5)=1

And 1 divides 3.



But if we say that

25x= 9 (mod 5)

There's no solution as GCD(25,5) =5 and 5 doesn't divide 9.

Now we have another rule to contend with. Which I have already mentioned in the passing in my first few mails.

Here it is again for your reference.

Say a= b (mod n)

And say k|a and k|b

And we need to divide by both sides of equation by the same number k.

If GCD(k,n) =1 then fine we can have

a/k = b/k (mod n)



But if GCD(k,n)= g



Then we must have a/k=b/k (mod n/g)

Yes the modulo gets divided by g.



Why?

As a=b (mod n)

We have n| (a-b)

And we must have .Since k|a and k|b so we can write

a= n1*k and b=n2*k

or n|(n1*k – n2*k) or n| (k*(n1-n2))

If n doesn't divide k then all's well , then n must divide (n1-n2).

Or n|(n1-n2)

That way we can cancel k out from there.

So a=b (mod n)

n1*k = n2*k (mod n)

we can cancel k out n1=n2 (mod n)

and we have already proved n|(n1-n2)



Problem starts when GCD(n,k) is not 1.That is they have a common factor.



Then if n|(k*(n1-n2)) holds true.

Then we no longer can say n| (n1-n2) .

So supposing we write k =GCD(k,n)* N1

And n=GCD(k,n)*N2



Where N1,N2 are some integer.





So we have n|(k*(n1-n2)) => (GCD(k,n)*N2) | (GCD(k,n)* N1 *(n1-n2))



Now if we cancel the GCD we can write.

N2| N1*(n1-n2)



Notice now N1 and N2 have no common factor left as we cancelled out all common factors from them.Or you can say we cancelled everything that was common from there signatures so they have nothing common left and GCD(N1,N2)=1

Now we can write



a/k = b/k (mod n/g)



you can check this.

Say 50 =100 (mod 25)

Then if we cancel out 10

We have 5=10( mod 25/ GCD(25,10))

Or 5= 10 (mod 25/5)

5=10 (mod 5)



Notice if we hadn't divided 25 we would had got wrong result.

I,e 5=10 (mod 25 ) which is FALSE.





Say if we try to solve.



25x = 15 (mod 10)

GCD (25,10) is 5 and 5 divides 15 and we must have a solution.

So dividing by 5 we get.

25x =15 => 5x = 3 ( mod 2)

We need to get x now .

Which we find by Euclid's algo or even by trial and error.

So we find 5*1-2*2 =1=GCD(2,5)

So 3 times this equation gives.

5*3 – 2*6 =3 …..We got it

So 3 which is 5's coefficient is a solution.

Check it 5*3 =15 = 3 (mod 2) IS TRUE

But if 3 is a solution so is 3+2*k where k is some integer.

And we know we have to finally get a solution in mod 10

So we find all other solutions which are less than 10.

We get many solutions PUTTING k=-1,1,2,3,4

1,3,5,7,9

You can substitute them back in 25x=15 (mod 10 ) and check.

Yes they all satisfy it.

So don't forget to convert it back to higher base if you divided the equation.

Notice a solution in mod 2 gives a lots of solutions in higher mod 10.

Though 25x= 15 ( mod 10) is pretty lame equation and you can easily guess without actually solving it this way.