Before I begin let us visit the topic of “numbers prime to each other.”
Recall that two numbers are called ‘prime to each other’ if they don’t have any prime factor in common.
Such numbers are also called co prime to each other.
It follows that if they don’t have any prime factor in common they don’t have any factor in common be it prime or composite.
How can we be sure that two numbers are co prime.
Say 1001 and 14.
How do we find out if they are co prime?
Factorise each of them into primes.
1001 =13*7*11
14=7*2
They have a 7 in common. So they cannot be co prime.
But
35 and 11
18 and 25
39 and 7
171 and 62
Are all co primes
If you think a bit you’ll realize that GCD of co prime numbers is 1.
In GCD what are we looking for are prime factors which are present in prime factorization of both the numbers. If they don’t have anything in common there GCD has to be 1.That is only 1 can divide both of them and leave no remainder.
Another good way to think of co prime numbers is this..
Say a and b are co prime
Then the fraction a/b cannot be reduced any further.
Why because we don’t have anything common in numerator and denominator that can be cancelled out.
Say 14/9 it cannot be reduced
But 14/49 can be reduced to 2/7
by cancelling out 7 in numerator and denominator
With that in mind we start with Fermat’s Little Theorem.
It says
a^(p-1) = 1 (mod p)
if ‘a is prime ‘
and ‘a and p are co prime’
What is nice about this theorem is RHS. It is 1
Often we are given sums like..
What is the remainder when 27^5977 is divided by 7.
We realize immediately that 7 is prime
And 27 is co prime with 7
We forget the giant number 5977 given to scare us and write the result we can get from Fermat’s theorem
The result is.
27^(7-1) =1 (mod 7 )
27^6 =1 (mod 7)
This result is then exploited to arrive at the sought remainder quickly.
We figure out how many times 5977 goes by 6.
5977= 996*6+1
Therefore
27^(5977)=27^(996*6+1) = (27^(996*6) ) * ( 27^1)
Now
27^(996*6) = (27^6)* (27^6)* (27^6)…. 996 times
=1*1*1….996 times =1 (mod 7)
That is we replaced each of 27^6 by 1 as 27^6 =1 (mod 7)
So what are we left with is
(27^(996*6) ) * ( 27^1) =1 * (27^1) (mod 7) = 27 (mod 7)
And 27 leaves remainder 6 when divided by 7
So 27 =6(mod 7)
Therefore answer is 6.
Try this trick for more problems.
Sunday, August 26, 2007
Tuesday, July 24, 2007
Diophantine Again
In my last post I introduced you to Linear Diophantine Equations.(Let us call them LDE for short)
We couldn’t help Alice but there were lessons learnt. (For example we shouldn’t be dreaming while spending money and later find to our dismay that some mystical equation fails to get our balances right )
Yet again I will like to emphasise that there can be lots of different ways to approach the same problem and you don’t need to follow exactly same steps to arrive at a solution.
Steps I outlined are very broad in nature.
You are free to follow your own course with basics in mind.
You must have already noticed that we depend a lot on the Bezout equation.
That is for two integers a and b we can have
ax+by = GCD(a,b)
I cannot overemphasise how important this equation is.
If you think a bit you will realise that this equation immediately gives us a way to relate two strangers in the world of integers a and b.
a and b can be anything and yet we find to our delight that they are related.
And as you might expect mathematicians have a special name for this kind of relation.
We say that GCD(a,b) can be expressed as linear combination of a and b.
This is just another way of saying that three numbers GCD(a,b),a and b are related.
To put it more formally we say that three entities say A,B,G are LINEARLY DEPENDENT if we can write a equation relating them as
xA+yB+zG=0
such that x ,y,z are not all zero. So if you think a bit you will immediately notice that Bezout equation accomplishes exactly the same thing. So if you plug in a for A , b for b and GCD(a,b) for G we can say with full confidence that these are linearly related for we know for sure we can find values for x and y such that they are not zero.
Note that g is -1.
Actually g=-1 or x and y are some values determined by Euclid’s Algorithm really doesn’t make any difference as long as they are not equal to zero all at a same time.
You can also extend this idea to n entities A,B,C,D,E….. instead of just three of them.
Now supposing we cannot find a solution and only way to relate A,B,G through a equation is such that x=y=z=0.Then we say A,B,G are LINEARLY INDEPENDENT. Fortunately we are not going to deal with such estranged entities, not for now at least.
So let us revisit the same old LDE and this time in a more systematic way.
Say we want to solve
4P+2E=18
Since GCD(4,2) = 2
And since 2|18 we know there is a solution.
We can start with Bezout equation for 4 and 2
4x+2y =2
We try to find x and y
One solution is x=1 and y=-1 you can find this by trial and error.
So we write
4(1)+2(-1)=2
Multiply by 9 and get
4(9)+2(-9)=18
So P=9 and E=-9 is a solution.
We try to find all possible solutions.
I will tell you how to write the solution immediately then furnish a proof.
Say we have equation ax+by =c
And supposing we found one solution. x0 ,y0 .In this case we found (9,-9)
Then all values for x and y can be found as following.
x = x0 + t (b/GCD(a,b))
y= y0 - t (a/GCD(a,b))
t is free running parameter. For each value of t we obatin a new solutuion.
t can be any integer negative , positive or 0.Thus we can write with equal justification .
x = x0 - t (b/GCD(a,b))
y= y0 + t (a/GCD(a,b))
Which means whether you put t with minus sign in first equation or last doesn’t matter as long they appear with opposite signs in the two equations. This is because t can be negative integer as well.
Now what is multiplied by t is b or a divided by GCD(a,b)
Notice that it is b when we are finding x. So if we are finding x we take coefficient of y.
And when we are finding y we take coefficient of x.So we exchange coefficients for x and y.
Say we want a general solution of P and E
We just found P=9 and E=-9
So we can immediately write general solution for P we can write
We already know GCD(4,2) = 2
So we can write
P=(9)+t(2/2) or P=9 + t 1
This 2 is GCD(4,2)
2 is coefficient of E that’s why it appears here in expression for P
We exchange the coefficients for P and E.
Similarly for for E we can write
E = (-9) –t (4/2) or E = (-9) - 2t
This 2 is GCD(4,2)
This 4 is coefficient of P that’s why it appears in
expression for E. We exchange coefficients.
So we have P=9+t
And E=-9-2t
As I already mentioned that if we write
P=9-t
and E =-9 +2t this set will also be correct .Sign of t doesn’t matter as log as it is opposite in these two equations. And we can proceed with any one of them without giving a second thought.
So let us retain the first.
P=9+t
E=-9-2t for now and proceed.
Out of infinite possible solutions for all values of t we know that Pencils and Erasers can’t be negative so we can write.
P>0 and E >0
If you notice if we give negative values for t , E tends to get a more positive value.
Note that if we give t=-5 then we get E=1 and P=4
If we give t=-6 then E= 3 and P=3
if t=-7 then E=5 and P=2
if t=-8 then E=7 and P=1
if t=-9 then E=9 and P=-1 and here we have to stop as erasers are becoming negative so we have four solutions.
We could have written all this a bit more compactly
We already know P > 0 so P=9+t > 0 or t > -9
And E>0 gives -9-2t > 0 or -9 > 2t or -9/2 > t or -4.5> t
But since t can be integer only so -4.5 > t means -5 >t
So we get
P=9+t
E=-9-2t where -9 < t < -5 All this looks very neat in three lines.
I will show you yet another example then we will be done for LDEs.
This time we chose a LDE which looks like it means business.
3456x+246y=234
Here we first find GCD(3456,246)
So we start with Euclid’s Algorithm
246| 3456 |14
- 246
---------------------
996
-984
-----------------------
12|246 |20
-24
-----------------------------
xx6 |12 |2
-12
------------------------------
xx
So 6 is the GCD
We immediately check whether 6 divides 234 it does so we have a solution.
Now we have to determine a solution for 3456x+246y=234
We start by writing steps in Euclid’s Algo.
3456=246*14+12 => 12 = 3456 -246 *14 …..Equation 1
246=12*20+6 => 6= 246 -12*20 … Equation 2
12=6*2 /* Not needed */
Substitute 12 in equation 2 by expression for 12 in equation 1
So 6= 246 – (3456 -246*14)*20
6= 246- 3456*20 +246*280
6= 246*281 -3456*20 This is it.
Multiply the whole thing by 39
6*39 =246*(281*39)-3456*(20*39)
234=246 *(10959)-3456*(780)
So one solution is 10959,780
We can now write the complete solution.
x= 10959 + t *(3456/6) so x=10959 +t * 576
y=780 - t*(246/6) so y=780-t*41 where t is any integer.
Depending upon whether x,y stand for pencils and erasers of forgetful Alice or Number of coins in my pocket you can enforce conditions like x>0 and y>0 and get a subset of above solution..(Yes here you end up with so many coins in your pocket. A pound has 100 pence and here each pence counts. Even one pence is valued. Wonder what happened to our own paisa)
Now I think if you see a LDE you can immediately write the solution just by looking at it. Let us hope we have better luck with Alice next time.
We couldn’t help Alice but there were lessons learnt. (For example we shouldn’t be dreaming while spending money and later find to our dismay that some mystical equation fails to get our balances right )
Yet again I will like to emphasise that there can be lots of different ways to approach the same problem and you don’t need to follow exactly same steps to arrive at a solution.
Steps I outlined are very broad in nature.
You are free to follow your own course with basics in mind.
You must have already noticed that we depend a lot on the Bezout equation.
That is for two integers a and b we can have
ax+by = GCD(a,b)
I cannot overemphasise how important this equation is.
If you think a bit you will realise that this equation immediately gives us a way to relate two strangers in the world of integers a and b.
a and b can be anything and yet we find to our delight that they are related.
And as you might expect mathematicians have a special name for this kind of relation.
We say that GCD(a,b) can be expressed as linear combination of a and b.
This is just another way of saying that three numbers GCD(a,b),a and b are related.
To put it more formally we say that three entities say A,B,G are LINEARLY DEPENDENT if we can write a equation relating them as
xA+yB+zG=0
such that x ,y,z are not all zero. So if you think a bit you will immediately notice that Bezout equation accomplishes exactly the same thing. So if you plug in a for A , b for b and GCD(a,b) for G we can say with full confidence that these are linearly related for we know for sure we can find values for x and y such that they are not zero.
Note that g is -1.
Actually g=-1 or x and y are some values determined by Euclid’s Algorithm really doesn’t make any difference as long as they are not equal to zero all at a same time.
You can also extend this idea to n entities A,B,C,D,E….. instead of just three of them.
Now supposing we cannot find a solution and only way to relate A,B,G through a equation is such that x=y=z=0.Then we say A,B,G are LINEARLY INDEPENDENT. Fortunately we are not going to deal with such estranged entities, not for now at least.
So let us revisit the same old LDE and this time in a more systematic way.
Say we want to solve
4P+2E=18
Since GCD(4,2) = 2
And since 2|18 we know there is a solution.
We can start with Bezout equation for 4 and 2
4x+2y =2
We try to find x and y
One solution is x=1 and y=-1 you can find this by trial and error.
So we write
4(1)+2(-1)=2
Multiply by 9 and get
4(9)+2(-9)=18
So P=9 and E=-9 is a solution.
We try to find all possible solutions.
I will tell you how to write the solution immediately then furnish a proof.
Say we have equation ax+by =c
And supposing we found one solution. x0 ,y0 .In this case we found (9,-9)
Then all values for x and y can be found as following.
x = x0 + t (b/GCD(a,b))
y= y0 - t (a/GCD(a,b))
t is free running parameter. For each value of t we obatin a new solutuion.
t can be any integer negative , positive or 0.Thus we can write with equal justification .
x = x0 - t (b/GCD(a,b))
y= y0 + t (a/GCD(a,b))
Which means whether you put t with minus sign in first equation or last doesn’t matter as long they appear with opposite signs in the two equations. This is because t can be negative integer as well.
Now what is multiplied by t is b or a divided by GCD(a,b)
Notice that it is b when we are finding x. So if we are finding x we take coefficient of y.
And when we are finding y we take coefficient of x.So we exchange coefficients for x and y.
Say we want a general solution of P and E
We just found P=9 and E=-9
So we can immediately write general solution for P we can write
We already know GCD(4,2) = 2
So we can write
P=(9)+t(2/2) or P=9 + t 1
This 2 is GCD(4,2)
2 is coefficient of E that’s why it appears here in expression for P
We exchange the coefficients for P and E.
Similarly for for E we can write
E = (-9) –t (4/2) or E = (-9) - 2t
This 2 is GCD(4,2)
This 4 is coefficient of P that’s why it appears in
expression for E. We exchange coefficients.
So we have P=9+t
And E=-9-2t
As I already mentioned that if we write
P=9-t
and E =-9 +2t this set will also be correct .Sign of t doesn’t matter as log as it is opposite in these two equations. And we can proceed with any one of them without giving a second thought.
So let us retain the first.
P=9+t
E=-9-2t for now and proceed.
Out of infinite possible solutions for all values of t we know that Pencils and Erasers can’t be negative so we can write.
P>0 and E >0
If you notice if we give negative values for t , E tends to get a more positive value.
Note that if we give t=-5 then we get E=1 and P=4
If we give t=-6 then E= 3 and P=3
if t=-7 then E=5 and P=2
if t=-8 then E=7 and P=1
if t=-9 then E=9 and P=-1 and here we have to stop as erasers are becoming negative so we have four solutions.
We could have written all this a bit more compactly
We already know P > 0 so P=9+t > 0 or t > -9
And E>0 gives -9-2t > 0 or -9 > 2t or -9/2 > t or -4.5> t
But since t can be integer only so -4.5 > t means -5 >t
So we get
P=9+t
E=-9-2t where -9 < t < -5 All this looks very neat in three lines.
I will show you yet another example then we will be done for LDEs.
This time we chose a LDE which looks like it means business.
3456x+246y=234
Here we first find GCD(3456,246)
So we start with Euclid’s Algorithm
246| 3456 |14
- 246
---------------------
996
-984
-----------------------
12|246 |20
-24
-----------------------------
xx6 |12 |2
-12
------------------------------
xx
So 6 is the GCD
We immediately check whether 6 divides 234 it does so we have a solution.
Now we have to determine a solution for 3456x+246y=234
We start by writing steps in Euclid’s Algo.
3456=246*14+12 => 12 = 3456 -246 *14 …..Equation 1
246=12*20+6 => 6= 246 -12*20 … Equation 2
12=6*2 /* Not needed */
Substitute 12 in equation 2 by expression for 12 in equation 1
So 6= 246 – (3456 -246*14)*20
6= 246- 3456*20 +246*280
6= 246*281 -3456*20 This is it.
Multiply the whole thing by 39
6*39 =246*(281*39)-3456*(20*39)
234=246 *(10959)-3456*(780)
So one solution is 10959,780
We can now write the complete solution.
x= 10959 + t *(3456/6) so x=10959 +t * 576
y=780 - t*(246/6) so y=780-t*41 where t is any integer.
Depending upon whether x,y stand for pencils and erasers of forgetful Alice or Number of coins in my pocket you can enforce conditions like x>0 and y>0 and get a subset of above solution..(Yes here you end up with so many coins in your pocket. A pound has 100 pence and here each pence counts. Even one pence is valued. Wonder what happened to our own paisa)
Now I think if you see a LDE you can immediately write the solution just by looking at it. Let us hope we have better luck with Alice next time.
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.
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.
Linear Diophantine Equations
We start with Alice.(If you like you may think of her from Alice in Wonderland)
Supposing Alice went to market and bought a few pencils and a few erasers. Alice paid Rs 18 in all. Later she distributed all Pencils and Erasers she bought among her friends in Wonderland. Later back from Wonderland,very much in reality her mother demanded what did she do with 18 rupees she had. Now Alice had no clue how many pencils she bought and how many erasers, but she knew pencils cost 4 and erasers cost 2 and all 18 rupees she had were spent on them.
So for Alice and all such forgetful, dreamy people let us see how number theory can come to aid.
Let us assume she bought P pencils and E erasers.
Then we must have 4P+2E=18
Where P and E are integers .Problem is that we have just one equation and two unknowns P and E. However we have one more information that is P and E are integers.
If you look at form of equation you will immediately recall the Bezout equation which says
For two numbers a,b
We can write xa+yb =GCD(a,b)
And we have 4,2 here instead of a and b.
And P,E instead of x,y
So how do we go about it.
First of all note what we can write for 4 and 2
It is this x4+y2=GCD(4,2)=2
Or x4+y2=2
So if 2 doesn't divide 18 we cannot have a solution.
This is because in the end
x4+y2 =2 and P4+E2=18 are identical equations and we have just tweaked x and y by multiplying them with something to get P and E.
So P/x=E/y=18/2
If you recall linear equations in two variable for x,y
a1x+b1y=c1
and a2x+b2y=c2
if a1/a2=b1/b2 then solution is possible only if
a1/a2=b1/b2=c1/c2= k
And if a1/a2=b1/b2 not equal to c1/c2 then there is no solution.
What this means is that second equation is just first equation multiplied by some constant k.
So k(a1x+b1y=c1) gives a2x+b2y=c2.
And in terms of equation it means you are not going to get an INDEPENDENT equation by just multiplying the first with a constant.
So much for equations let us come to rescue Alice.
We write
x4+y2 =2
and P4+E2=18
Step 1 divide P4+E2=18 by GCD(4,2) i,e by 2
or P2+E=9
Now we obtain another equation P2+E1=9
we have another equation in terms of 2 and 1.
2 and 1 have gcd =1
So it is possible to write for some s,t s2+t1 =1 (bezout equation for 2 and 1)
By trial and error we get s=-1 and t=3.You can use Euclid's Algo as well.
So (-1)2 +(3)1=1
Multiply whole thing by 9.
And get (-9)2+(27)1=9 analogous to P2+E1=9
Again multiply by 2
(-9)4+(27)2=18 analogous to P4+E2=18
And this is the same equation we have been searching for.
and we can have on comparing coefficients P=-9 and E=27
But something is wrong Alice cannot buy negative number of pencils.
So what do we do now.
It turns out there is a neat trick in mathematics to handle this kind of problems.
Step 2
Supposing we take the equation
4-(2)2=0
We can add this equation any number of times to (-9)4+(27)2=18
without changing anything. Because adding zeros doesn't change anything.
Note the negative coefficient of 4. It is -9
So if we add 4 ten times we can make it positive.
So 10 * (4- (2)2)=0 gives
(10)4-(20)2=0
Adding this to original equation (-9)4+(27)2=18 gives
4+(7)2=18
or (1)4+(7)2=18
So finally we can conclude
Alice bought 1 pencil and 7 erasers.
But wait I found that adding 4-2(2)=0 doesn't change anything. So I can add any multiple of this to main equation and obtain another new solution.
In fact there are infinite number of solutions. But the fact that Alice must have bought positive number of erasers and pencils might save the day .Let us see
Supposing we add 11 times the 4-2(2)=0 to (-9)4+(27)2=18 we get (2)4+(5)2=18
And 13 times we get (3)4+(3)2=18
And 14 times we get (4)4+(1)2=18
Any further we will have pencils as negative.
So Alice is undone She might have bought . 1,7 or 2,5 or 3,3 or 4,1
pencils and erasers respectively.
So sorry Alice we cannot help you.
This class of equations
ax+by =c
is called Linear Diophantine Equation.
I just showed you how to solve one.
Supposing Alice went to market and bought a few pencils and a few erasers. Alice paid Rs 18 in all. Later she distributed all Pencils and Erasers she bought among her friends in Wonderland. Later back from Wonderland,very much in reality her mother demanded what did she do with 18 rupees she had. Now Alice had no clue how many pencils she bought and how many erasers, but she knew pencils cost 4 and erasers cost 2 and all 18 rupees she had were spent on them.
So for Alice and all such forgetful, dreamy people let us see how number theory can come to aid.
Let us assume she bought P pencils and E erasers.
Then we must have 4P+2E=18
Where P and E are integers .Problem is that we have just one equation and two unknowns P and E. However we have one more information that is P and E are integers.
If you look at form of equation you will immediately recall the Bezout equation which says
For two numbers a,b
We can write xa+yb =GCD(a,b)
And we have 4,2 here instead of a and b.
And P,E instead of x,y
So how do we go about it.
First of all note what we can write for 4 and 2
It is this x4+y2=GCD(4,2)=2
Or x4+y2=2
So if 2 doesn't divide 18 we cannot have a solution.
This is because in the end
x4+y2 =2 and P4+E2=18 are identical equations and we have just tweaked x and y by multiplying them with something to get P and E.
So P/x=E/y=18/2
If you recall linear equations in two variable for x,y
a1x+b1y=c1
and a2x+b2y=c2
if a1/a2=b1/b2 then solution is possible only if
a1/a2=b1/b2=c1/c2= k
And if a1/a2=b1/b2 not equal to c1/c2 then there is no solution.
What this means is that second equation is just first equation multiplied by some constant k.
So k(a1x+b1y=c1) gives a2x+b2y=c2.
And in terms of equation it means you are not going to get an INDEPENDENT equation by just multiplying the first with a constant.
So much for equations let us come to rescue Alice.
We write
x4+y2 =2
and P4+E2=18
Step 1 divide P4+E2=18 by GCD(4,2) i,e by 2
or P2+E=9
Now we obtain another equation P2+E1=9
we have another equation in terms of 2 and 1.
2 and 1 have gcd =1
So it is possible to write for some s,t s2+t1 =1 (bezout equation for 2 and 1)
By trial and error we get s=-1 and t=3.You can use Euclid's Algo as well.
So (-1)2 +(3)1=1
Multiply whole thing by 9.
And get (-9)2+(27)1=9 analogous to P2+E1=9
Again multiply by 2
(-9)4+(27)2=18 analogous to P4+E2=18
And this is the same equation we have been searching for.
and we can have on comparing coefficients P=-9 and E=27
But something is wrong Alice cannot buy negative number of pencils.
So what do we do now.
It turns out there is a neat trick in mathematics to handle this kind of problems.
Step 2
Supposing we take the equation
4-(2)2=0
We can add this equation any number of times to (-9)4+(27)2=18
without changing anything. Because adding zeros doesn't change anything.
Note the negative coefficient of 4. It is -9
So if we add 4 ten times we can make it positive.
So 10 * (4- (2)2)=0 gives
(10)4-(20)2=0
Adding this to original equation (-9)4+(27)2=18 gives
4+(7)2=18
or (1)4+(7)2=18
So finally we can conclude
Alice bought 1 pencil and 7 erasers.
But wait I found that adding 4-2(2)=0 doesn't change anything. So I can add any multiple of this to main equation and obtain another new solution.
In fact there are infinite number of solutions. But the fact that Alice must have bought positive number of erasers and pencils might save the day .Let us see
Supposing we add 11 times the 4-2(2)=0 to (-9)4+(27)2=18 we get (2)4+(5)2=18
And 13 times we get (3)4+(3)2=18
And 14 times we get (4)4+(1)2=18
Any further we will have pencils as negative.
So Alice is undone She might have bought . 1,7 or 2,5 or 3,3 or 4,1
pencils and erasers respectively.
So sorry Alice we cannot help you.
This class of equations
ax+by =c
is called Linear Diophantine Equation.
I just showed you how to solve one.
Euclid 's Algo
Today we start with Euclid's algorithm to find GCD.
You will appreciate that factoring large numbers can be really tedious.So it's good that we have a simple algorithm around to do the job for us.
All you need to understand is ordinary division process.
Say you have 2 numbers 45 AND 60
And you need to find GCD via Euclid's algorithm.
Note that if 45 divided 60 , then 45 would had been GCD.
GCD cannot be greater than smallest of two numbers.
Secondly if there's a number G which divides both of them then we could write
45=G*n1
60=G*n2
for some n1 and n2
then 60-45=G*n1-G*n2=G(n1-n2) So G divide the difference 60-45
The idea is that those numbers must be separated by some multiples of G on the number line.
- this gap has to be filled with Gs
-----------------------|------------------------------------------|-----------------
+++++++++++++++++45++++++++++++++++++++++++++++60+++++++++++++++
Or you can say by adding sufficient number of Gs you can get 60 from 45.
Now if you are looking for GCD that is the greatest of value of G that is possible then where do we start.
Obviously if we start with 60-45 i,e 15 that is the greatest possible value.
because with 15 we can fill the GAP in one go.Any other value has to be smaller than 15 or it's factor.
Infact 15 is the GCD here.As it divides both of them.
But I took a particularly simple case here.Just to illustrate how can we get GCD without factoring each number.
Let us move on to Euclid.
Supposing instead of 45 and 60
we have 30 and 165
Then obviously 165-30 = 135
135 cannot be the GCD so it must be a factor of 135 and it has to be smaller than or equal to 30
Yet again we can find a factor of 135 which is smaller than 30.And that factor is 15 and again we get the GCD as 15 as it divides both of them.
So we can have 30 =15*2
165=15*11
Notice one thing if we divide 165 by 30 we get
165=30*5+15
But 15 not only divides 30 and 165 but also 15 i,e the remainder left after dividing 165 by 30
This is very crucial result.If you recall I proved a result similar to this in my last mail.
What is happening is this
165 = 30 (mod GCD(165,30))
or 165 =30 (mod 15)..... both leave remainder 0 with the GCD
But we can add any multiple of 15 to either side without affecting equality.
So Addin 15*8 to RHS we get
165 = 30+15*8=150 (mod 15)
or 165-150=0 (mod 15)
or 15 =0 (mod 15)
Again notice 150 is the nearest multiple of 30 to 165.
So 15 divides 165,150,30 and as usual 15 which is the difference between 165 and 150 .
This difference is also the remainder left when 165 is divided by 30.
So in end we conclude GCD must divide the remainder when the smaller number divides the bigger.
Therefore GCD itself must be equal to the remainder or a factor of this number.
Here in this case GCD and the remainder turn out to be same but this is not the general case.It may be a factor of this remainder.But at any rate we can try this remainder to begin with.And at any rate GCD cannot be greater than this remainder.
Now we can write => GCD(30,165)= GCD(30,15)
This is because we 15 is the greatest GCD possible
And since any number which divides 30 and 165 must divide 15 and 30 as well
And which one is greatest ,we just saw it has to be 15.All others will be smaller than it i,e fatcors of 15.
So by finding GCD of 30 and 15 we can find GCD of 30 and 165.
Now we try to find GCD of 30 and 15
We do the same find the remainder on division of 30 by 15 and try it as GCD.
Here it turns out there is no remainder.
And so 15 must be the GCD.
i,e in essence is Euclid's algorithm.
Say we have two numbers. a,b with b less than a
Then we can write on division
a=bq1+r1 divide a by b
again
b=r1q2+r2 divide b by r1
r1=r2q3+r3 divide r1 by r2
r2=r3q4+r4 divide r2 by r3
.
.
.
rn-1=rn *qn finally rn by rn-1
And rn is the GCD.
At each stage we use the remainder to divide the divisor
in the hope that this remainder divides that divisor evenly and we get the GCD :-)
(Amazingly we don't do anything with quotient)
At each stage note that
GCD(a,b)=GCD(b,r1)=GCD(r1,r2)=GCD(r2,r3)
=GCD(rn-1,rn)=rn
At each stage we can start afresh with two numbers and try to find the GCD.
Yes we may get lost in all the remainders. But you get the idea right.
Let us see how to do it practically.
Say we want the GCD of (2261,1275)
Then we start as
1275 | 2261 | 1
-1275
---------------------------
986 |1275 | 1
- 986
----------------------------
289|986 |3
-867
-------------------------------
119 | 289 | 2
-238
---------------------------
51|119|2
- 102
----------------------------
17|51 |3
51
---------------------
0
So 17 is the GCD.
That is Euclid's Algorithm.Reamainder's bridging the Gaps.
One very famous theorem about GCD is this (Bezout's Theorem)
GCD(a,b) = x*a + y* b
For some integers x and y.
Note these integers may be positive or negative.
Now can you guess why this should be so.
And can you actually find a way to evaluate x and y.If you look at Euclid's algorithm and trace your way back from last remainder which is the GCD to the first equation you can find out why.
You will appreciate that factoring large numbers can be really tedious.So it's good that we have a simple algorithm around to do the job for us.
All you need to understand is ordinary division process.
Say you have 2 numbers 45 AND 60
And you need to find GCD via Euclid's algorithm.
Note that if 45 divided 60 , then 45 would had been GCD.
GCD cannot be greater than smallest of two numbers.
Secondly if there's a number G which divides both of them then we could write
45=G*n1
60=G*n2
for some n1 and n2
then 60-45=G*n1-G*n2=G(n1-n2) So G divide the difference 60-45
The idea is that those numbers must be separated by some multiples of G on the number line.
- this gap has to be filled with Gs
-----------------------|------------------------------------------|-----------------
+++++++++++++++++45++++++++++++++++++++++++++++60+++++++++++++++
Or you can say by adding sufficient number of Gs you can get 60 from 45.
Now if you are looking for GCD that is the greatest of value of G that is possible then where do we start.
Obviously if we start with 60-45 i,e 15 that is the greatest possible value.
because with 15 we can fill the GAP in one go.Any other value has to be smaller than 15 or it's factor.
Infact 15 is the GCD here.As it divides both of them.
But I took a particularly simple case here.Just to illustrate how can we get GCD without factoring each number.
Let us move on to Euclid.
Supposing instead of 45 and 60
we have 30 and 165
Then obviously 165-30 = 135
135 cannot be the GCD so it must be a factor of 135 and it has to be smaller than or equal to 30
Yet again we can find a factor of 135 which is smaller than 30.And that factor is 15 and again we get the GCD as 15 as it divides both of them.
So we can have 30 =15*2
165=15*11
Notice one thing if we divide 165 by 30 we get
165=30*5+15
But 15 not only divides 30 and 165 but also 15 i,e the remainder left after dividing 165 by 30
This is very crucial result.If you recall I proved a result similar to this in my last mail.
What is happening is this
165 = 30 (mod GCD(165,30))
or 165 =30 (mod 15)..... both leave remainder 0 with the GCD
But we can add any multiple of 15 to either side without affecting equality.
So Addin 15*8 to RHS we get
165 = 30+15*8=150 (mod 15)
or 165-150=0 (mod 15)
or 15 =0 (mod 15)
Again notice 150 is the nearest multiple of 30 to 165.
So 15 divides 165,150,30 and as usual 15 which is the difference between 165 and 150 .
This difference is also the remainder left when 165 is divided by 30.
So in end we conclude GCD must divide the remainder when the smaller number divides the bigger.
Therefore GCD itself must be equal to the remainder or a factor of this number.
Here in this case GCD and the remainder turn out to be same but this is not the general case.It may be a factor of this remainder.But at any rate we can try this remainder to begin with.And at any rate GCD cannot be greater than this remainder.
Now we can write => GCD(30,165)= GCD(30,15)
This is because we 15 is the greatest GCD possible
And since any number which divides 30 and 165 must divide 15 and 30 as well
And which one is greatest ,we just saw it has to be 15.All others will be smaller than it i,e fatcors of 15.
So by finding GCD of 30 and 15 we can find GCD of 30 and 165.
Now we try to find GCD of 30 and 15
We do the same find the remainder on division of 30 by 15 and try it as GCD.
Here it turns out there is no remainder.
And so 15 must be the GCD.
i,e in essence is Euclid's algorithm.
Say we have two numbers. a,b with b less than a
Then we can write on division
a=bq1+r1 divide a by b
again
b=r1q2+r2 divide b by r1
r1=r2q3+r3 divide r1 by r2
r2=r3q4+r4 divide r2 by r3
.
.
.
rn-1=rn *qn finally rn by rn-1
And rn is the GCD.
At each stage we use the remainder to divide the divisor
in the hope that this remainder divides that divisor evenly and we get the GCD :-)
(Amazingly we don't do anything with quotient)
At each stage note that
GCD(a,b)=GCD(b,r1)=GCD(r1,r2)=GCD(r2,r3)
=GCD(rn-1,rn)=rn
At each stage we can start afresh with two numbers and try to find the GCD.
Yes we may get lost in all the remainders. But you get the idea right.
Let us see how to do it practically.
Say we want the GCD of (2261,1275)
Then we start as
1275 | 2261 | 1
-1275
---------------------------
986 |1275 | 1
- 986
----------------------------
289|986 |3
-867
-------------------------------
119 | 289 | 2
-238
---------------------------
51|119|2
- 102
----------------------------
17|51 |3
51
---------------------
0
So 17 is the GCD.
That is Euclid's Algorithm.Reamainder's bridging the Gaps.
One very famous theorem about GCD is this (Bezout's Theorem)
GCD(a,b) = x*a + y* b
For some integers x and y.
Note these integers may be positive or negative.
Now can you guess why this should be so.
And can you actually find a way to evaluate x and y.If you look at Euclid's algorithm and trace your way back from last remainder which is the GCD to the first equation you can find out why.
Divisibility rules
Some say "God created integers and the rest is human creation"
So with this beautiful thought let me show you how divisibility rules are constructed.
Let us start with 3.
Since childhood we have been mugging like parrots "add all digits of number and if that is divisible by three than the whole number is divisible by 3"
Let us see where this rule comes from.
We all know this simple fact.
Every number can be expressed as sum of coefficients multiplied by powers of 10
Say 1236 =1*10^3 +2*10^2+3*10^1+6*10^0
Now we can also express this as coefficients multiplied by powers of 100 instead of 10
Say 1236 =12*100^1+36*10^0
Similarly we can try pwers of 1000
Say 1*1000^1+236*1000^0
and so on
Now let us come back.So if we need to operate on digits of number, instead of number as one whole uint, we need to represent them like this in any of the forms as above.
say we have a number 1236 we can write it as 1*10^3 +2*10^2+3*10^1+6*10^0
now let us write as before 1236=1*10^3 +2*10^2+3*10^1+6*10^0= something (mod 3)
but we know this something should be equal to 0 if we this is number is divisible by 3 .
So let us evaluate the LHS and see whether indeed this is the case.
now let us see we have powers of 10 in LHS.
and we know how to find modulo of powers.
we start with 10.
Now 10=1 (mod 3) as 10 leaves remainder 1 when divided by 3
again 10^2 =10*10 = 1*1 =1 (mod 3) replace each 10 by 1 that is substituting from eqation above
Similarly 10^3=1*1*1 =1(mod 3)
So any power of 10 leaves remainder 1 when divided by 3.
Now lets us get back to 1*10^3 +2*10^2+3*10^1+6*10^0= something (mod 3)
replace each of the powers by 1
1+2+3+6=12 (mod 3)
12=0(mod 3)
so that something is indeed 0 and this number can be divided by 3
now let us write this all formally
let us have a number abcde... of n digits
where abcde.. are digits of number
then it can be written as a*10^(n-1)+b*10^(n-2)+c*10(n-3) and so on
In mod 3 we can have each term a*1+b*1+c*1+...=a+b+c... (mod 3)
So if a+b+c+... =0 (mod 3) then this number is divisible by 3 right
Thus if sum of digits is divisible by 3 the whole number is divisible by 3
Now if I tell you 10= -1 (mod 11). then can you derive the famous divisibility rule for 11.
(yes 11 goes 1 times and remainder is -1 . 10=1*11-1
you can also note that 10=10 (mod 11) subtracting 11 from RHS gives the same result.
Note you can substract any multiple of 11 from either side without changing the equality
Think why , any way you can always do a-b and see whether it is divisible by mod number n and find whether equation is correct)
You need to proceed identically that is finding modulo of powers of 10 wrt 11 mod.
Now let us try some other numbers.
Say 9.
Now we again know that 10 =1 (mod 9)
Yes same as 3
So we can have 10=1 (mod 9)
or 10^2 = 1*1 (mod 9)
and similarly 10^3=1*1*1 (mod 9)=1 (mod 9)
So any power of 10 is 1 (mod 9)
Again any number of form abc.... can be written as a*10^n +b*10^(n-1) and so on
So we can write abc...=a*10^n +b*10^(n-1)+....=a+b+c... (mod 9)
So if a+b+c+... =0 (mod 9) then umber is divisible by 9
Same as 3.If sum of digits is divisible by 9 then whole number is divisible by 9.
Similarly let us try 11.
for 11
we know 10=-1 (mod 11)
So 10^2=(-1)*(-1) replacing each 10 with -1
So 10^2 =1
again 10^3 =(-1)(-1)(-1)=-1 (mod 11)
and so on odd powers return -1 and even powers of 10 gives 1
So for a number abcd...
We can have abcd.....=a^(n)+b^(n-1)+c^(n-2)+d^(n-3) ...=a-b+c-d+....(mod 11)
So all we need to do is sum the alternate terms together and take the difference if that is divisible by 11 the whole number is divisible by 11
Note it is not important which number we start with and which sum we subtarct from which.
All we need to do is form the sum with alternate digits.
Say we get a-b+c-d+...= something (mod 11)
We can easily multiply by -1.Remember the rule we can always multiply with a constant.
and get -a+b-c+d ..= -something (mod 11)
Again that 'something' may be neagtive positive doesn't matter it is just that 11 should divide it.
With that let us become a bit adventurous and try for other numbers
Now let us try so where do we start.
We just saw that it is very convenient if powers of 10 leave remaninder 1 or -1 with some number N.Say if N is 3,11,9 we were quick to formulate the rule.
But we have already tried numbers which divide 11 and 9.Actually 11 is prime so we can't do much with it.
So 3 divides 9 so we have a rule for it .
9 and 11 are as such by default.
Now let us try 999,1001 both of these will leave remainder 1 and -1 respectively.
And fortunately this time.
1001 has factor 1001 =7*13*11 check it.
As always we try to find modulo of powers of 1000 this time instead of 10.
So we can have
1000 = -1 (mod 7) as 1000 =143*7 -1
1000=-1 (mod 13) similarly
1000=-1 (mod 11)
so 1000 leaves remainde -1 for each.
So what is the rule.
Proceed similarly.
let us take a number abcdef= abc*(1000^1) +def*(1000^0)=abc(1000)+def*1
that is expanding in powers of 1000
so we have abc*(1000^1) +def*(1000^0)=abc(1000)+def*1=abc(-1)+def (mod 7 or 13 or 11)
=abc-def (mod 7 or 13 or 11)
So rule is--- form two groups of number taking three digits aleternately at a time beginning from right .
Sum and take the difference of these two groups.
If this diiference is divisible then you can be sure whole number is divisible.
Let us check it
Say let us try 123898768
form the group 123, 898 ,768
Take the sum and subtract (123+768)-(898)=-7
and -7 is divisible by 7 .(You can reverse it also and get 7 as result instead doesn't matter.)
So this number is divisible by 7 check it.
So we have one more test for 11
and we have test for 13 and 7
you can try for 33
as 100 =1 (mod 33)
and may be even higher powers of 10.
So with this beautiful thought let me show you how divisibility rules are constructed.
Let us start with 3.
Since childhood we have been mugging like parrots "add all digits of number and if that is divisible by three than the whole number is divisible by 3"
Let us see where this rule comes from.
We all know this simple fact.
Every number can be expressed as sum of coefficients multiplied by powers of 10
Say 1236 =1*10^3 +2*10^2+3*10^1+6*10^0
Now we can also express this as coefficients multiplied by powers of 100 instead of 10
Say 1236 =12*100^1+36*10^0
Similarly we can try pwers of 1000
Say 1*1000^1+236*1000^0
and so on
Now let us come back.So if we need to operate on digits of number, instead of number as one whole uint, we need to represent them like this in any of the forms as above.
say we have a number 1236 we can write it as 1*10^3 +2*10^2+3*10^1+6*10^0
now let us write as before 1236=1*10^3 +2*10^2+3*10^1+6*10^0= something (mod 3)
but we know this something should be equal to 0 if we this is number is divisible by 3 .
So let us evaluate the LHS and see whether indeed this is the case.
now let us see we have powers of 10 in LHS.
and we know how to find modulo of powers.
we start with 10.
Now 10=1 (mod 3) as 10 leaves remainder 1 when divided by 3
again 10^2 =10*10 = 1*1 =1 (mod 3) replace each 10 by 1 that is substituting from eqation above
Similarly 10^3=1*1*1 =1(mod 3)
So any power of 10 leaves remainder 1 when divided by 3.
Now lets us get back to 1*10^3 +2*10^2+3*10^1+6*10^0= something (mod 3)
replace each of the powers by 1
1+2+3+6=12 (mod 3)
12=0(mod 3)
so that something is indeed 0 and this number can be divided by 3
now let us write this all formally
let us have a number abcde... of n digits
where abcde.. are digits of number
then it can be written as a*10^(n-1)+b*10^(n-2)+c*10(n-3) and so on
In mod 3 we can have each term a*1+b*1+c*1+...=a+b+c... (mod 3)
So if a+b+c+... =0 (mod 3) then this number is divisible by 3 right
Thus if sum of digits is divisible by 3 the whole number is divisible by 3
Now if I tell you 10= -1 (mod 11). then can you derive the famous divisibility rule for 11.
(yes 11 goes 1 times and remainder is -1 . 10=1*11-1
you can also note that 10=10 (mod 11) subtracting 11 from RHS gives the same result.
Note you can substract any multiple of 11 from either side without changing the equality
Think why , any way you can always do a-b and see whether it is divisible by mod number n and find whether equation is correct)
You need to proceed identically that is finding modulo of powers of 10 wrt 11 mod.
Now let us try some other numbers.
Say 9.
Now we again know that 10 =1 (mod 9)
Yes same as 3
So we can have 10=1 (mod 9)
or 10^2 = 1*1 (mod 9)
and similarly 10^3=1*1*1 (mod 9)=1 (mod 9)
So any power of 10 is 1 (mod 9)
Again any number of form abc.... can be written as a*10^n +b*10^(n-1) and so on
So we can write abc...=a*10^n +b*10^(n-1)+....=a+b+c... (mod 9)
So if a+b+c+... =0 (mod 9) then umber is divisible by 9
Same as 3.If sum of digits is divisible by 9 then whole number is divisible by 9.
Similarly let us try 11.
for 11
we know 10=-1 (mod 11)
So 10^2=(-1)*(-1) replacing each 10 with -1
So 10^2 =1
again 10^3 =(-1)(-1)(-1)=-1 (mod 11)
and so on odd powers return -1 and even powers of 10 gives 1
So for a number abcd...
We can have abcd.....=a^(n)+b^(n-1)+c^(n-2)+d^(n-3) ...=a-b+c-d+....(mod 11)
So all we need to do is sum the alternate terms together and take the difference if that is divisible by 11 the whole number is divisible by 11
Note it is not important which number we start with and which sum we subtarct from which.
All we need to do is form the sum with alternate digits.
Say we get a-b+c-d+...= something (mod 11)
We can easily multiply by -1.Remember the rule we can always multiply with a constant.
and get -a+b-c+d ..= -something (mod 11)
Again that 'something' may be neagtive positive doesn't matter it is just that 11 should divide it.
With that let us become a bit adventurous and try for other numbers
Now let us try so where do we start.
We just saw that it is very convenient if powers of 10 leave remaninder 1 or -1 with some number N.Say if N is 3,11,9 we were quick to formulate the rule.
But we have already tried numbers which divide 11 and 9.Actually 11 is prime so we can't do much with it.
So 3 divides 9 so we have a rule for it .
9 and 11 are as such by default.
Now let us try 999,1001 both of these will leave remainder 1 and -1 respectively.
And fortunately this time.
1001 has factor 1001 =7*13*11 check it.
As always we try to find modulo of powers of 1000 this time instead of 10.
So we can have
1000 = -1 (mod 7) as 1000 =143*7 -1
1000=-1 (mod 13) similarly
1000=-1 (mod 11)
so 1000 leaves remainde -1 for each.
So what is the rule.
Proceed similarly.
let us take a number abcdef= abc*(1000^1) +def*(1000^0)=abc(1000)+def*1
that is expanding in powers of 1000
so we have abc*(1000^1) +def*(1000^0)=abc(1000)+def*1=abc(-1)+def (mod 7 or 13 or 11)
=abc-def (mod 7 or 13 or 11)
So rule is--- form two groups of number taking three digits aleternately at a time beginning from right .
Sum and take the difference of these two groups.
If this diiference is divisible then you can be sure whole number is divisible.
Let us check it
Say let us try 123898768
form the group 123, 898 ,768
Take the sum and subtract (123+768)-(898)=-7
and -7 is divisible by 7 .(You can reverse it also and get 7 as result instead doesn't matter.)
So this number is divisible by 7 check it.
So we have one more test for 11
and we have test for 13 and 7
you can try for 33
as 100 =1 (mod 33)
and may be even higher powers of 10.
Monday, July 16, 2007
A question
What is the remainder when 17^19 is divided by 9
We will use ^ for "raise to the power" through out.
Now by long didvision it will take some time and really it is hopeless.
Let us try this by modulo arithmetic.
Let us translate this in a equation
17^19 = something (mod 9)
Now this something and 17^19 leave same remainder on division by 9 so we try to find this something in lowest term possible.
As if we find this something we will also know what remainder 17^19 leaves on division by 9
Now let us get going
Let us say we start with 17
now 17 = x (mod 9)
Now x can take lots of values but we try to find the lowest one
we find that 17 = 8 (mod 9) .............................we wil need this later so let me mark this as (equation 1)
as 17 leaves 8 when divided 9
so we have 17=8 (mod 9)
Now let us try to find 17^2 = y (mod 9)
Now here the trick starts
i turns out you can write 17*17 =y (mod 9)
Now in modulo arithmetic you can substitute each of the 17 with a number that is equal to it.
Now we found 8=17 so we write it as
We merely write 8 for each 17
8*8 =y (mod 9)
64=y (mod 9)
now we know 64 = 1 (mod 9)
divide 64 by 9 and you get remainder 1 that's why.
Now we odn't need to go nay further
let s return to original equation 17^19 = something (mod 9)
Now 17^19 is just a row of 17's nineteen times.
Now we found 17=8 (mod 9)
and 17^2=1 (mod 9)
this means 17^4 =1 (mod 9) as 17^4=(17^2)*(17^2)
and we can substitute 1 for each of 17^2 .....right
Infact for any power of 2 we can have 17^(power of 2) =1 (mod 9) ....convince yourselves
Now try to substitute these two values in the original equation.
note that we can write 17^19 as (17^16)*(17^3)=(17^16)(17^2)(17)=(1)(1)(8)=8
So we have 17^19=8 (mod 9)
and 8 is the required remainder.
try to follow each step you can do it very quicly if you get the hang of it.
Let us see what I did once again.
17^(19)= some number (mod 9)
we try to RHS as small as possible
we found 17= 8 (mod 9)
17^2 =17*17 =8*8 (mod 9)
8*8 =64 =1 (mod 9)
so 17^2 =1 (mod 9)
Note that this mod 9 is really not necessary if it is understood what modulo we are working with so you can drop it.
similarly 17^4 =(17^2)*(17^2) =1*1 =1 (mod 9)
similarly 17^8=(17^4)(17^4)=1*1=1 (mod 9)
similarly 17^16 =1 (mod 9) and so on
17^19 =17^ 16 * 17^2 * 17 =1* 1 * 8 =8 (mod 9)
try some examples from printouts I gave you.
Now let us go to some more rules
I will state only two of them for now
if we have a=b (mod x)
and c=d (mod x)
then ac=bd (mod x) i,e you can multiply
and a+c=b+d (mod x) i,e you can add
for division you need to follow one rule i,e divisor must be relatively prime to the modulo
so a=b (mod x)=> a/k =b/k (mod x) provided k doesn't divide x.I will explain this why this happens.
Got it.
Now I can explain why we are able to substitute numbers by there equivalents.
say 17=8 (mod 9) ....1
17=8 (mod 9) ....2
So we can multiply these two identical equations to get 17*17 =8*8 (mod 9)
So when we have 17*17 we can always substitute it by 8*8 as both are equal
Similarly if you have 17+17 you can always substitute it by 8+8
So final conclusion you can substitute any number connected by multiplication or addition operators.
Got it...
We will use ^ for "raise to the power" through out.
Now by long didvision it will take some time and really it is hopeless.
Let us try this by modulo arithmetic.
Let us translate this in a equation
17^19 = something (mod 9)
Now this something and 17^19 leave same remainder on division by 9 so we try to find this something in lowest term possible.
As if we find this something we will also know what remainder 17^19 leaves on division by 9
Now let us get going
Let us say we start with 17
now 17 = x (mod 9)
Now x can take lots of values but we try to find the lowest one
we find that 17 = 8 (mod 9) .............................we wil need this later so let me mark this as (equation 1)
as 17 leaves 8 when divided 9
so we have 17=8 (mod 9)
Now let us try to find 17^2 = y (mod 9)
Now here the trick starts
i turns out you can write 17*17 =y (mod 9)
Now in modulo arithmetic you can substitute each of the 17 with a number that is equal to it.
Now we found 8=17 so we write it as
We merely write 8 for each 17
8*8 =y (mod 9)
64=y (mod 9)
now we know 64 = 1 (mod 9)
divide 64 by 9 and you get remainder 1 that's why.
Now we odn't need to go nay further
let s return to original equation 17^19 = something (mod 9)
Now 17^19 is just a row of 17's nineteen times.
Now we found 17=8 (mod 9)
and 17^2=1 (mod 9)
this means 17^4 =1 (mod 9) as 17^4=(17^2)*(17^2)
and we can substitute 1 for each of 17^2 .....right
Infact for any power of 2 we can have 17^(power of 2) =1 (mod 9) ....convince yourselves
Now try to substitute these two values in the original equation.
note that we can write 17^19 as (17^16)*(17^3)=(17^16)(17^2)(17)=(1)(1)(8)=8
So we have 17^19=8 (mod 9)
and 8 is the required remainder.
try to follow each step you can do it very quicly if you get the hang of it.
Let us see what I did once again.
17^(19)= some number (mod 9)
we try to RHS as small as possible
we found 17= 8 (mod 9)
17^2 =17*17 =8*8 (mod 9)
8*8 =64 =1 (mod 9)
so 17^2 =1 (mod 9)
Note that this mod 9 is really not necessary if it is understood what modulo we are working with so you can drop it.
similarly 17^4 =(17^2)*(17^2) =1*1 =1 (mod 9)
similarly 17^8=(17^4)(17^4)=1*1=1 (mod 9)
similarly 17^16 =1 (mod 9) and so on
17^19 =17^ 16 * 17^2 * 17 =1* 1 * 8 =8 (mod 9)
try some examples from printouts I gave you.
Now let us go to some more rules
I will state only two of them for now
if we have a=b (mod x)
and c=d (mod x)
then ac=bd (mod x) i,e you can multiply
and a+c=b+d (mod x) i,e you can add
for division you need to follow one rule i,e divisor must be relatively prime to the modulo
so a=b (mod x)=> a/k =b/k (mod x) provided k doesn't divide x.I will explain this why this happens.
Got it.
Now I can explain why we are able to substitute numbers by there equivalents.
say 17=8 (mod 9) ....1
17=8 (mod 9) ....2
So we can multiply these two identical equations to get 17*17 =8*8 (mod 9)
So when we have 17*17 we can always substitute it by 8*8 as both are equal
Similarly if you have 17+17 you can always substitute it by 8+8
So final conclusion you can substitute any number connected by multiplication or addition operators.
Got it...
Modulo Arithmetic
Number theroy starts with modulo arithmetic.
And why should we learn another kind of Arithmetic?
Wish I had an easy answer for that.Unless you are really gifted and you want to learn something of importance in theory of numbers you need to be familiar with modulo arithmetic.
So here we go....
As usual we write equations of form LHS =RHS
There's one crucial difference we always write these equations with reference to some number we call as 'modulo'
And to make it more expalanatory we write that number in bracket after the equation.
LHS=RHS (MOD N)
So we are doing arithmetic with respect to this number N we have decided to call as modulo.
Now rules of modulo equations are very simple and correspond to normal artihmetci we do.
we say that some number a=b (mod N)
if (a-b) is divisible by N
So difference of a and b be should be divisible by N
Stated equivalently a and b should leave same remainders when divided individually by N.
Say we have 5=8 (mod 3)
as 5 and 8 leave same remainder when divided by 3
or 8-5 =3 which is divisible by 3
Similarly 14=7 (mod 7)
2=4 (mod 2)
10=17 (mod 7)
10001=1(mod 1000)
One interesting thing is we can have negative numbers as well
Say 5= -3 ( mod 8)
as 5-(-3) =8 which is divisible by 8
Or if you divide 5 by 8 you get 5 as remainder .
if you divide -3 by 8 you get 5 as remainder
and 5= 8*(0)+5
as -3 = 8*(-1)+5
In first case 8 goes 0 times therefore quotient is 0 and remainder 5
and in second case 8 goes -1 times, yes negative quotients are also possible.
So in world of modulo arithmetic we are kind of always playing with remainders.
And it is incredibly powerful.
Can you think of few modulo equations and write them down ...
And why should we learn another kind of Arithmetic?
Wish I had an easy answer for that.Unless you are really gifted and you want to learn something of importance in theory of numbers you need to be familiar with modulo arithmetic.
So here we go....
As usual we write equations of form LHS =RHS
There's one crucial difference we always write these equations with reference to some number we call as 'modulo'
And to make it more expalanatory we write that number in bracket after the equation.
LHS=RHS (MOD N)
So we are doing arithmetic with respect to this number N we have decided to call as modulo.
Now rules of modulo equations are very simple and correspond to normal artihmetci we do.
we say that some number a=b (mod N)
if (a-b) is divisible by N
So difference of a and b be should be divisible by N
Stated equivalently a and b should leave same remainders when divided individually by N.
Say we have 5=8 (mod 3)
as 5 and 8 leave same remainder when divided by 3
or 8-5 =3 which is divisible by 3
Similarly 14=7 (mod 7)
2=4 (mod 2)
10=17 (mod 7)
10001=1(mod 1000)
One interesting thing is we can have negative numbers as well
Say 5= -3 ( mod 8)
as 5-(-3) =8 which is divisible by 8
Or if you divide 5 by 8 you get 5 as remainder .
if you divide -3 by 8 you get 5 as remainder
and 5= 8*(0)+5
as -3 = 8*(-1)+5
In first case 8 goes 0 times therefore quotient is 0 and remainder 5
and in second case 8 goes -1 times, yes negative quotients are also possible.
So in world of modulo arithmetic we are kind of always playing with remainders.
And it is incredibly powerful.
Can you think of few modulo equations and write them down ...
Subscribe to:
Posts (Atom)
