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.

 137=60*2+17 60=17*3+9 17=9*1+8    9=8*1+1 2 3 1 1 17 9 8 (LBR) 1 (LR) Table 1 Q R

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.