Mathematics in India

Introduction

Algorithms

The word `algorithm’ has been occurring frequently in our discussions in this series. As mentioned in [14], [pp. 64-65] Al-Khwārizmī had written an arithmetic treatise around 820 CE explaining the decimal notation and the Indian procedures for carrying out the four fundamental operations in arithmetic. The Latin translation of his treatise and its offshoots played a significant role in the spread of the decimal notation and Indian arithmetic methods in mediaeval Europe; and the word `algorismus’ (later `algorithmus’), derived from Algoritmi, the Latin form of Al-Khw\=arizmī, was given to any Indian computational method. The word `algorismus’ got contracted to `algorism’ which later became `algorithm’. Thus, the term “algorithm” originally referred to any Indian method for the fundamental arithmetic operations. Later, it came to denote a computer-implementable instruction. Jean-Luc Chabert remarks at the beginning of his Introduction to A History of Algorithms (Springer, 1999):

Ancient Indian mathematicians present much of their findings in the form of “algorithms” in the above sense, as many of the results that we have seen so far illustrate. Although their algorithms are rich in algebraic ideas, the format of “step by step instructions” which can be “carried out quite mechanically” often tends to camouflage the mathematical depth of the results.

In the next part of the series, we will discuss the emergence of `Algebra’ as a distinct subject in Indian mathematics from around the time of Brahmagupta. However, as we have seen repeatedly, sophisticated algebraic ideas are ubiquitous in Indian mathematical thoughts from at least the Vedic time, that is, much before they get crystallized into the structured subject that we now recognise as `Algebra’. In some sense, such algebraic ideas form the fountain-spring from which have emerged the ancient Indian algorithms.

Integer solutions of equations

In our high-school mathematics, we usually seek solutions of equations in real numbers or complex numbers. For instance, the solutions to the equation 2x^2+1=2^2 are given by x=\pm \sqrt{\frac{3}{2}}.

An intricate challenge for mathematicians is to devise algorithms for extracting those solutions of an equation in more than one variable which are integers (or rational numbers). For instance, consider the question of finding integers x,y such that 2x^2+1=y^2. In this case, a solution x=2,y=3 can be obtained by inspection. But there are other solutions like x=12, y=17. In fact, there are infinitely many integer solutions.

On the other hand, equations (even with integer coefficients) need not have integer solutions. For instance, one can easily see that the equation x^2+y^2=3 has no integral solution, though we know that it has infinitely many real solutions – corresponding to points on a circle.

The stringent restriction of admitting only integer (or even rational) solutions can make such problems particularly difficult. Sometimes, it is difficult even to determine whether an equation has an integral or even a rational solution or not. For instance, consider Fermat’s assertion that x^n+y^n=z^n has no nonzero integral solution when n>2. The proof of the statement by Andrew Wiles (1995) involves the works of numerous mathematicians over a period of nearly 350 years. Many powerful ideas and results in modern algebra and number theory originated from the very attempts to overcome the difficulties in finding integral solutions of equations. Indeed, new areas of mathematics have their genesis in the attempts to solve the problem.

Among the greatest mathematical achievements of post-Vedic stalwarts like Āryabhaṭa, Brahmagupta and Jayadeva are their contributions to this fascinating branch of `Number Theory’, especially their systematic methods for finding integers satisfying linear and certain quadratic `indeterminate’ equations. We explain the term `indeterminate’.

Indeterminate or Diophantine equations

An algebraic (i.e., polynomial) equation in more than one variable (or more generally, a system of m algebraic equations in more than m variables) is called `indeterminate’. The term is suggestive of the fact that such a system may have infinitely many solutions.

Diophantus of Alexandria (c. 250 CE) investigated the problem of finding a rational number satisfying an indeterminate equation – a topic of geometric importance. In his honour, any problem of finding integer solutions, as well as any problem of finding rational solutions, of an indeterminate equation is called a Diophantine problem. The corresponding indeterminate equation is also called a Diophantine equation.

Here, the adjective `Diophantine’ pertains not so much to the nature of the equation as to the nature of the admissible solutions of the equation. For instance, when one studies the locus of the equation x^2+y^2=5 in coordinate geometry, the equation is usually not considered to be a `Diophantine equation’. However when one studies the same equation for its integer solutions ((\pm 2, \pm 1) and (\pm 1, \pm 2 )), one considers it to be a Diophantine equation.

We clarify here that, while Diophantus was interested in `one’ particular `rational’ solution, Indian algebraists investigated `all’ possible `integral’ solutions. This difference in aim has been emphasized by the American historian of mathematics F. Cajori more than a hundred years ago (see [4], [p. 94–95]):

The study of indeterminate equations would play an important role in the evolution of classical algebra in ancient India as well as in modern Europe.

Indeterminate equations in history of mathematics

One of the tendencies in modern research on the history of mathematics has been to discover in ancient works the equivalents of modern concepts and ideas lying concealed in archaic language and style. This has been the approach of I.G. Bashmakova¹ in her work on Diophantus. Her innovative studies with such an approach have contributed to a revival of interest in Diophantus and have enhanced the understanding of modern scholars about his work on indeterminate equations.

However there is a dearth of literature which makes an analogous sophisticated analysis of ancient Indian works on indeterminate equations. Much information is recorded in the book by Datta-Singh (see [6]) which remains the richest reference book on ancient Indian algebra. However there is not much discussion on the significance of the works from the viewpoint of modern algebra. The ideas of abstract modern algebra had not become commonplace among the general mathematical community in India in the 1920’s and 1930’s when Datta did his pioneering work on the history of mathematics. In fact it is only in 1930 that the first textbook in Modern Algebra (by van der Warden) was published.

Now, although the basic facts regarding ancient Indian works on indeterminate equations are well-known among specialists in the history of Indian mathematics, not many students of mathematics, even in India, are aware of these works. Consequently, there is a general lack of awareness about the heights attained in ancient Indian mathematics not only among general readers but even among scholars in relevant disciplines like science (including mathematical science), history or Indology.

Integer solutions of equations in Śulba-sūtras

Historians of Indian mathematics have observed that certain Śulba prescriptions amount to specifying integer solutions of indeterminate equations arising in the context of the Vedic rituals. The builders of Vedic altars had to determine the numbers and sizes of bricks for the different layers of the altars, subject to various conditions arising out of engineering requirements as well as the requirements of the mystic rituals. For instance, a version of the Gārhapatya vedi is stipulated to have five layers of bricks, each layer containing 21 bricks, and forming an area of one square unit (vyāyāma). To have stability in the structure, the rifts (between two adjacent bricks) of two consecutive layers should not coincide; thus not all bricks can be of the same length. Suppose each layer has x square bricks of length \frac{1}{m} unit and y square bricks of length \frac{1}{n} unit, with m >n. Then, expressed in algebraic notation for our convenience, the altar-specifications amount to finding integers x,y,m,n satisfying the simultaneous indeterminate equations

\[\begin{equation}
x+y=21; \frac{x}{m^2}+\frac{y}{n^2}=1.
\end{equation}\]

There are precisely two sets of positive integral solutions for (x,y,m,n), namely (9, 12, 6, 4) and (16, 5, 6, 3). The Baudhāyana Śulba-sūtra prescribes making three types of square bricks of lengths {\frac{1}{6}}, {\frac{1}{4}} and \frac{1}{3} units and then placing 9 bricks of length \frac{1}{6} unit and 12 bricks of length \frac{1}{4} unit in the first, third and fifth layers; and 16 bricks of length \frac{1}{6} unit and 5 bricks of length \frac{1}{3} unit in the second and fourth layers. That takes care of both the ritual as well as the engineering requirements. Mathematically, we see that Baudhāyana has given all positive integral solutions of the simultaneous equations described in (1).

Constructions of śyena-cits present more intricate mathematical questions. Two such problems, due to Baudhāyana and Āpastamba respectively, when formulated in algebraic symbols, lead to the following systems of equations Inin eight/ten variables x,y,z,u,m,n,p,q; v,r to be solved in integers:

\[\begin{equation}
x+y+z+u=200; \frac{x}{m}+\frac{y}{n}+\frac{z}{p}+\frac{u}{q}=7
\frac{1}{2}.
\end{equation}\]

\[\begin{equation}
x+y+z+u+v=200; \frac{x}{m}+\frac{y}{n}+\frac{z}{p}+\frac{u}{q}+
\frac{v}{r}=7 \frac{1}{2}.
\end{equation}\]

The actual difficulties of construction are much more than what appears from mere algebraic considerations. The principles for constructions have also to ensure that the bricks are arranged in such a way so as to have the prescribed shape (like the intricate shape of a falcon). For more details, see [5], [Chapter XIV].

The Śulba-sūtras also mention several rectangles the lengths of whose adjacent sides a,b and the length of each diagonal c are all integers (or rational numbers), i.e., (a,b,c) are integral (or rational) triples satisfying the famous equation x^2+y^2=z^2. The integral triples (3,4,5), (5,12,13), (7,24,25), (8,15,17), (12,35,37) and some of their multiples (like (15, 36, 39)) occur in the Śulba-sūtras (see [5], [Chapter X] for more examples). The rectangle with sides 15 and 36 is highlighted not only in the Śulba-sūtras but also in the much more ancient Taittirīya Saṃhitā (2.4.5) and the Śatapatha Brāhmaṇa (3.5.1.1; 10.2.3.4).

Baudhāyana’s method for converting a rectangle into a square that was highlighted in [12], [pp. 28–29] suggests that Vedic scholars were aware that triples of the form (2rs, r^2-s^2,r^2+s^2) satisfy x^2+y^2=z^2 (see [5], [Chapter XIV]). Recall that his method implicitly involves the formula
ab=(\frac{a+b}{2})^2-(\frac{a-b}{2})^2,that is,
4ab+(a-b)^2=(a+b)^2.When a, b are squares, say a=r^2, b=s^2, we get the relation

(2rs)^2 + (r^2 - s^2)^2 = (r^2 + s^2)^2.The above relation may also be obtained from Kātyāyana’s method for combining squares that was highlighted in [12], [pp. 27–28] which implicitly involves the formula

na^2=(\frac{n+1}{2})^2a^2-(\frac{n-1}{2})^2a^2(see [5], [Chapter XIV]).

Linear indeterminate equations in India

Some prominent authors

The mathematical treatises of the Classical Age in ancient India exude the general intellectual robustness of the era. Two outstanding works of the period are: Āryabhaṭīya of Āryabhaṭa (499 CE) and Brāhma-Sphuṭa-Siddhānta of Brahmagupta (628 CE). These texts have a decisive influence on the course taken by Indian mathematics (and astronomy) for the next 1000 years. In particular, they are responsible for the emergence of a flourishing algebra culture in Indian mathematics.

A favourite topic among Indian mathematicians of the era is the devising of suitable algorithms to determine the general integral solution of the linear indeterminate equation ay-bx=c with integer coefficients. The algorithms are termed kuṭṭaka (pulverizer), derived from the root kuṭṭ (to crush, to grind); the equation itself (or the problem of finding integer solutions of the equation) is also referred to as kuṭṭaka.

The earliest extant description of the kuṭṭaka algorithm occurs in the Āryabhaṭīya (499 CE) and is generally considered to be Āryabhaṭa’s most significant contribution in (pure) mathematics. However, as the earlier post-Vedic mathematical treatises have not survived, one cannot ascertain the antiquity of the topic in India. Āryabhaṭa does not claim originality for any of his results. At the beginning of his chapter on mathematics, he makes a general acknowledgement that he is presenting the mathematical knowledge that is honoured at Kusumapura.

Āryabhaṭa describes the kuṭṭaka algorithm in just two terse stanzas (verses 32 and 33) at the end of the chapter Gaṇita (mathematics). The exposition on Āryabhaṭa’s obscure stanzas by his commentator Bhāskara I (c. 600 CE) has helped modern scholars to understand, translate and discuss Āryabhaṭa’s algorithm. His solution is discussed, with variations and refinements, in the texts of several subsequent Indian mathematicians including Bhāskara I (c. 600 CE), Brahmagupta (628 CE), Mahāvīra (850 CE), Govindasvāmin (c. 860 CE), Pṛthūdakasvāmin (c. 860 CE), Āryabhaṭa II (950 CE), Śrīpati (1039 CE), Bhāskara II (1150 CE), Nārāyaṇa (c. 1350 CE) and many others. There are numerous applications in Indian astronomy, especially in determining periodic events.

The high regard for the kuṭṭaka in Indian mathematics

We give some examples to show how much importance was given to the kuṭṭaka principle by Indian mathematicians. Brahmagupta names his chapter on Algebra (Chapter 18 of Brāhma-Sphuṭa-Siddhānta) as Kuṭṭakādhyāyaḥ. Thus, the subject Algebra itself is initially referred to as kuṭṭaka-gaṇita, or simply, kuṭṭaka, before the current Sanskrit term bījagaṇita appears in Indian mathematics.

In his commentary Āryabhaṭīya-bhāṣya, Bhāskara I gives 30 examples to illustrate Āryabhaṭa’s method (see [25], [pp 309–334] and [18], [pp. 130–166]); examples are also given in his astronomy treatises Mahā-Bhāskarīya (see [23], [pp. 29–46]) and Laghu-Bhāskarīya ([24], [pp. 99–114]).

The Mahāsiddhānta of Āryabhaṭa II contains a separate chapter (18) called kuṭṭaka exclusively on the solution to the linear indeterminate equation.

Bhāskara II discusses the kuṭṭaka in both his mathematics treatises Līlāvatī (see [21], [Chapter 33, pp. 167–175] [22], [Chapter 5, pp. 49–69]) and Bījagaṇita (see [1], [Chapter 5, pp. 17–21] and [20], [Chapter 5, pp. 49–69]).

Devarāja writes a separate treatise Kuṭṭākāra-śiromaṇi exclusively on the topic (see [6], [p 88]); such specialised treatises are very rare in the mathematical literature of ancient Indians.

Developments in modern mathematical sciences have vindicated the exalted status given to the kuṭṭaka by Indian mathematicians. We mention two examples.

The kuṭṭaka contains the seeds of a very influential idea of modern number theory: Fermat’s descent principle.

Finding integer solutions to the linear indeterminate equation ay-bx=c is now a fundamental step in modern cryptography (roughly, the science of making and breaking codes).

Towards the end of this part of the article we shall give brief indications of the connections kuṭṭaka has with cryptography and the descent principle.

It may be noted that if d is the GCD of a and b, then the kuṭṭaka shows how to express d as a linear combination d=xa-yb.

Linear indeterminate equations in modern Europe

F. Cajori laments (see [4], [pp. 97–98]):

Indeed, the Indian works on indeterminate equations during the 5th–12th centuries were too advanced for Arab and Persian scholars. For instance, in 1587 CE, when Fyzi translates, at the behest of Emperor Akbar, Bhāskara II’s popular treatise Līlāvatī from Sanskrit into Persian, he omits the portion on kuṭṭaka which is highlighted prominently in Līlāvatī.

It would then appear that the kuṭṭaka and other Indian works on integer solutions of indeterminate equations did not get transmitted to Europe during the medieval period. However, there are studies suggesting that, by the thirteenth century, some European mathematicians might have come to know of the kuṭṭaka method. It seems to occur in De elementis arismetice artis by Jordanus de Nemore. Menso Folkerts and Richard Lorch remark in their paper “The Arabic Sources of Jordanus de Nemore” (July 2007):

The problem of finding the integer solution of a linear indeterminate equation is described in Europe by C.G. Bachet de Méziriac (1581–1638) more than eleven centuries after Āryabhaṭa. Bachet had been interested in mathematical recreations and puzzles. His book Problèmes plaisants et délectables qui se font par les nombres (Pleasant and delectable problems to be solved by numbers) is a collection of such puzzles. In the first edition (1612 CE) of this book, Bachet states that if a and b are relatively prime integers, then one can find a least integral multiple of a which exceeds an integer multiple of b by a given integer c (i.e., one can find integers x,y such that ay-bx=c). The proof is given in the second edition of the book (1624). Dickson mentions that Bachet “employed notations for 18 quantities, making it difficult to hold in mind the relations between them and so obtain a true insight into his correct process” (see [7], [p. 44]).

In 1621, Bachet published a bilingual edition (Greek original with Latin translation) of Diophantus’ Arithmetica with extensive commentary. This work is largely responsible for the resurgence of number theory in Europe. Weil remarks about Bachet (see [28], [p. 33]):

In his edition (1621) of Diophantus’s Arithmetica, Bachet mentions his solution to the linear indeterminate equation ay-bx=c, emphasising that the method is his own (see [28], [p. 7]).

After Bachet’s work, several mathematicians in Europe continue to discuss various approaches to the equation ay-bx=c. Some of the early names include J. Kersey (1673), M. Rolle (1690), T.F. de Lagny (1697), L. Euler (1735), N. Saunderson (1740), W. Emerson (1764), J.L. Lagrange (1767), J. Bernoulli (1772) among many others; Chapter II of Dickson’s book [7] gives the details. As late as in 1798, that is, nearly two centuries after Bachet, the great Legendre writes in the preface of his Theory of Numbers (quoted in translation in [16], [p. 3]):

Pierre de Fermat (1601–65), who is regarded as the father of modern number theory, carefully reads Bachet’s version of Diophantus and comes across his solution to the linear indeterminate equation. He creates enthusiasm for number theory among his contemporary mathematicians through the problem of finding integer solutions to certain quadratic indeterminate equations (see Box 5 in [11], [p. 19]). He lays special emphasis on methods for finding `integer’ solutions of indeterminate equations as distinct from the easier, though important, question of finding rational solutions that occurs in Diophantus.

The kuṭṭaka algorithm

Brevity in Indian tradition

Mathematical treatises in ancient India by the leading mathematicians, especially the earlier texts, are generally very brief. They are meant only to indicate broad hints and a student or a learner is expected to use the intellect for working out the complete details. Sometimes the commentaries give details. The approach of the ancient stalwarts can be seen from the following remarks that Bhāskara II makes in the epilogue of his text Bījagaṇita (see [1], [p. 53] and [20], [pp. 196–197]):

This attitude matches the attitude of most modern mathematicians who too feel that a budding researcher eventually gains more insight from a terse text than from a clearly spelt-out text, from an obscure important paper than from a lucid one.

The original description of kuṭṭaka by Āryabhaṭa, quoted at the end of this part, is excruciatingly brief. Historians of mathematics have interpreted his two verses based on ancient commentaries; for instance, B. Datta has been guided by the explanation of Bhāskara I, the earliest commentator on Āryabhaṭīya whose work is available to us.

The descriptions by Bhāskara I, Brahmagupta and several other writers are quite similar, in essence. Āryabhaṭa II observes some simplifying devices which are emulated by later writers. In Bījagaṇita, Bhāskara II makes a neat presentation of the main algorithm and the useful auxiliary principles and states a few suggestive examples where one can implement the prescribed rules (see [1], [Chapter 5] and [20], [Chapter 5]).

We make a summary of the various presentations of the kuṭṭaka by authors ranging from Bhāskara I to Bhāskara II, highlighting their key ideas. Details take up 54 pages in the book of Datta-Singh (see [6], [pp. 87–140]).

Formulation of the kuṭṭaka

If we take a,b,c to be positive integers, then any linear indeterminate equation in two variables is of the form ay-bx=\pm c or ay+bx=\pm c. The concrete applications in ancient Indian astronomy require the determination of all `positive’ integral solutions of equations of the type ay-bx=\pm c, where a,b,c are positive integers, a problem even more subtle than that of finding all integral solutions. We shall discuss algorithms evolved by Indian mathematicians for determining all such solutions. For simplicity, we shall often discuss solutions in integers rather than in positive integers.

As an illustration of how a concrete problem like 100y-63x=\pm 90 is usually phrased in Indian mathematical literature, we quote from the Bījagaṇita (also Līlāvatī) of Bhāskara II (see [1], [p. 20] [20], [p. 58] and [21], [p. 167]):

The equation ay-bx=\pm c is thus visualised by ancient Indians in the form y=\frac{bx \pm c}{a}. The quantities a,b,c,x,y are called hāra or bhājaka (divisor), bhājya (dividend), kṣepa (interpolator), guṇaka (multiplier) and phala or labdhi (quotient) respectively.

Bhāskara I arranges the equation in the form y=\frac{bx + c}{a} or x=\frac{ay +c}{b} so as to ensure that the interpolator c comes with a positive sign. Almost all ancient Indian writers observe, in some form, that the equation ay-bx=c will have integral solutions only if c is divisible by the GCD (greatest common divisor) of a and b.

Modern strategies in kuṭṭaka

A standard trick in modern mathematics is to be on the lookout for simplifications or `reductions’ through which one tries to transform a problem to an equivalent but neater problem, possibly a more tractable problem, where the underlying features become more transparent. This feature can be seen repeatedly in the Indian kuṭṭaka methods.

The reductions in the kuṭṭaka may also be viewed in the light of the `divide and conquer’ strategy used in computer science, where a problem is broken down recursively into sub-problems of the same or related type, until the sub-problems become simple enough to be solved directly; the sub-problems are then combined to produce an algorithmic solution to the original problem. As discussed in (see [13], [pp. 54–55)] an early manifestation of this “divide and conquer” strategy can be seen in Pi\dot{\rm n}galācārya’s brilliant algorithm for computing 2^n.

We first illustrate a few preliminary reductions in the kuṭṭaka.

Preliminary reduction 1: size of coefficients

First, Bhāskara I, Brahmagupta, Āryabhaṭa II, Śrīpati and Bhāskara II, among others, explicitly state that all the coefficients should be divided by \mathrm{GCD} (a,b) (= \mathrm{GCD} (a,b,c)), so that the coefficients in the reduced equation become relatively prime, or to use ancient terminology, [mutually] dṛḍha (firm or reduced), niccheda (having no divisor), nirapavarta (irreducible). For determining the GCD, the standard long division method of mutual division is recommended.

The first example 221y + 65 = 195x in the kuṭṭaka section of the Bījagaṇita of Bhāskara II (see [1], [p. 20] and [20], [p. 57]; also [21], [p. 171]) is meant to illustrate this reduction.

The equation 221y-195x=-65 reduces to 17y-15x=-5.

By this reduction, not only do the coefficients become smaller (thereby simplifying computations), but, more importantly, one is now better equipped to tackle the problem as one has the advantage of the additional property of a and b being coprime – a property which is potentially useful.

Another subtle reduction of Āryabhaṭa II, applicable in case there is a common factor between a and c or between b and c, further reduces the size of the coefficients of x and y.

Let g_1= \mathrm{GCD} (a,c), a_1=\frac{a}{g_1}, g_2= \mathrm{GCD} (b, \frac{c}{g_1}) and b_1=\frac{b}{g_2}. Then Āryabhaṭa II, and his successors like Bhāskara II, observe that the problem of solving ay-bx= \pm c reduces to the problem of solving a_1Y-b_1X= \pm 1: if (u,v) is an integral solution of the latter, then (\frac{cu}{g_2}, \frac{cv}{g_1}) is an integral solution of the original equation.

For instance, the problem of solving 100y-63x=-90 (cited by Bhāskara II) reduces to solving 10Y-7X=-1. Once one obtains the solution X=3, Y=2 of the reduced equation 10Y-7X=-1 by the main algorithm (in this case, one can also get it easily by inspection!), one immediately gets the solution x=30, y=18 for the original equation 100y-63x=-90.

Preliminary reduction 2: reduce to finding one solution

Second, the problem of finding all positive integral solutions is reduced to that of finding one positive integral solution. Note that, since a and b are positive, if (x_1,y_1), (x_2,y_2) are pairs of positive integers satisfying ay-bx=\pm c, then x_1 \le x_2 if and only if y_1 \le y_2. Therefore, one can talk about a “minimum positive integral solution” (\alpha, \beta).

Now suppose that (u,v) is a positive integral solution of ay-bx= \pm c. From (u,v), one first finds the minimum positive integral solution (\alpha, \beta). Dividing u and v by a and b respectively, we have u=pa+r and v=qb+s for some whole numbers p,q, r,s such that 0<r<a and 0<s<b.

If p=q, then (r,s) is clearly a solution of ay-bx=\pm c; in fact, it is the minimum positive integral solution (proof is easy).

If p \not= q, then it can be seen that p<q when we consider the equation ay-bx=c; and p>q when we deal with ay-bx=-c. The minimum positive integral solutions in the two cases are (r, s+(q-p)b) and (r+(p-q)a,s) respectively.

The above rule for arriving at the minimum solution has been explained lucidly by Āryabhaṭa II but is already implicit in Bhāskara I.

If (\alpha, \beta) is a minimum positive integral solution of ay-bx=\pm c, then Bhāskara I and his successors describe the general positive integral solution as (\alpha+ta, \beta+tb) where t is a positive integer.

To see this, first note that if a \beta-b \alpha=c, then a(\beta+tb)-b(\alpha+ta)=a \beta -b \alpha =c.

Conversely, suppose ay-bx=c. We also have a \beta-b \alpha=c. Subtracting, we get

a(y-\beta)=b(x-\alpha).As a,b are coprime, we have b divides y-\beta and a divides x-\alpha.

Thus, \frac{x-\alpha}{a}=\frac{y-\beta}{b}=t is an integer. Hence, x=\alpha+ta and y=\beta+tb for some integer t.

The above arguments also show that if (x_0,y_0) is any integral solution of ay-bx=c, then the general integral solution is given by x= x_0+ta, y=y_0+tb where t is any integer.

Preliminary reduction 3: reduce to the case c=1

Third, it is clearly enough to solve an equation of the type ay-bx=\pm 1; for, if av-bu=\pm 1, then a(cv)-b(cu)= \pm c.

Such equations are called sthira-kuṭṭaka (constant pulverizer). This simplification too is made by some of the Indian mathematicians right from Bhāskara I.

As we shall see in an example from astronomy, the conditions in problems on Indian astronomy, involving the equations ay-bx=\pm c, are often such that the coefficients a,b are the same in several equations but the interpolator c varies.

In such situations, working first with the constant pulverizer and then modifying the solution according to the specific problem becomes convenient.

Preliminary reduction 4: a>b

Some ancient Indian authors also show that we can reduce to the case a >b. This step is achieved through two different methods.

The later method corresponds to the modern approach: if b>a, think of the equation as bx-ay = \mp c rather than ay-bx = \pm c.

But earlier writers like Bhāskara I, who already have to arrange the equation ay-bx=c so as to have only positive coefficients, use the following device when b>a: Let b=aq+b_1 where b_1 <a. Then the original equation transforms into the equation ay_1-b_1x=c (where y_1=y-qx) which is of the desired form. If (u,v) is a solution of ay_1-b_1x=c, then (u,v+qu) is a solution of ay-bx=c.

We shall henceforth assume a>b as it will facilitate our discussions.

Main reduction: An Example

The heart of the kuṭṭaka algorithm lies in the implicit reduction of the problem to the case b=1. This is achieved through a sequence of inductive steps. For transparency, we describe this main step through modern notation. However in order that we do not get lost in notation, we first indicate the ideas implicit in the main step through a simple example.

We consider the problem of finding positive integers satisfying 10y-7x=1, the reduced form of one of the exercises set by Bhāskara II.

It would have been easy to solve the equation had one of the coefficients been 1, say, if one had to solve y-7x=1; one could have taken x=t for any t and y=7t+1; for instance, x=1, y=8.

Can we make use of this observation that it is easy to solve ay-bx=c in integers if one of the coefficients of x,y is one?

An idea: can we try to make a change of variables (x,y) \rightarrow (x_1,y_1) so that the equation 10y-7x=1 becomes an equation of the form y_1-b_1x_1=\pm 1?

Can we do it through a sequence of change of variables (x,y) \rightarrow (x_1,y_1) \rightarrow (x_2, y_2) \rightarrow … , each time the size of the coefficients becoming smaller?

To implement the idea, we need a method to reduce the coefficients, i.e., to get an equivalent equation with smaller coefficients. Let us return to the example.

10= 1 \times 7 +3.

Substituting, we have

(1 \times 7+3)y-7x=1, i.e., latex]7(y-x) +3y =1[/latex].

Thus, the original problem reduces to solving:

7z - 3y= -1, where z=x-1y, i.e., x= 1y+z.

Thus, if we can find out (y,z), we shall know (x,y). But the new pair of coefficients (3,7) is smaller than the earlier (7,10).

We continue the process.

7=2 \times 3 +1.

3(2z-y) +z= -1.

The problem reduces to solving:

3w-z=1, where w=y-2z, i.e., y= 2z+w.

As the coefficient of z is one, we are through. Put w=1. Then,

\[\begin{align*}
z&=3w-1=2,\\
y&=w+2z=5,\\
x&=y+z=7.
\end{align*}\]Thus, we have found a solution of the equation 10y-7x=1: x=7, y=5.

How do we achieve this? We break the larger coefficient 10 with the hammer of the smaller 7 and carry on with similar hammering, till the smaller coefficient becomes 1.

We now describe the main step of Āryabhaṭa’s algorithm using the interpretation of Bhāskara I.

Main step

Formally, there are two major components in the method. The first is to apply the long division algorithm for finding GCD, to the two numbers a and b and note down the intermediate quantities. To facilitate our theoretical understanding, we write them here in the form of successive divisions. Here, n denotes the total number of steps

\[\begin{align*}
a&=a_1b+r_1 (1 \le r_1 < b),\\
b&=a_2r_1+r_2 (1 \le r_2 <r_1< b),\\
r_1&=a_3r_2+r_3 (1 \le r_3 < r_2 <r_1< b),\\
\vdots\\
r_{n-2}&=a_nr_{n-1}+1 (1 =r_n < r_{n-1} < r_{n-2} < \cdots < b).
\end{align*}\]Now, for solving ay-bx=1, the next and crucial step in the kuṭṭaka is a reversal.

Define quantities x_{n+2}, x_{n+1}, x_n, … by backward induction as follows: first define x_{n+2} and x_{n+1} to be whole numbers satisfying the relation r_{n-1}x_{n+2}-x_{n+1}=(-1)^n.

Thus, if n is odd, one can simply take x_{n+2}=0 and x_{n+1}=1; if n is even, one can take x_{n+2}=1 and x_{n+1}=r_{n-1}-1.

Now define x_m (n \geq m \geq 1) by x_m=a_mx_{m+1}+x_{m+2}. For facilitating the computation of x_n, …, x_2, x_1, the Indians construct convenient tables called vallī. As will be clear from subsequent discussions, the numbers x_1, x_2 satisfy ax_2-bx_1= 1; thus (x_1,x_2) is a solution of the equation ay-bx= 1.

For instance, for the equation 26y-7x= 1, we first obtain the a_i‘s as follows:

\[\begin{align*}
26&= 3 \times 7 + 5.\\
7&= 1 \times 5 + 2.\\
5&= 2 \times 2 + 1.
\end{align*}\]Thus, here, n=3; a_1=3, a_2=1, a_3=2.

Now, the reversal (or back-substitution algorithm for solving simultaneous linear equations) yields:

\[\begin{align*}
x_5&=0. x_4=1.\\
x_3&=a_3x_4+x_5=2 \times 1+0=2.\\
x_2&=a_2x_3+x_4=1 \times 2 +1=3.\\
x_1&=a_1x_2+x_3=3 \times 3 +2=11.\end{align*}\]Thus, 26 \times 3 - 7 \times 11=1.

The algorithm is carried out in the form of a table:

For a_1=3, a_2=1, a_3=2, it takes the form:

In our mode of communication, we had to print four columns above with several entries repeated. Indians would write only one column: initially the first column and then keep on replacing the entries – in the above case, first replace a_3 by x_3, then a_2 by x_2 and finally a_1 by x_1.

Bhāskara I explains that one need not continue the repeated division till the stage r_n=1. One can terminate at an intermediate stage k if, having obtained r_1, …, r_k, one can observe, by inspection, positive integers u, v satisfying r_{k-1}u-r_kv=(-1)^k. One can then define x_{k+2} (=u), x_{k+1} (=v), …, x_2 (=y), x_1 (=x) recursively, as before, and obtain a solution of the equation ay-bx=1.

For solving ay-bx=-1, one considers numbers x_{k+1} (k \leq n) and x_{k+2} satisfying r_{k-1}x_{k+2}-r_kx_{k+1}=(-1)^{k+1}; the rest is as above. Or, one can take the approach of Bhāskara II: solve ay-bx=1 and use the fact that if (\alpha, \beta) is the minimum positive integral solution of ay-bx=1, then (a-\alpha, b-\beta) is the minimum positive integral solution of ay-bx=-1.

To derive solutions of 26y-7x=- 1 from the solution (11,3) of 26y-7x=1, note that 26 \times 3 - 7 \times 11=1 implies 26 \times (3+7t) - 7 \times (11+26t)=1 for all t, i.e., 26 \times (-3+7t) - 7 \times (-11+26t)=-1 for all t. In particular, 26 \times 4 -7 \times 15=-1, i.e, 7 \times 15 - 26 \times 4 =1.

Brahmagupta, Bhāskara II and Nārāyaṇa give similar rules for deriving integer solutions of ay+bx=c (see [6], [pp. 120–125]).

Hidden in the deceptively simple kuṭṭaka algorithm lies a beautiful idea which has inspired a powerful technique in modern number theory.

The key `descent’-like idea

We now discuss the underlying idea of Āryabhaṭa for solving ay-bx=\pm 1 that we had earlier tried to illustrate through a numerical example. To fix our ideas, let us take the RHS to be 1. The key idea may be formulated as follows:

1. Assume the existence of a positive integral solution (x,y) to the equation aY-bX=1.
2. Then transform this equation in successive steps into equations with progressively smaller coefficients and solutions to eventually arrive at an equation a^{\prime}Y^{\prime}-X^{\prime}=\pm 1 with an obvious solution (x^{\prime}, y^{\prime})=(a^{\prime}t \mp 1,t) for any t.
3. Then work backwards from this obvious solution (x^{\prime}, y^{\prime}) of the reduced equation to determine the desired solution (x,y) of the original equation.

To elaborate, assume that (x,y) is a positive solution of the equation aY-bX= 1. Recall that we are assuming 0<b<a and a,b are coprime.

If a-b=1, then (1,1) is a solution of aY-bX=1. So we may further assume that a-b >1. Then x>y.

If b had been 1, we would have been through. This prompts the approach: why not try to “break” (i.e., “pulverize”) the coefficients a,b into smaller ones?

Recall the relation a=a_1b+r_1 with 0<r_1<b. Each component of the pair (b,r_1) is smaller than that of the pair (a,b).

Now one tries to transform the equation aY-bX= 1 to get an equation with coefficients b and r_1. The relation ay-bx= 1 leads to the relation (a_1y-x)b+r_1y= 1.

Set z:=x-a_1y. Then clearly 0<z<y and (y,z) is a positive solution of the equation bZ-r_1Y= - 1 which is again a linear equation of the original form; but now the solution (y,z) is coordinate-wise smaller than the original (x,y) and, moreover, the coefficients (of the new equation) too have become smaller since 0<b<a and 0<r_1<b. The two pairs of solutions being linearly related, if one can determine the smaller pair (y,z), one can easily compute the original (x,y).

Denote x,y,z by x_1,x_2,x_3 respectively. Proceeding as above (introducing x_4, x_5, \cdots, etc.), since r_n=1 (as per our earlier notation), one eventually arrives at the easily solvable equation r_{n-1}X_{n+2}-X_{n+1}=(-1)^n. From this equation, one works backwards to arrive at the solution (x,y) of the original equation aY-bX=1.

For instance, in the example 10x_2-7x_1=1, the kuṭṭaka uses the fact that solving 10x_2-7x_1=1 is equivalent to solving 7x_3-3x_2=-1 (where x_3=x_1-x_2), which, in turn, is equivalent to solving 3x_4-x_3=1 (where x_4=x_2-2x_3); and the latter has the obvious positive integral solution x_3=2, x_4=1.

Thus, the main algorithm itself is an illustration of a non-trivial application of the modern `reduction’ principle: it transfers, through a sequence of steps, a somewhat involved problem to a problem with an obvious solution. Since the process involves the breaking up of the original data (both solutions and coefficients) into successively smaller numbers by repeated division, the term kuṭṭaka (pulverizer) is apt; in fact, it gives a hint to the learner of the main idea behind the algorithm.

A crucial principle implicit in this algorithm is that a decreasing sequence of positive integers must terminate after a finite stage – which is but a version of Fermat’s celebrated `principle of descent’!

Kuṭṭaka and Fermat’s infinite descent

Bachet’s rediscovery of the kuṭṭaka in his way, more than 11 centuries after Āryabhaṭa, triggers several fruitful ideas in number theory. The principle is ingeniously developed by Fermat, Brouncker and Wallis in their researches on number theory both for constructing solutions of equations and for showing that certain equations do not have integral solutions. The most profound example is Fermat’s famous principle of “infinite descent” (or, simply “descent”) which may be formulated as follows:

The principle of descent may be viewed as a consequence of the `Well-ordering Principle’:

As a simple illustration of the descent principle, one can prove that Fermat’s Last Theorem³ holds for n=4. One proves that the equation x^4+y^4=z^2 has no positive integral solution. (Note that if x^4+y^4=u^2 does not have any positive integer solution, then x^4+y^4=z^4=(z^2)^2 cannot have any positive integer solution.)

The main idea of the proof is to assume the existence of a hypothetical positive integral solution (x_0, y_0,z_0); without loss of generality, one may assume that x_0 and y_0 are coprime and x_0 is even. Then (x_0^2,y_0^2, z_0)=(2mn, m^2-n^2, m^2+n^2) for some positive integers m,n; a fact known from the ancient times (it occurs explicitly in Euclid, Diophantus and Brahmagupta). Now after some elementary algebraic manipulations,⁴ one can construct another solution (x_1,y_1,z_1) with x_1, y_1,z_1 coprime positive integers and 0<z_1<z_0. But then, repeating the process, one gets an infinite chain (descent)

z_0>z_1> z_2> \cdots z_n \cdots >0which is impossible! The contradiction proves that there does not exist any positive integral solution of x^4+y^4=z^2.

The resemblance between the descent principle and the kuṭṭaka idea is unmistakable! Both make subtle uses of the principle that

Āryabhaṭa’s algorithm uses this principle to obtain integer solutions of linear indeterminate equations; Fermat’s descent uses the same principle to show that certain equations (like x^4+y^4=z^2) do not have nonzero integer solutions.

Indeed, not only the kuṭṭaka method, the term kuṭṭaka itself, reminds one of Fermat’s celebrated principle. As André Weil (1906–1999), one of the giants of twentieth century mathematics, remarks (see [28], [p.7]):

Fermat uses the descent method to prove that the area of a right-angled triangle, the lengths of whose sides are all rational numbers, cannot be the square of a rational number (see [16], [p. 13]). In a letter written towards the end of his life, he remarks that all his proofs of his discoveries in number-theory use the descent method! He predicts (see [16], [p. 13]):

This technique has indeed turned out to be a powerful tool of fundamental importance in modern number theory! It has been crucially used, directly or implicitly, in several deep theorems in the area, especially in the study of elliptic curves.

Kuṭṭaka in various frameworks

Kuṭṭaka and a problem of congruence arithmetic

Now suppose that a is a positive integer coprime to n. The problem of finding an integer x satisfying the congruence problem ax \equiv 1 (mod n) is clearly equivalent to finding integers x, y such that ax-ny=1 and hence can be solved by kuṭṭaka.

For readers familiar with the concept of ideals and quotient rings, if \mathbb Z is the ring of integers, n is a positive integer, and a is a positive integer coprime to n, then in the quotient ring {\mathbb Z}/n{\mathbb Z}, the image \overline{a} of a is a unit (i.e., invertible) and the inverse can be explicitly computed by the kuṭṭaka.

We mention here a useful fact. Suppose e is a solution of ax \equiv 1 (mod n). Then it can be seen that the congruence y \equiv ax+b (mod n) implies x \equiv e(y-b) modulo n. For instance, we have seen that e=15 is a solution of 7x \equiv 1 (mod 26). Therefore, the congruence y \equiv 7x+12 (mod 26) implies x \equiv 15(y-12) \equiv 15y+2 modulo 26. This calculation will be used in our subsection on Kuṭṭaka in Cryptography.

Kuṭṭaka and continued fractions

Continued fractions is a useful topic in elementary number theory; Ramanujan had a phenomenal mastery over continued fractions. An introductory article on Continued Fractions and how Ramanujan used it to promptly solve a problem posed by Mahalanobis was discussed in the article by Sudhir Rao in the inaugural January 2017 issue of Bhāvanā. A nice introduction to the theory of continued fractions is given in the classics on Classical Algebra by Barnard and Child (see [3]), and by Hall and Knight (see [17]); a student-friendly account is also given in [27].

The kuṭṭaka may be interpreted as a technique in the theory of continued fractions. The formulation y=\frac{bx+c}{a} and method of solution have given rise to a suggestion that the pioneers of the kuṭṭaka algorithm knew the basic principles of continued fractions (see [2]).

Knowledge of continued fractions is more apparent in some of the later Indian works. In the versions of kuṭṭaka we have described so far, after obtaining the quotients a_1, …, a_n, one computes quantities x_n, x_{n-1}, … in the backward direction (i.e., one moves from below to top in the table).

But in certain later texts like the Karaṇapaddhati and the Yuktibhāṣā (1540 CE) of Jyeṣṭhadeva, having obtained the quotients a_1, …, a_n, the authors construct sequences of numbers p_m and q_m by the recurrence relations

\[\begin{align*}p_0=1,p_1=a_1; p_m=a_mp_{m-1}+p_{m-2}\\
q_0=0,q_1=1; q_m=a_mq_{m-1}+q_{m-2}\end{align*}\]till they reach p_n and q_n (where n is as before). Then it is asserted that aq_n-bp_n=(-1)^{n+1}, i.e., (p_n,q_n) is a solution of one of the equations ay-bx=\pm 1 (the solutions of the other equation can be derived using techniques discussed earlier).

This direct method can be best understood in the language and framework of continued fractions. One has been calculating the simple continued fraction expansion of \frac{a}{b}; the quantities a_1, a_2,…, a_n, a_{n+1}(=r_{n-1}) are the “quotients”, i.e., {\frac{a}{b}}=[a_1, …, a_n, r_{n-1}], and \frac{p_m}{q_m} are the successive convergents (which are actually characterised by the above recurrence relations). The theory of continued fractions yields the identity p_mq_{m-1}-q_mp_{m-1}=(-1)^m. Since p_{n+1}=a and q_{n+1}=b, we have the relation aq_n-bp_n=(-1)^{n+1}.

The solution of the linear indeterminate equation in the notation of continued fractions was given by Saunderson in England in 1740 and Lagrange in France in 1767.

Kuṭṭaka and matrix operations

It may be of interest to note that the kuṭṭaka algorithm may also be interpreted as the solution of a system of linear equations by matrix operations.

The linear transformations a=a_1b+r_1, b=b; x=a_1y+z, y=y may be expressed as

\[\begin{align*}\left( \begin{array}{cc} a&b \\[2pt] x&y \end{array} \right)
&=
\left( \begin{array}{cc} b&r_1 \\[2pt] y&z \end{array} \right)
\left( \begin{array}{cc} a_1&1 \\[2pt] 1&0 \end{array} \right)\\
&=
\left( \begin{array}{cc} b&r_1 \\[2pt] y&z \end{array} \right)
\left( \begin{array}{cc} 0&1 \\[2pt] 1&0 \end{array} \right)
{\left( \begin{array}{cc} 1&0 \\[2pt] 1&1 \end{array} \right)}^{a_1}\\
&= \cdots \end{align*}\]Proceeding in this manner, eventually the LHS can be expressed as a product of invertible matrices with entries 0,1.

Kuṭṭaka: Impact on subsequent progress of mathematics

From at least the time of Āryabhaṭa, the kuṭṭaka algorithm comes up in Indian mathematics as a practical algorithm to solve an interesting number-theoretic problem which arises in Indian astronomy. The problem and its solution would be described in Europe by C.G. Bachet (in 1612 and 1621). The work of both Āryabhaṭa and Bachet on finding integer solutions of linear equations have a tremendous impact on fundamental mathematical thinking in India and Europe respectively and there are interesting parallels in both the developments.

In India, after Āryabhaṭa’s kuṭṭaka (499), Brahmagupta takes up the much harder problem of finding positive integer solutions to the quadratic indeterminate equation Nx^2+1=x^2 for a fixed non-square positive integer N. It is solved in India by subsequent algebraists using the cakravāla method which we shall discuss in a subsequent issue. Along with the kuṭṭaka, this equation is considered very important in Indian mathematics. One also sees the establishment of a strong algebra culture in India.

In Europe, after Bachet (1621) announces his method for solving ay-bx=c in integers, a variant of Āryabhaṭa’s method, considerable excitement is generated among European mathematicians. The work inspires several fruitful ideas including the principle of descent. As we have seen, even after 177 years, Legendre (1798) describes Bachet’s method as “very ingenious” which indirectly gives us an idea of the weight of the kuṭṭaka achievement of the fifth century.

Again, Fermat takes up the problem of finding integer solutions to the indeterminate equation Nx^2+1=y^2 and encourages contemporary mathematicians to do so. While analyzing Brouncker’s solution to the equation Nx^2+1=y^2, Weil brings out the implicit `descent’-like idea in Brouncker’s method and remarks that Bachet’s method must have provided a model for Fermat and Brouncker. We quote below excerpts from the passage of Weil (see [28], [p. 93]); we have highlighted a portion in italics.

It may be noted that the discovery of the Indian cakravāla (which also has a descent-like aspect to it) takes place in an environment where the kuṭṭaka method has a strong influence; in fact, the kuṭṭaka algorithm itself is used in the solution, as we shall see in a later part of this series.

Kuṭṭaka in modern cryptography

The word `cryptography’, derived from kryptós (secret) and graphein (writing), signifies the science of secret communication in the presence of adversaries. We shall now illustrate how the determination of integer solutions of linear indeterminate equations fulfils a fundamental step in cryptography. It involves algorithms for `encryption’ (coding), called `cipher’ which contains a secret `key’ known only among communicants, and for `decryption’ (decoding).

We attach values to the 26 letters as follows: A=0, B=1, C=2, \cdots, Z=25. More than two thousand years ago, Julius Caesar used codes like: “shift each letter by 3” (i.e. A goes to D, B to E, and so on, W to Z, X to A, Y to B, Z to C). In modern language, he used the coding function x+3 (mod 26), so that the decoding function would be y-3 (mod 26). In the terminology of cryptography he used `shift cipher’ x+b (mod 26) with `key’ b; in the above example b=3 so that a word like YES will get coded as BHV.

Such a coding will be too simplistic for the modern age. A more complicated cipher will be the `affine cipher’ ax+b (mod 26) with keys a,b, which we explain below.

First note that we call a transformation (or function) in one variable x `linear’ if it is of the form f(x)=ax and a `translation’ if it is of the form x+b, where a,b are constants. A function is called `affine’ if it is a composite of a linear transformation and a translation, i.e., it is of the form f(x)=ax+b. In a linear transformation, f(0)=0, i.e., the origin is preserved; in an affine transformation, the origin gets shifted by b units.

In an `affine cipher’ ax+b (mod 26) with keys a,b, if x is the value attached to the letter to be coded, then its code will be ax+b (mod 26). Thus, if the keys are a=7, b=12, and the letter E is to be coded, i.e., if x=4, then the code for E will have value 7 \times 4 +12=40 \equiv 14 (mod 26); thus the code for E will be O.

The decoding algorithm will then be e(y-b) (mod 26), where e is an integer such that ea \equiv 1 (mod 26). As we noted before, the kuṭṭaka algorithm determines e and mathematically, this is the only intricate computation involved in the entire procedure.

To see a numerical example, consider the coding function 7x+12 (mod 26) obtained by taking the keys a=7, b=12. Since 7 \times 15 \equiv 1 (mod 26), here e=15 so that eb=180 \equiv 24 \equiv -2. Thus the decoding function will be 15y+2 (mod 26). For instance YES will get coded as YOI and the decoding function gives back YES.

Euclidean algorithm and Kuṭṭaka: A Caveat

There is an unfortunate tendency among writers on history of mathematics to make remarks to the effect that the solution to the linear indeterminate equation “is essentially identical with” or “does not differ substantially from” or “is just a straightforward application of” the “Euclidean algorithm” for finding the GCD. Such phrases are highly misleading and tend to undermine, often inadvertently, the achievement involved in the discovery of the kuṭṭaka. In fact, in the Indian treatment of kuṭṭaka, the algorithm for finding the GCD is not even described – the knowledge is taken for granted. The kuṭṭaka algorithm begins where the algorithm for the GCD ends.

To put matters in perspective we recall that there are two major steps or principles involved in the ancient Indian kuṭṭaka for solving ay-bx=c:

1. Computation of the GCD d of a and b.
2. Expression of d as a linear combination of a and b.

In modern college-algebra, the two steps may be viewed, respectively, as corresponding to the algorithmic proofs of the following general statements in Ring Theory of modern Abstract Algebra:

1. “The ring of integers \mathbb Z is a Euclidean Domain and in a Euclidean Domain, any two non-zero elements have a GCD.” and
2. “Any Euclidean Domain is a PID.”

Thus, in essence, the kuṭṭaka implicitly gives a constructive proof of the statement (B).

For readers unfamiliar with the terms: a Euclidean Domain is an integral domain R in which the appropriate analogue of the principle of “division with remainder”—the so-called “Division Algorithm” mentioned in (see [13], [p. 44])—holds for any two elements a and b of R with b \ne 0.

Formally, a Euclidean Domain is an integral domain R on which there exists a (non-negative) integer-valued function N on R with N(0)=0 such that given a, b(\ne 0) \in R, there exist q,r \in R such that a=bq+r with either r=0 or N(r)<N(b). The ring of integers \mathbb Z is a Euclidean Domain with N(a)=|a|.

A PID (Principal Ideal Domain) is an integral domain R in which every ideal I is principal, that is, every ideal I is of the form Rd for some d \in R. Note that if a,b \in I=Rd, then there exist x,y \in R such that ax-by=d. \mathbb Z is a PID whereas the polynomial ring R={\mathbb Z}[x] is not a PID, as the ideal \{2f+xg | f,g \in R \} is not principal.

The concept of GCD of two integers has the following generalisation in the case of an integral domain R: d is said to be a GCD of two non-zero elements a and b of R if

(i) a=a_1d and b=b_1d for some a_1, b_1 \in R, and

(ii) if d^{\prime} \in R is such that a=a^{\prime}d^{\prime} and b=b^{\prime}d^{\prime} for some a^{\prime}, b^{\prime} \in R, then d=d_1d^{\prime} for some d_1 \in R.

As in Euclid’s Elements (Proposition 2 of Book VII), the repeated application of Division Algorithm shows that any two non-zero elements of a Euclidean Domain have a GCD and that it can be computed algorithmically. By describing, again algorithmically, how to express the GCD as a linear combination of a and b, Āryabhaṭa’s kuṭṭaka shows that the ideal generated by two non-zero elements a and b of a Euclidean Domain R is the principal ideal generated by their GCD thereby giving a constructive proof of the property that any Euclidean Domain is a PID (the converse is not true). Further details on Euclidean Domains and PIDs can be found in Chapter 8 of the book Abstract Algebra by D.S. Dummit and R.M. Foote (Wiley 2003); one may also see Chapter 11 Section 2 of Algebra by M. Artin (Prentice-Hall of India) or Chapter 2 of University Algebra by N.S. Gopalakrishnan (Wiley Eastern)..

To return to our discussions, Step II does not occur in the Elements or in any extant ancient Greek text. Modern mathematicians, well-trained in years of high-school classical algebra, sometimes think of Step II as a trivial corollary to Step I.

But to appreciate Step II in the context of its history in India, one should note that it was discovered before algebra had formally established itself in Indian mathematics and that at the time of discovery and for a few centuries thereafter, it was considered a significant feat by some of the strong ancient Indian mathematicians. Even Brahmagupta’s treatise imparts considerable emphasis on the kuṭṭaka and provides plenty of illustrative examples. All of them touch Step I lightly, they dwell mainly on Step II.

One has also to note that, after Bachet’s rediscovery (1612) of the kuṭṭaka, Legendre described the method as `very ingenious’ as late as in 1798. We have seen that a profound aspect of the kuṭṭaka method for solving Step II is that it contains the seeds of the idea of “descent” and that, Bachet’s rediscovery of the method influences, in a subtle way, the emergence of the “descent” principle. Step II is of interest in computational number theory and we have seen that it is a fundamental step in cryptography.

The myriad significances of the kuṭṭaka (more of which we will see in the next section) indicate that it is more subtle than what its description as being “essentially the Euclidean algorithm” would indicate.

The equation d=ay-bx, expressing the GCD d as a linear combination of integers a and b, is sometimes known as `Bézout’s identity’; perhaps Āryabhaṭa’s identity would have been more appropriate historically.

Kuṭṭaka, simultaneous remainders and simultaneous indeterminate equations

The `Chinese Remainder’ problem seeks to find an integer N which when divided by a_1 leaves a remainder c_1, when divided by a_2 leaves a remainder c_2, and so on. In the modern language of congruences, the problem is to find an integer x satisfying the simultaneous congruences

\[\begin{equation}\label{CRT}
x \equiv c_i ({\rm mod}\, a_i), 1 \le i \le r.
\end{equation}\]However, even in India, it is not so well-known that Āryabhaṭa, Bhāskara I and Brahmagupta explicitly state the above `Chinese Remainder’ problem of `simultaneous remainders’ and describe algorithms to solve it using kuṭṭaka.

Āryabhaṭa describes the case r=2; Bhāskara I and Brahmagupta discuss the general case with examples. The a_i are termed variously as cheda, bhājak or bhāgahāra (divisors) and the c_i are called agra or śeṣa (remainders).

The connection between the kuṭṭaka problem of finding integer solutions of the linear indeterminate equation and the problem of finding simultaneous remainders is easy to see. If N is a number being sought in the latter problem then in the above notation,

N=a_1y_1+c_1=a_2y_2+c_2= \cdots =a_ky_k+c_k.Applying kuṭṭaka first on the equation a_1y_1+c_1=a_2y_2+c_2, one can get a minimum positive as well as the general solution for (y_1,y_2). The general solution is in terms of a single parameter z_3; both the expressions a_1y_1+c_1 and a_2y_2+c_2 take the form t_3z_3+s_3 for some t_3, s_3. The process is repeated with t_3z_3+s_3=a_3y_3+c_3, and so on.

Ancient Indian mathematicians also solve simultaneous linear indeterminate equations of the type

\[
b_1y-a_1x_1=c_1, b_2y-a_2x_2=c_2, …, b_ry-a_rx_r=c_r
\]under the obvious consistency conditions. They name the system saṃśliṣṭa kuṭṭaka (conjunct pulverizer).

Note that the special case b_1=b_2=\cdots b_r=1 is the problem of simultaneous reminders stated above (what is known as the `Chinese Remainder’ problem) which has been discussed by Āryabhaṭa (for r=2), Bhāskara I and Brahmagupta. It is not clear from the brief verses of Āryabhaṭa whether he considers only the case b_1=b_2=1 or the more general case; the commentary on Āryabhaṭa’s verses by Parameśvara (c. 1430 CE) explains the general case itself. The generalised conjunct pulverizer is considered by later mathematicians like Mahāvīra (850 CE), Āryabhaṭa II (950 CE), Śrīpati (1039 CE) and Bhāskara II (1150 CE).

Bhāskara I uses the term niragra-kuṭṭākāra (non-residual pulverizer) for the problem of solving simultaneous linear indeterminate equations; and the term sāgra-kuṭṭākāra (residual pulverizer) for the equivalent problem of solving the problem of simultaneous remainders. These problems have applications in computations involving periodic events – for instance, in calendar-making and in the determination of the time of occurrence of a certain alignment of celestial bodies (e.g., the determination of the time of eclipses).

To see the connection, note that if k events E_1, … E_k occur regularly with periods a_1, …, a_k with E_i happening at times c_i, c_i+a_i, c_i+2a_i,…, then the k events occur simultaneously at time N where N is a number which, when divided by each a_i, (1 \leq i \leq k), leaves remainder c_i. The problem and its algorithmic solutions have numerous applications in ancient Indian astronomy; we shall quote an application to astronomy in the next section. An astronomy problem based on a linear indeterminate equation is called graha-kuṭṭākāra (planetary pulverizer).

Below we quote a few historical problems on simultaneous remainders that are to be solved using kuṭṭaka.

Example 1 (Bhāskara I, c. 600) “Tell me at once, O mathematician, that number which leaves unity as remainder when divided by any of the numbers from 2 to 6 but is exactly divisible by 7.” [Ans : 301]

Example 2 (Mahāvīra, c. 850) “Five heaps of fruits added with two fruits were divided equally between nine travellers; six heaps added with four fruits were divided amongst eight; four heaps increased by one fruit were divided amongst seven. Tell the number of fruits in each heap.” [(Least) Ans : 194]

The `Chinese Remainder’ problem (2) is stated and its solution worked out in detail in the treatise Shushu Jiuzhang (Mathematical Treatise in Nine Sections), dated 1247 CE, by the thirteenth century Chinese mathematician Qin Jiushao⁵ (1202–1261). However, isolated numerical examples occur in earlier Chinese works. We quote two below.

Example 3 (Sun Tsu, c. 300) “There are certain things whose number is unknown. If we count them by threes, we have two left over; by fives, we have three left over; and by sevens, two are left over. How many things are there?” [(Least) Ans : 23]

Example 4 (Yih-hiang, c. 700) “Find the number of completed units of work, the same number of units to be performed by each of four sets of 2, 3, 6, 12 workmen, such that after certain whole days’ work, there remains 1, 2, 5, 5 units not completed by the respective sets.” [(Least) Ans : 17]

While lecturing on the kuṭṭaka to students of Class 11 in an INSPIRE Science Camp in the summer of 2014, the present author had set the following exercise:

Exercise 1. In a science camp of 210 students, creativity tests were planned in each of the subjects Mathematics, Physics and Chemistry. The students were to attempt the questions in groups of 5, 6 and 7 respectively. Unfortunately, a few students could not turn up due to unforeseen circumstances and it was found that dividing students into groups of 5, 6 and 7 would leave remainders 2, 1 and 5 respectively. Using kuṭṭaka, a professor of mathematics quickly realised how many students were present and suggested how the students could be grouped if uniformity in number was to be insisted. What was the total number of students present?

While lecturing on the `Chinese Remainder Theorem’ in 2018, the present author had set the following exercise, a slightly modified version of a problem discussed in the classic An Introduction to the Theory of Numbers (Chapter VIII, Section 8.1, p. 95) by G.H. Hardy and E.M. Wright:

Exercise 2. (Hardy-Wright) From Monday, 1 January 2018, six professors begin two-year courses of lectures on Monday, Tuesday, Wednesday, Thursday, Friday, and Saturday. They announce their intention of lecturing at intervals of two, three, four, one, six, and five days respectively. However, no lecture is to take place on a Sunday and a professor would omit his lecture if it falls on a Sunday. For instance, the dates of the lectures of the first professor were January 1,3,5,9,11,13, … (omitting 7 January, a Sunday). What will be the date of the first Sunday on which all six professors find themselves compelled to omit a lecture?

In 1801, C.F. Gauss made the following now-standard formulation of the `Chinese Remainder Theorem’:

Theorem 1. If m=m_1m_2… m_n, where m_1, …, m_n are pairwise coprime, and if

a_i \equiv 0 ({\rm mod}\, \frac{m}{m_i}), a_i \equiv 1 ({\rm mod}\, m_i), 1 \le i \le n,then x=a_1r_1+ \cdots +a_nr_n is a solution of x \equiv r_i ({\rm mod}\, m_i), 1 \le i \le n, and other solutions differ by a multiple of m.

When m_1, …, m_n need not be pairwise coprime, one has the following more general, but less elegant, statement; with other notation as above.

Theorem 2. Assume that each r_i-r_j is divisible by the GCD of m_i and m_j. Let \ell be the LCM of m_1, …, m_n and express \ell as a product \ell = {\ell}_1 \cdots {\ell}_n such that \ell_i are pairwise coprime (includes 1) and each \ell_i divides m_i. If b_i \equiv 0 ({\rm mod }\, \frac{\ell}{\ell_i}), b_i \equiv 1 ({\rm mod }\, \ell_i), 1 \le i \le n, then x=b_1r_1+ \cdots +b_nr_n is a solution of x \equiv r_i ({\rm mod }\, m_i), 1 \le i \le n, and other solutions differ by a multiple of \ell.

Readers familiar with basic ring theory (say, at M.Sc. Mathematics level) would have seen the following generalisation of Theorem 1:

Theorem 3. Let R be a commutative ring with unity and I_1, I_2, …, I_n be pairwise comaximal ideals of R (i.e. I_j + I_{\ell}=R for every pair j, \ell with j \ne \ell). Then the natural map

\phi: R \longrightarrow R/I_1 \times \cdots \times R/I_n,defined by \phi (x)= (x \, {\rm mod }\, I_1, … , x \, {\rm mod }\, I_n), is surjective.

That is, given any c_1, … c_n \in R, there exists x \in R such that x - c_j \in I_j for every j, 1 \le j \le n.

The above version of `Chinese Remainder Theorem’ is a basic result of ring theory of fundamental importance in Commutative Algebra, Algebraic Number Theory and Algebraic Geometry. Taking R to be the polynomial ring k[X], one can see that the result gives a framework for Lagrange Interpolation:

To see this, one has to take I_j to be the ideal (X-a_j){\mathbb Q}[X], where \mathbb Q denotes the field of rational numbers and {\mathbb Q}[X] the polynomial ring.

More discussions and applications on the linear indeterminate (or Diophantine) equation, the problem of simultaneous remainders (or Chinese Remainder problem), results on congruences and related topics can be found in Silverman’s book (see [27]). Unfortunately, the author is not aware of the contributions of Āryabhaṭa and other Indian mathematicians on the topics and the book does not mention the Indian works. The treatment in [27] is informal; a formal treatment can be found in [19].

An application in Indian astronomy

Indian astronomers solve equations of the type ay-bx=c, with large integer coefficients a,b. We try to give the reader some idea how large integers arise in their works on astronomy. A student-friendly introduction to standard terms in astronomy that we use in this section has been given in [8] and [9].

Ancient Indian astronomers conceive of long time-periods (yuga, kalpa, etc) in which the five visible planets along with the Sun and the Moon are estimated to execute `integral’ numbers of revolutions starting from a time when the above celestial objects are `in conjunction’ – that is, all are on the great circle of the `celestial sphere’ passing through the `vernal equinox’ and the pole of the `ecliptic’. For instance, by the estimates in Āryabhaṭīya (see [26], [p 6]), a yuga of 4320000 “sidereal years” has 1577917500 civil days and, during this period, Saturn and Mars perform, respectively, 146564 and 2296824 revolutions. The significance of yuga, with such long periods, has been discussed in [10].

Ancient astronomers must have used the kuṭṭaka for estimating the moments when the visible planets (and the Sun and the Moon) are in conjunction. It is perhaps significant that Āryabhaṭa, who begins his treatise by mentioning the time of commencement of the current yuga and the number of revolutions performed by each planet in a yuga, ends his mathematics chapter by describing the kuṭṭaka.

We now give one example of a typical application of the kuṭṭaka in Indian astronomy texts. Let D denote the number of civil days in a certain epoch and N the number of revolutions performed by a planet in that epoch. Let y denote the ahargaṇa, the number of mean civil days elapsed since the beginning of the specified epoch up to a given day; and let x denote the bhagaṇa, the number of complete revolutions performed by a planet during this period. Note that x is the quotient obtained by dividing the product yN by D.

The kuṭṭaka is applied to determine the ahargaṇa y and the bhagaṇa x from the residue r=yN-xD (D and N are known constants). For instance, in Laghu-Bhāskarīya (chapter 8, verse 17), Bhāskara I gives certain algebraic conditions satisfied by the residues of Saturn and Mars (on a given day) and asks the reader to calculate the ahargaṇa (for that day) and the bhagaṇa of Saturn and Mars (see [24], [p. 99]).

Since Saturn performs 146564 complete revolutions in 1577917500 days, on dividing the two integers by the common factor 4, we get an intermediary epoch of 394479375 days in which Saturn performs 36641 revolutions. Taking D=394479375 and N=36641, one gets the sthira-kuṭṭaka 36641Y-394479375X=1 from which the solutions for y and x can be obtained depending on r. In the case of Mars, one gets the sthira-kuṭṭaka 191402Y-131493125X=1.

Āryabhaṭa’s verses on Kuṭṭaka

References

• [1] S.K. Abhyankar (ed), Bījagaṇita of Bhāskarācārya, Bhaskaracharya Pratishthana (1980).
• [2] A.K. Bag, The Method of Integral Solution of Indeterminate Equations of the Type: by=ax \pm c in Ancient and Medieval India, Indian J. History of Science, 12(1) (1977), p 1–16.
• [3] S. Barnard and J. Child, Higher Algebra, Macmillan (1936); Indian reprint (2001).
• [4] F. Cajori, History of Mathematics, AMS Chelsea (2000); originally Macmillan 1893; 1919.
• [5] B. Datta, The Science of the Sulba, University of Calcutta (1932); reprint (1991).
• [6] B. Datta and A.N. Singh, History of Hindu Mathematics Part II, Asia Publishing House (1962); reprinted by Bharatiya Kala Prakashan (2004); originally Motilal Banarasidass (1938).
• [7] L.E. Dickson, History of the Theory of Numbers Vol II, Chelsea Publishing Co. NY (1952); reprinted AMS Chelsea (1999); originally Carnegie Institute Publ., 256 (1920).
• [8] A.K. Dutta, Āryabhaṭa and Axial Rotation of Earth Part 1: The Khagola (The Celestial Sphere), Resonance 11(3), 51–68, (March 2006).
• [9] A.K. Dutta, Āryabhaṭa and Axial Rotation of Earth Part 2: The Nakṣatra Dina (Sidereal Day), Resonance 11(4), 56–74, (April 2006).
• [10] A.K. Dutta, Āryabhaṭa and Axial Rotation of Earth Part 3: A Brief History, Resonance 11(5), 58–72, (May 2006).
• [11] A.K. Dutta, The bhāvanā in Mathematics, Bhāvanā 1(1), 13–19 (January 2017).
• [12] A.K. Dutta, Mathematics in Ancient India Part 1: Geometry in Vedic and Sūtra Literature, Bhāvanā, 6(1), 23–33, (January 2022).
• [13] A.K. Dutta, Mathematics in Ancient India Part 2: Computational Mathematics in Vedic and Sūtra Literature, Bhāvanā, 6(2), 43–61, (April 2022).
• [14] A.K. Dutta, Mathematics in Ancient India Part 3: The Decimal Notation and some Arithmetic Algorithms, Bhāvanā, 6(3), 50–67, (July 2022).
• [15] A.K. Dutta, Mathematics in Ancient India Part 4: Principles of Arithmetic, Bhāvanā, 6(4), 36–49, (October 2022).
• [16] J.R. Goldman, The Queen of Mathematics: A Historically Motivated Guide to Number Theory, A.K. Peters (1997).
• [17] H.S. Hall and S.R. Knight, Higher Algebra, Macmillan (1960); originally published in 1887; Indian reprint available.
• [18] A. Keller (ed), Expounding the Mathematical Seed Vol 1, A Translation of Bhāskara I on the Mathematical Chapter of the Āryabhaṭīya, Birkhauser (2006).
• [19] I. Niven, H.S. Zuckerman and H.L. Montgomery, An Introduction to The Theory of Numbers, Wiley India (2013).
• [20] V.B. Panicker (ed), Bhaskaracharya’s Bijaganitham, Bharatiya Vidya Bhavan (2006).
• [21] K.S. Patwardhan, S.A. Naimpally and S.L. Singh (ed), Līlāvatī of Bhāskarācārya, Motilal Banarasidass (2001).
• [22] A. Padmanabha Rao, Bhāskarācārya’s Līlāvatī Part II, Chinmaya International Foundation Shodha Sansthan, Ernakulam (2014).
• [23] K.S. Shukla (ed), Mahā-Bhāskarīya, Bhāskara I and his works Part II, Lucknow University (1960).
• [24] K.S. Shukla (ed), Laghu-Bhāskarīya, Bhāskara I and his works Part III, Lucknow University (1963).
• [25] K.S. Shukla (ed), Āryabhaṭīya of Āryabhaṭa with the commentary of Bhāskara I and Someśvara, Indian National Science Academy (1976).
• [26] K.S. Shukla and K.V. Sarma (ed), Āryabhaṭīya of Āryabhaṭa, Indian National Science Academy (1976).
• [27] J.H. Silverman, A Friendly Introduction to Number Theory, Third edition, Pearson (2006); Indian reprint published by Dorling Kindersley (2009).
• [28] A. Weil, Number Theory: An approach through history from Hammurapi to Legendre, Birkhauser (1984).

Footnotes

1. Isabella G. Bashmakova (1921–2005) was a prominent Russian historian of mathematics. A retrospective of her life and work was published in Historia Mathematica 8, 389–392, (1981), on the occasion of her 60th birthday. A more detailed and updated account, with bibliography of her writings, was published in Historia Mathematica 29, 370–382, (2002), on her 80th birth anniversary. ↩
2. p. 11 in http://www.muslimheritage.com/uploads/Arabic\_Sources\_Jordanus.pdf. ↩
3. The statement that x^n+y^n=z^n has no positive integral solution if n>2. ↩
4. The result and the complete proof is given in books on elementary number theory; for [16], [pp. 16–17]; [19], [pp. 237–239]. ↩
5. Also known as Ch’in Chiu-Shao. ↩