Find remainder when 13^400 is divided by 187.
I can only tell you the general solution.
I am note sure whether this is shortest or the best.
I have tried some trial and error in the end to arrive at solution fast but it looks unlikely to work in an exam.
First let me write the result I’ll use.
a^(p-1) = 1 (mod p)
provided a is not a multiple of p
or a and p don’t have a common factor
and p is a prime.
Say 5^(7-1) =1 (mod 7)
5^6 = 1 (mod 7)
Here 7 is the prime
And 5 is not a multiple of 7 and they don’t have a common factor as well
so the equation holds
A simple example is 7^(3-1) =1 (mod 3)
7^2 = 1 (mod 3)
Or 49 =1 (mod 3)
We know 49 will leave remainder 1 when divided by 3 so it holds.
Now let us get back to problem.
13^400
Let us forget 400 for the moment
we have to work with are 13 and 187
Unfortunately 187 is not a prime
187 =11*17
So we cannot say 13^186=1 (mod 187) …This would be incorrect
So we have to take recourse to similar theorem
It says a^(phi(n)) =1 (mod n)
Provided a is not a multiple of n
Or n and a don’t have a common factor.
Where phi(n) is Euler number of n.
Luckily 13 is not multiple of 187 neither they do have a common factor…..
Next step we write
13^(phi(187)) = 1 (mod 187)
All we have got to do is to find phi(187)
Now 187=11*17
Therefore phi(187)= 187(1-1/11)*(1-1/17)
= 187*10/11 *16/17 = 160
We can write
13^160 =1 (mod 187)
As 400=160*2+80
Therefore 13^400 = (13^320)*(13^80)
As 13^320=(13^160 )*(13^160) =1*1 =1
Therefore 13^400 = (13^320)*(13^80)= 1* (13^80)=13^80 (mod 187)
We have to work with 13^80
And we don’t have any magic bullets left so we try to start from scratch
Idea is to construct 80 as sum of powers of 2….
We have 13 =13 (mod 187)
13*13 =13^2 = 169 = -18 (mod 187)
Reduce 169 to -18 by subtracting 187
Now 13^4 = (13^2)*( 13^2)
Replace 13^2 by -18
13^4 = -18*-18 = 324 = 137 = -50 (mod 187)
Here we reduce 137 to -50 by subtracting 187 so that we get a smaller number to work with.
13^8 = (-50)*(-50) =2500 = 69 (mod 187)
13^16 =69*69= 4761 = 86 (mod 187)
Similarly we get
13^32 = 103 (mod 187)
13^64=137 (mod 187)
Since 80 = 64+16
13^80 = (13^64)*(13^16)= 137*86 = 11782 =1 (mod 187)
Answer is 1
However this is very lengthy process
Can we simplify it a bit….
We return to 13^160 =1 (mod 187)
There’s a very important theorem which might save the day
It says if there’s a smaller number say k
Such that 13^k = 1(mod 187)
Then k must divide 160
It is a general theorem it says if we have a^(phi(n)) =1
Then for any smaller number k if it holds
a^k = 1 (mod n)
Then k must divide phi(n)
We may try divisors of 160
Say we take 10 =8+2
So 13^10 = 13^8 * 13^2= 69* -18 = -1242 = 67
It is not 1
Let us try 20
13^20=13^10 * 13^10 = 67*67=4489 =1 (mod 187)
It works
So it follows any power which is multiple of 20 will leave remainder 1
Therefore 13^400 =1 (mod 187)
Now let us return to
if we have a^(phi(n)) =1
Then for any smaller number k if it holds
a^k = 1 (mod n)
Then k must divide phi(n)
Why do you think this works
We have to return to group theory.
All numbers relatively prime to 187 and smaller than it form a group…
And order of group is phi(187)
I,e phi(187) elements are present in group.
Lagrange theorem says that if there’s subgroup of this group
Then order of subgroup must divide order of the original group.
Now if we have k
a^k = 1 (mod n)
Then a k order group exist which os sub group of the original phi(n) order subgroup.
k is also called multiplicative order of a mod n
k is minimum number for which a^k =1 (mod n) holds
Monday, February 9, 2009
A question of Counting
I am indebted to my friend Shekhar for helping me generate material for this blog.
How many 6-digit number contain exactly 4 different digits?
Solution.
In Short
10C4*4C2* 6!/(2! 2!) + 10C4 * 4C1 * 6!/(3!) - 1/10*(10C4*4C2* 6!/(2! 2!) + 10C4 * 4C1 * 6!/(3!))
=226800+100800-1/10(226800+100800)= 294840
The Detailed solution is as following
Start by picking
any four distinct digits from 0,1,2,3,4,5,6,7,8,9
Note I included 0
This can be done in 10C4 ways
Of these 4 digits I can choose 2 digits that will occur twice in the final number
Say I chose 1 2 3 4
then I can choose any two of them which will occur twice
say a number of form 1 2 3 4 3 2
Where in 3 and 2 repeat once each
Total ways in such a selection can be made is
10C4* 10C2
now suppsing I have 1 2 3 4 and I have 3 2 that will occur in duplicates
I can form any permutaion of them to get a new number
So total number of ways will be
number of selection multiplied by possible arrangements
which is just permutaion of 6 things where 2 things occur more than once
that is 6! (2! 2!)
gives me a total of
6! (2! 2!) * 10C4* 10C2
Is that all
No we can have a case wherein a digit is triplicate instead of two duplicates
again same rule applies
I choose 4 distinct digits in 10 C 4 ways
Then I choose one digit from these chosen 4 numbers which will occur thrice in 4C1 ways
total of
10C4*4C1 ways
and total number of numbers such formed as
10C4*4C1 * 6!/(3!)
Howver that is not all
I need to subtract cases where in 0 occurs as first digit
Howvere a 0 will be the first digit in one tenth of cases
This is becuase first place will be occupied by 1,2,3,4,6 etc equal number of times
So I subtract 1/10 of the sum of above two cases
which gives me the final result
How many 6-digit number contain exactly 4 different digits?
Solution.
In Short
10C4*4C2* 6!/(2! 2!) + 10C4 * 4C1 * 6!/(3!) - 1/10*(10C4*4C2* 6!/(2! 2!) + 10C4 * 4C1 * 6!/(3!))
=226800+100800-1/10(226800+100800)= 294840
The Detailed solution is as following
Start by picking
any four distinct digits from 0,1,2,3,4,5,6,7,8,9
Note I included 0
This can be done in 10C4 ways
Of these 4 digits I can choose 2 digits that will occur twice in the final number
Say I chose 1 2 3 4
then I can choose any two of them which will occur twice
say a number of form 1 2 3 4 3 2
Where in 3 and 2 repeat once each
Total ways in such a selection can be made is
10C4* 10C2
now suppsing I have 1 2 3 4 and I have 3 2 that will occur in duplicates
I can form any permutaion of them to get a new number
So total number of ways will be
number of selection multiplied by possible arrangements
which is just permutaion of 6 things where 2 things occur more than once
that is 6! (2! 2!)
gives me a total of
6! (2! 2!) * 10C4* 10C2
Is that all
No we can have a case wherein a digit is triplicate instead of two duplicates
again same rule applies
I choose 4 distinct digits in 10 C 4 ways
Then I choose one digit from these chosen 4 numbers which will occur thrice in 4C1 ways
total of
10C4*4C1 ways
and total number of numbers such formed as
10C4*4C1 * 6!/(3!)
Howver that is not all
I need to subtract cases where in 0 occurs as first digit
Howvere a 0 will be the first digit in one tenth of cases
This is becuase first place will be occupied by 1,2,3,4,6 etc equal number of times
So I subtract 1/10 of the sum of above two cases
which gives me the final result
A Distribution Problem
A Question sent to me by my dear friend
1. Six white and six black balls of the same size are distributed among ten urns so that there is at least one ball in each urn.
What is the number of different distributions of the balls?
The solution in short is
2*10C6 - (10C6 * 6C2) + (10C6* 10C1)*2+ (10C5*5C1)*5C1=18900-3150+4200+6300
=26250
The details are as following
First of all note this very follwoing important point.
Whenever I distribute the balls
Every case I consider should be completely disjoint
That is my cases should never oeverlap
It will get clearer as I proceed
Supposing I label the 10 urns as 1,2,3,4,5,6,7,8,9,10.
Observation one : Urns are distinguishable
I have 6 red and 6 black balls
Observation two : 6 blacks are not distinguishable among themselves
6 whites are not ditinguishable among themselves
The aim is to distribute the balls so as each distibution which
we count has to be different in some sense
1) Each Urn has a different number of balls
2) if the urn has same number of balls, for each urn in two different distributions , then colour of a ball must be different for at least one urn
Say number of balls in a distribution D1 and D2 urn
is such that 1,2,3,4,5,6,7,8,9,10 have exactly equal number of balls then
at least one of the urns must have ball of different colour
only then I can call D1 and D2 as different and count them.
Let us proceed
Supposing I distribute this way
Case 1
I choose ANY 6 urns then I fill them with black balls.
I get 6 filled and 4 empty
I fill the 4 remaining empty urns with 4 RED balls
So I have 2 RED balls left
I choose any 2 of the 10 urns each having a single red or black ball and place the remaining 2 red balls
I get for this
10C6 that is choosing 6 urns out of 10
4 urns are always empty I need not choose them.
But the 2 urns for remaining 2 Red Balls can be chosen in 10C2 ways
So I get for whole process
10C6*10C2
Now I started out with balck balls
What if I started out with RED balls.
I proceed identically and choose 6 urns for RED and then distribute the rest of 2 blacks among any 2 of 10 urns.
So I get 2* (10C6*10C2) for red and balck for 6 and 2 kind of distribution
But wait
Supposing I distributed 6 red in urns 1,2,3,4,5,6
And 4 blacks in 7,8,9,10
I have 2 blacks supposing I put them in urns 5,6
problem is that this kind of distribution was possible from other way around as well that is
I distribute 6 Black balls in urns 5,6,7,8,9,10
4 reds in 1,2,3,4 and remaining 2 reds I put in 5,6
There's a double counting I need to elimiante
the problem only occurs if I put remaining last two balls in urns containing ball of a different colour.
So I subtract
10C6*6C2 to eliminate double counting
because after I put 4 balls in urns of a particular colour the last two balls can be put in urn containing balls of different colur in 6C2 ways
Case 2
I put 6 red balls in any 6 urns
then 4 black in remaining 4 empty urns
and remining 2 black balls together in any of the 10 urns having 1 ball of any colour
this can be done in 10C6*10C1 ways
And since I can start with black instead of red I multiply by 2
to get
(10C6* 10C1)*2
there will be no double counting you can convince yourself.
Case 3
I choose 5 red balls and put them in any urns
Then I choose 5 black balls and put them in rest of 5 empty urns
Then I choose 1 remaining red ball and place it in urn having red ball
Then I choose 1 remaining black ball and place it in urn having black ball
that is red goes to red and black goes to black
5 black can be chosen 10C5 ways
rest 5 are automatically chosen I don't need to choose again for red
the one remaining black can be put in any of 5 urns containg black in 5C1 ways
and 1 remaing red can be put in any urn contain red in 5C1 ways
I get in total (10C5*5C1)*5C1
Finally
I add all of them
The point is that all of the distributions in Case 1,2,3 should be totally exclusive to any other
There cannot be way that a distribution belonging to Case 1 can be found in Case 2 or Case 3
Second point is case 1,2,3 exhaust all possible scenarios
There's no distribution possible which does not belong to any one of the cases
These two points should crack most of the tough problems
The difficult part is forming the cases.
1. Six white and six black balls of the same size are distributed among ten urns so that there is at least one ball in each urn.
What is the number of different distributions of the balls?
The solution in short is
2*10C6 - (10C6 * 6C2) + (10C6* 10C1)*2+ (10C5*5C1)*5C1=18900-3150+4200+6300
=26250
The details are as following
First of all note this very follwoing important point.
Whenever I distribute the balls
Every case I consider should be completely disjoint
That is my cases should never oeverlap
It will get clearer as I proceed
Supposing I label the 10 urns as 1,2,3,4,5,6,7,8,9,10.
Observation one : Urns are distinguishable
I have 6 red and 6 black balls
Observation two : 6 blacks are not distinguishable among themselves
6 whites are not ditinguishable among themselves
The aim is to distribute the balls so as each distibution which
we count has to be different in some sense
1) Each Urn has a different number of balls
2) if the urn has same number of balls, for each urn in two different distributions , then colour of a ball must be different for at least one urn
Say number of balls in a distribution D1 and D2 urn
is such that 1,2,3,4,5,6,7,8,9,10 have exactly equal number of balls then
at least one of the urns must have ball of different colour
only then I can call D1 and D2 as different and count them.
Let us proceed
Supposing I distribute this way
Case 1
I choose ANY 6 urns then I fill them with black balls.
I get 6 filled and 4 empty
I fill the 4 remaining empty urns with 4 RED balls
So I have 2 RED balls left
I choose any 2 of the 10 urns each having a single red or black ball and place the remaining 2 red balls
I get for this
10C6 that is choosing 6 urns out of 10
4 urns are always empty I need not choose them.
But the 2 urns for remaining 2 Red Balls can be chosen in 10C2 ways
So I get for whole process
10C6*10C2
Now I started out with balck balls
What if I started out with RED balls.
I proceed identically and choose 6 urns for RED and then distribute the rest of 2 blacks among any 2 of 10 urns.
So I get 2* (10C6*10C2) for red and balck for 6 and 2 kind of distribution
But wait
Supposing I distributed 6 red in urns 1,2,3,4,5,6
And 4 blacks in 7,8,9,10
I have 2 blacks supposing I put them in urns 5,6
problem is that this kind of distribution was possible from other way around as well that is
I distribute 6 Black balls in urns 5,6,7,8,9,10
4 reds in 1,2,3,4 and remaining 2 reds I put in 5,6
There's a double counting I need to elimiante
the problem only occurs if I put remaining last two balls in urns containing ball of a different colour.
So I subtract
10C6*6C2 to eliminate double counting
because after I put 4 balls in urns of a particular colour the last two balls can be put in urn containing balls of different colur in 6C2 ways
Case 2
I put 6 red balls in any 6 urns
then 4 black in remaining 4 empty urns
and remining 2 black balls together in any of the 10 urns having 1 ball of any colour
this can be done in 10C6*10C1 ways
And since I can start with black instead of red I multiply by 2
to get
(10C6* 10C1)*2
there will be no double counting you can convince yourself.
Case 3
I choose 5 red balls and put them in any urns
Then I choose 5 black balls and put them in rest of 5 empty urns
Then I choose 1 remaining red ball and place it in urn having red ball
Then I choose 1 remaining black ball and place it in urn having black ball
that is red goes to red and black goes to black
5 black can be chosen 10C5 ways
rest 5 are automatically chosen I don't need to choose again for red
the one remaining black can be put in any of 5 urns containg black in 5C1 ways
and 1 remaing red can be put in any urn contain red in 5C1 ways
I get in total (10C5*5C1)*5C1
Finally
I add all of them
The point is that all of the distributions in Case 1,2,3 should be totally exclusive to any other
There cannot be way that a distribution belonging to Case 1 can be found in Case 2 or Case 3
Second point is case 1,2,3 exhaust all possible scenarios
There's no distribution possible which does not belong to any one of the cases
These two points should crack most of the tough problems
The difficult part is forming the cases.
Sunday, August 26, 2007
Fermat's Little Theorem
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.
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.
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.
Subscribe to:
Posts (Atom)
