Kuṭṭaka is an algorithm for finding integer solutions of linear Diophantine equations. A linear Diophantine equation is an equation of the form ax + by = c where x and y are unknown quantities and a, b, and c are known quantities with integer values. 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. It was Bhāskara I (c. 600 – c. 680) who gave a detailed description of the algorithm with several examples from astronomy in his Āryabhatiyabhāṣya, who gave the algorithm the name Kuṭṭaka. In Sanskrit, the word Kuṭṭaka means pulverization (reducing to powder), and it indicates the nature of the algorithm. The algorithm in essence is a process where the coefficients in a given linear Diophantine equation are broken up into smaller numbers to get a linear Diophantine equation with smaller coefficients. In general, it is easy to find integer solutions of linear Diophantine equations with small coefficients. From a solution to the reduced equation, a solution to the original equation can be determined. Many Indian mathematicians after Aryabhaṭa have discussed the Kuṭṭaka method with variations and refinements. The Kuṭṭaka method was considered to be so important that the entire subject of algebra used to be called Kuṭṭaka-ganita or simply Kuṭṭaka. Sometimes the subject of solving linear Diophantine equations is also called Kuṭṭaka.

In literature, there are several other names for the Kuṭṭaka algorithm like Kuṭṭa, Kuṭṭakāra and Kuṭṭikāra. There is also a treatise devoted exclusively to a discussion of Kuṭṭaka. Such specialized treatises are very rare in the mathematical literature of ancient India.^[1] The treatise written in Sanskrit is titled Kuṭṭākāra Śirōmaṇi and is authored by one Devaraja.^[2]

The Kuṭṭaka algorithm has much similarity with and can be considered as a precursor of the modern day extended Euclidean algorithm. The latter algorithm is a procedure for finding integers x and y satisfying the condition ax + by = gcd(a, b).^[3]

The problem that can supposedly be solved by the Kuṭṭaka method was not formulated by Aryabhaṭa as a problem of solving the linear Diophantine equation. Aryabhaṭa considered the following problems all of which are equivalent to the problem of solving the linear Diophantine equation:

• Find an integer which when divided by two given integers leaves two given remainders. This problem may be formulated in two different ways:

• Let the integer to be found be N, the divisors be a and b, and the remainders be R₁ and R₂. Then the problem is to find N such that

N ≡ R₁ (mod a) and N ≡ R₂ (mod b).

• Letting the integer to be found to be N, the divisors be a and b, and the remainders be R₁ and R₂, the problem is to find N such that there are integers x and y such that

N = ax + R₁ and N = by + R₂.

This is equivalent to

ax − by = c where c = R₂ − R₁.

• Find an integer such that its product with a given integer being increased or decreased by another given integer and then divided by a third integer leaves no remainder. Letting the integer to be determined be x and the three integers be a, b and c, the problem is to find x such that (ax ± b)/c is an integer y. This is equivalent to finding integers x and y such that

(ax ± b)/c = y.

This in turn is equivalent to the problem of finding integer solutions of ax ± by = ±c.

Aryabhata and other Indian writers had noted the following property of linear Diophantine equations: "The linear Diophantine equation ax + by = c has a solution if and only if gcd(a, b) is a divisor of c." So the first stage in the pulverization process is to cancel out the common factor gcd(a, b) from a, b and c, and obtain an equation with smaller coefficients in which the coefficients of x and y are relatively prime.

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. The operation of the pulveriser should be considered in relation to them."^[1]

Aryabhata gave the algorithm for solving the linear Diophantine equation in verses 32–33 of Ganitapada of Aryabhatiya.^[1] Taking Bhāskara I's explanation of these verses also into consideration, Bibhutibbhushan Datta has given the following translation of these verses:

"Divide the divisor corresponding to the greater remainder by the divisor corresponding to the smaller remainder. The residue (and the divisor corresponding to the smaller remainder) being mutually divided (until the remainder becomes zero), the last quotient should be multiplied by an optional integer and then added (in case the number of quotients of the mutual division is even) or subtracted (in case the number of quotients is odd) by the difference of the remainders. (Place the other quotients of the mutual division successively one below the other in a column; below them the result just obtained and underneath it the optional integer.) Any number below (that is, the penultimate) is multiplied by the one just above it and added by that just below it. Divide the last number (obtained so doing repeatedly) by the divisor corresponding to the smaller remainder; then multiply the residue by the divisor corresponding to the greater remainder and add the greater remainder. (The result will be) the number corresponding to the two divisors."

Some comments are in order.

• The algorithm yields the smallest positive integer which gives specified remainders when divided by given numbers.
• The validity of the algorithm can be established by translating the process into modern mathematical notations.^[1]
• Subsequent Indian mathematicians including Brahmagupta (628 AD), Mahavira (850), Aryabhata II (950), Sripati (1039), Bhāskara II (1150) and Narayana (1350) have developed several variants of this algorithm and have also discussed several special cases of the algorithm.^[1]

Without loss of generality, let ax-by=c be our Diophantine equation where a, b are positive integers and c is an integer. Divide both sides of the equation by gcd(a,b). If c is not divisible by gcd(a,b) then there are no integer solutions to this equation. After the division, we get the equation a'x-b'y=c'. The solution to this equation is the solution to ax-by=c. Without loss of generality, let us consider a > b.

Using Euclidean division, follow these recursive steps:
a' = a₁b' + r₁
b' = a₂r₁ + r₂
r₁ = a₃r₂ + r₃
…
r_n-2 = a_nr_n-1 + 1. Where r_n = 1.

Now, define quantities x_x+2, x_n+1, x_n,.. by backward induction as follows:
If n is odd, take x_n+2 = 0 and x_n+1 = 1.
If n is even, take x_n+2=1 and x_n+1=r_n-1-1.
Now,calculate all x_m (n≥m≥1) by x_m=a_mx_m+1+x_m+2. Then y = c'x₁ and x = c'x₂.

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]