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:
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 divisorofc." 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:
Some comments are in order.
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' = a1b' + r1
b' = a2r1 + r2
r1 = a3r2 + r3
…
rn-2 = anrn-1 + 1. Where rn = 1.
Now, define quantities xx+2, xn+1, xn,.. by backward induction as follows:
Ifn is odd, take xn+2 = 0 and xn+1 = 1.
Ifn is even, take xn+2=1 and xn+1=rn-1-1.
Now,calculate all xm (n≥m≥1)byxm=amxm+1+xm+2. Then y = c'x1 and x = c'x2.
Consider the following problem:
Remainders = 15, 19
Greater remainder = 19
Divisor corresponding to greater remainder = 45
Smaller remainder = 15
Divisor corresponding to smaller remainder = 29
Difference of remainders = 19 - 15 = 4
Divide 45 by 29 to get quotient 1 and remainder 16: 29 ) 45 ( 1
29
----
Divide 29 by 16 to get quotient 1 and remainder 13: 16 ) 29 ( 1
16
----
Divide 16 by 13 to get quotient 1 and remainder 3: 13 ) 16 ( 1
13
----
Divide 13 by 3 to get quotient 4 and remainder 1: 3 ) 13 ( 4
3
----
Divide 3 by 1 to get quotient 3 and remainder 0: 1 ) 3 ( 3
1
----
The process of mutual division stops here. 0
Quotients = 1, 1, 1, 4, 3
Number of quotients = 4 (an even integer)
(excluding the first quotient)
Choose an optional integer = 2 (= k)
The last quotient = 3
Multiply the optional integer by last quotient = 2 × 3 = 6
Add the above product to difference of remainders = 6 + 4 = 10 (= 3 × k + 4)
Write elements of 1st column : 1, 1, 4, 3, 2, 4 (contains 4 quotients)
Compute elements of 2nd column : 1, 1, 4, 10, 2 (contains 3 quotients)
Compute elements of 3rd column : 1, 1, 42, 10 (contains 2 quotients)
Compute elements of 4th column : 1, 52, 42 (contains 1 quotient)
Compute elements of 5th column : 94, 52 (contains no quotients)
The computational procedure is shown below:
Quotient 1 : 1 1 1 1 94
↗
Quotient 2 : 1 1 1 52 (52×1 + 42 = 94) 52
↗
Quotient 3 : 4 4 42 (42×1 + 10 =52) 42
↗
Quotient 4 : 3 10 (10×4 + 2 = 42) 10
↗
k : 2 (2×3 + 4 = 10) 2
Difference : 4
of remainders
The last number obtained = 94
The residue when 94 is divided by the divisor corresponding to smaller remainder = 7
Multiply this residue by the divisor corresponding to larger remainder = 7 × 45 = 315
Add the larger remainder = 315 + 19 = 334
The required number is 334.
334 = 11 × 29 + 15. So, 334 leaves a remainder of 15 when divided by 29.
334 = 7 × 45 + 19. So, 334 leaves a remainder of 19 when divided by 45.
The number 334 is the smallest integer which leaves remainders 15 and 19 when divided by 29 and 45 respectively.
The following example taken from LaghubhāskarīyaofBhā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. successively (in the general solution). 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. Saturn makes 146,564 revolutions and Mars makes 229,6824 revolutions in a Yuga. So Saturn makes 146,564/1,577,917,500 = 36,641/394,479,375 revolutions in a day. By saying that the residue of the revolution of Saturn is x, what is meant is that the fractional number of revolutions is x/394,479,375. Similarly, Mars makes 229,6824/1,577,917,500 = 190,412/131,493,125 revolutions in a day. By saying that the residue of the revolution of Mars is y, what is meant is that the fractional number of revolutions is y/131,493,125.
Let x and y denote the residues of the revolutions of Saturn and Mars respectively satisfying the conditions stated in the problem. They must be such that each of x + y. x − y and xy + 1 is a perfect square.
Setting
one obtains
and so
For xy + 1 also to be a perfect square we must have
Thus the following general solution is obtained:
The value q = 2 yields the special solution x = 40, y = 24.
Ahargana is the number of days elapsed since the beginning of the Yuga.
Let u be the value of the ahargana corresponding the residue 24 for Saturn. During u days, saturn would have completed (36,641/394,479,375)×u number of revolutions. Since there is a residue of 24, this number would include the fractional number 24/394,479,375 of revolutions also. Hence during the ahargana u, the number of revolutions completed would be
which would be an integer. Denoting this integer by v, the problem reduces to solving the following linear Diophantine equation:
Kuttaka may be applied to solve this equation. The smallest solution is
Let u be the value of the ahargana corresponding the residue 40 for Mars. During u days, Mars would have completed (190,412/131,493,125) × u number of revolutions. Since there is a residue of 40, this number would include the fractional number 40/131,493,125 of revolutions also. Hence during the ahargana u, the number of revolutions completed would be
which would be an integer. Denoting this integer by v, the problem reduces to solving the following linear Diophantine equation:
Kuttaka may be applied to solve this equation. The smallest solution is
{{cite book}}: CS1 maint: numeric names: authors list (link)
{{cite book}}: CS1 maint: numeric names: authors list (link)
