Aryabhatta's Kuttaka method :
The word 'kuttaka' means pulveriser(which means reducer). This method was developed by Aryabhatta in the 5th century to solve indeterminate equations of the form ax - by = c.
Meaning of the equation :
It is required to determine an integer N which when
divided by 'a' leaves a remainder r1 and when divided by 'b' leaves a
remainder r2. (the premise for the chinese remainder theorem !)
From this we get :
N = xa + r1
N = yb + r2.
By equating the first equation with the second we get xa + r1 = yb + r2 or ax - by = c for c = r2 - r1.
The method :
Aryabhata noted that any factor common to a and b
should be a factor of c (This is what the chinese remainder theorem states ! Amazing how
people can think the same way !), otherwise the equation has no solution. Dividing a, b
and c by the greatest common factor of (a,b) we can reduce the equation to the form where
a and b have no common factor except for 1.
Consider the example :
137x + 10 = 60y
Express the larger of the coefficients(in this case 137 > 60, so choose 137) as product of
the smaller coefficient( i.e 60). Continue doing this, now taking 60 as the larger coefficient and so on. Hence, we get Table 1.
From this we can form the column of quotients (Column Q
of Table 1) and the column of remainders (Column R of Table 1).
The number of quotients (except the first one of column Q) is odd.
Now, we have to find a number called the multiplier (call it z) such that
z * LR - 10 = LBR * m
Here, 10 is the constant in the equation to be solved (137x+10=60y) and m is any integer.
Thus, we get, z * 1 - 10 = 8 * m.
We have 18 * 1 - 10 = 8 * 1 . The 1 on the right hand side is the quotient.
Thus, we have z = 18 and m = 1 for the equation 137x + 10 = 60y.
In the above case, 10 is subtracted because the number of quotients is odd.
If the number quotients is even, the constant of the equation has to be added.
Now, a table has to be formed and the solution can be
read off from it.
How do we form the table ? Click here to find out.