**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 r_{1} and when divided by 'b' leaves a
remainder r_{2}. (the premise for the chinese remainder theorem !)

From this we get :

N = xa + r_{1}

N = yb + r_{2}.

By equating the first equation with the second we get xa + r_{1} = yb + r_{2}
or ax - by = c for c = r_{2} - r_{1}.

__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 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 (

Thus, we get,

We have 18 * 1 - 10 = 8 * 1 . The 1 on the right hand side is the quotient.

Thus, we have

**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.