Shortcut for Finding Integral Solution of an Equation
Many a times we need to find out the integral solutions of a linear equation. Lets find out how to do it. (I will also tell you a shortcut for the same)
Consider a linear equation ax + by = c
The first and the foremost condition for any linear equation to have integral solution is that the constant term must be a multiple of the HCF of coefficients of x and y. In other words c should be a multiple of HCF (a, b). If this condition is satisfied only then, integral solution of the equation are possible. For example if the equation is:
4x + 6y = 12. In this case HCF (4,6) = 2 and 12 is a multiple of 2. Hence the above equation has some integral solutions. In 5x + 9y = 29, here HCF (5,9) = 1, and obviously 29 is a multiple of 1 (in fact any number is), hence the above equation has integer solution.
The next step is to find out these solutions. I will explain this to you using an example. Consider an equation
79x + 23y = 11019. HCF (79,23) = 1 which divides 11019. No problems here.
Now we write 79 as a factor of 23 like this: 79 = 3 * 23 + 10
Then we continue this till we get 0 as the remainder. The next step would be: 23 = 2 * 10 + 3
Then 10 = 3 * 3 + 1
3 = 3 * 1 + 0. So, we stop here.
Now the next step is to write this in reverse:
hence 1 can be written as:
1 = 10-3 * 3
= 10-3 * (23-2 * 10)
= 7 * 10-3 * 23
= 7 * (79-3 * 23) – 3 * 23
= 7 * 79-24 * 23
Now look back at our original equation 79x + 23y = 11019. Since 1 = 79 * (7) + 23 * (- 24). Hence, (7, -24) satisfies the equation 79x + 23y = 1, and hence (7 * 10019, -24 * 11019) satisfies 79x + 23y = 11019. So we get an integral solution (77133, -264456). Now there may be other such solutions as well. The general equation of such points is given by:
x = x1 + (b / d) * t
y = y1 – (a / d) * t
Here, x1 and y1 are 1 integer solution which have just found out. d is the HCF (a, b). And putting t = 0,1,2,3 ……. or -1, -2, -3, -4, -5, -6 ………. will give us the entire set of such integral points.
Hence for our equation it becomes x = 77133 + 23 * t and y = -264456 – 79 * t
Now, its quite obvious that there are infinite such solutions. Sometimes we have to just find out the positive integral solutions. it can be done as: x1 + (b / d) * t> = 0 and y1 – (a / d) * t> = 0. In our case doing this will get us:
t <= – 3348 and t> = -3353. Hence number of positive integral solutions = 3353-3348 + 1 = 6.
Now, there is a shorcut for finding out the number of positive integer solution.
number of positive integral solutions = (c * HCF (a, b)) / (a * b)
Of course you have to check first whether c is a multiple of HCF (a, b)
Note: the number which will come out will be fraction most of the times. You have to round it off to get the answer. And this trick is an approximation. Although you will get the right answer 99.99% of the times, remember to add 1 when the answer is not a fraction but a perfect integer.