Kuṭṭaka

Kuṭṭaka is an algorithm for finding integer solutions of linear Diophantine equations.

The algorithm was originally invented by the Indian astronomer-mathematician Āryabhaṭa (476–550 CE) and is described very briefly in his Āryabhaṭīya.

Āryabhaṭa did not give the algorithm the name Kuṭṭaka, and his description of the method was mostly obscure and incomprehensible.

In Sanskrit, the word Kuṭṭaka means pulverization (reducing to powder), and it indicates the nature of the algorithm.

In general, it is easy to find integer solutions of linear Diophantine equations with small coefficients.

Many Indian mathematicians after Aryabhaṭa have discussed the Kuṭṭaka method with variations and refinements.

[1] The treatise written in Sanskrit is titled Kuṭṭākāra Śirōmaṇi and is authored by one Devaraja.

The latter algorithm is a procedure for finding integers x and y satisfying the condition ax + by = gcd(a, b).

For example, Bhāskara I observes: "The dividend and the divisor shall become prime to each other, on being divided by the residue of their mutual division.

"[1] Aryabhata gave the algorithm for solving the linear Diophantine equation in verses 32–33 of Ganitapada of Aryabhatiya.

The following example taken from Laghubhāskarīya of Bhāskara I[4] illustrates how the Kuttaka algorithm was used in the astronomical calculations in India.

[5] The sum, the difference and the product increased by unity, of the residues of the revolutions of Saturn and Mars – each is a perfect square.

Taking the equations furnished by the above and applying the methods of such quadratics obtain the (simplest) solution by the substitution of 2, 3, etc.

Then calculate the ahargana and the revolutions performed by Saturn and Mars in that time together with the number of solar years elapsed.

In the Indian astronomical tradition, a Yuga is a period consisting of 1,577,917,500 civil days.

Let x and y denote the residues of the revolutions of Saturn and Mars respectively satisfying the conditions stated in the problem.