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 katex is not defined are given by katex is not defined.

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 katex is not defined such that katex is not defined. In this case, a solution katex is not defined can be obtained by inspection. But there are other solutions like katex is not defined. 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 katex is not defined 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 katex is not defined has no nonzero integral solution when katex is not defined. 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 katex is not defined algebraic equations in more than katex is not defined 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 katex is not defined 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 (katex is not defined and katex is not defined), 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 katex is not defined square bricks of length katex is not defined unit and katex is not defined square bricks of length katex is not defined unit, with katex is not defined. Then, expressed in algebraic notation for our convenience, the altar-specifications amount to finding integers katex is not defined 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 katex is not defined, namely katex is not defined and katex is not defined. The Baudhāyana Śulba-sūtra prescribes making three types of square bricks of lengths katex is not defined and katex is not defined units and then placing 9 bricks of length katex is not defined unit and 12 bricks of length katex is not defined unit in the first, third and fifth layers; and 16 bricks of length katex is not defined unit and 5 bricks of length katex is not defined 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 katex is not defined 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 katex is not defined and the length of each diagonal katex is not defined are all integers (or rational numbers), i.e., katex is not defined are integral (or rational) triples satisfying the famous equation katex is not defined. 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 katex is not defined satisfy katex is not defined (see [5], [Chapter XIV]). Recall that his method implicitly involves the formula
katex is not definedthat is,
katex is not definedWhen katex is not defined are squares, say katex is not defined, we get the relation

katex is not definedThe 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

katex is not defined(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 katex is not defined 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 katex is not defined 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 katex is not defined is the GCD of katex is not defined and katex is not defined, then the kuṭṭaka shows how to express katex is not defined as a linear combination katex is not defined.

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 katex is not defined and katex is not defined are relatively prime integers, then one can find a least integral multiple of katex is not defined which exceeds an integer multiple of katex is not defined by a given integer katex is not defined (i.e., one can find integers katex is not defined such that katex is not defined). 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 katex is not defined, 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 katex is not defined. 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 katex is not defined to be positive integers, then any linear indeterminate equation in two variables is of the form katex is not defined or katex is not defined. The concrete applications in ancient Indian astronomy require the determination of all `positive’ integral solutions of equations of the type katex is not defined, where katex is not defined 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 katex is not defined 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 katex is not defined is thus visualised by ancient Indians in the form katex is not defined. The quantities katex is not defined 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 katex is not defined or katex is not defined so as to ensure that the interpolator katex is not defined comes with a positive sign. Almost all ancient Indian writers observe, in some form, that the equation katex is not defined will have integral solutions only if katex is not defined is divisible by the GCD (greatest common divisor) of katex is not defined and katex is not defined.

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 Pikatex is not definedgalācārya’s brilliant algorithm for computing katex is not defined.

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 katex is not defined (katex is not defined), 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 katex is not defined 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 katex is not defined reduces to katex is not defined.

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 katex is not defined and katex is not defined being coprime – a property which is potentially useful.

Another subtle reduction of Āryabhaṭa II, applicable in case there is a common factor between katex is not defined and katex is not defined or between katex is not defined and katex is not defined, further reduces the size of the coefficients of katex is not defined and katex is not defined.

Let katex is not defined, katex is not defined, katex is not defined and katex is not defined. Then Āryabhaṭa II, and his successors like Bhāskara II, observe that the problem of solving katex is not defined reduces to the problem of solving katex is not defined: if katex is not defined is an integral solution of the latter, then katex is not defined is an integral solution of the original equation.

For instance, the problem of solving katex is not defined (cited by Bhāskara II) reduces to solving katex is not defined. Once one obtains the solution katex is not defined of the reduced equation katex is not defined by the main algorithm (in this case, one can also get it easily by inspection!), one immediately gets the solution katex is not defined for the original equation katex is not defined.

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 katex is not defined and katex is not defined are positive, if katex is not defined are pairs of positive integers satisfying katex is not defined, then katex is not defined if and only if katex is not defined. Therefore, one can talk about a “minimum positive integral solution” katex is not defined.

Now suppose that katex is not defined is a positive integral solution of katex is not defined. From katex is not defined, one first finds the minimum positive integral solution katex is not defined. Dividing katex is not defined and katex is not defined by katex is not defined and katex is not defined respectively, we have katex is not defined and katex is not defined for some whole numbers katex is not defined such that katex is not defined and katex is not defined.

If katex is not defined, then katex is not defined is clearly a solution of katex is not defined; in fact, it is the minimum positive integral solution (proof is easy).

If katex is not defined, then it can be seen that katex is not defined when we consider the equation katex is not defined; and katex is not defined when we deal with katex is not defined. The minimum positive integral solutions in the two cases are katex is not defined and katex is not defined 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 katex is not defined is a minimum positive integral solution of katex is not defined, then Bhāskara I and his successors describe the general positive integral solution as katex is not defined where katex is not defined is a positive integer.

To see this, first note that if katex is not defined, then katex is not defined.

Conversely, suppose katex is not defined. We also have katex is not defined. Subtracting, we get

katex is not definedAs katex is not defined are coprime, we have katex is not defined divides katex is not defined and katex is not defined divides katex is not defined.

Thus, katex is not defined is an integer. Hence, katex is not defined and katex is not defined for some integer katex is not defined.

The above arguments also show that if katex is not defined is any integral solution of katex is not defined, then the general integral solution is given by katex is not defined, katex is not defined where katex is not defined is any integer.

Preliminary reduction 3: reduce to the case katex is not defined

Third, it is clearly enough to solve an equation of the type katex is not defined; for, if katex is not defined, then katex is not defined.

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 katex is not defined, are often such that the coefficients katex is not defined are the same in several equations but the interpolator katex is not defined 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: katex is not defined

Some ancient Indian authors also show that we can reduce to the case katex is not defined. This step is achieved through two different methods.

The later method corresponds to the modern approach: if katex is not defined, think of the equation as katex is not defined rather than katex is not defined.

But earlier writers like Bhāskara I, who already have to arrange the equation katex is not defined so as to have only positive coefficients, use the following device when katex is not defined: Let katex is not defined where katex is not defined. Then the original equation transforms into the equation katex is not defined (where katex is not defined) which is of the desired form. If katex is not defined is a solution of katex is not defined, then katex is not defined is a solution of katex is not defined.

We shall henceforth assume katex is not defined 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 katex is not defined. 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 katex is not defined, 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 katex is not defined; one could have taken katex is not defined for any katex is not defined and katex is not defined; for instance, katex is not defined.

Can we make use of this observation that it is easy to solve katex is not defined in integers if one of the coefficients of katex is not defined is one?

An idea: can we try to make a change of variables katex is not defined so that the equation katex is not defined becomes an equation of the form katex is not defined?

Can we do it through a sequence of change of variables katex is not defined, 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.

katex is not defined.

Substituting, we have

katex is not defined, i.e., latex]7(y-x) +3y =1[/latex].

Thus, the original problem reduces to solving:

katex is not defined, where katex is not defined, i.e., katex is not defined.

Thus, if we can find out katex is not defined, we shall know katex is not defined. But the new pair of coefficients katex is not defined is smaller than the earlier katex is not defined.

We continue the process.

katex is not defined.

katex is not defined.

The problem reduces to solving:

katex is not defined, where katex is not defined, i.e., katex is not defined.

As the coefficient of katex is not defined is one, we are through. Put katex is not defined. 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 katex is not defined: katex is not defined.

How do we achieve this? We break the larger coefficient katex is not defined with the hammer of the smaller katex is not defined 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 katex is not defined and katex is not defined and note down the intermediate quantities. To facilitate our theoretical understanding, we write them here in the form of successive divisions. Here, katex is not defined 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 katex is not defined, the next and crucial step in the kuṭṭaka is a reversal.

Define quantities katex is not defined by backward induction as follows: first define katex is not defined and katex is not defined to be whole numbers satisfying the relation katex is not defined.

Thus, if katex is not defined is odd, one can simply take katex is not defined and katex is not defined; if katex is not defined is even, one can take katex is not defined and katex is not defined.

Now define katex is not defined by katex is not defined. For facilitating the computation of katex is not defined, the Indians construct convenient tables called vallī. As will be clear from subsequent discussions, the numbers katex is not defined satisfy katex is not defined; thus katex is not defined is a solution of the equation katex is not defined.

For instance, for the equation katex is not defined, we first obtain the katex is not defined‘s as follows:

$$\begin{align*} 26&= 3 \times 7 + 5.\\ 7&= 1 \times 5 + 2.\\ 5&= 2 \times 2 + 1. \end{align*}$$ Thus, here, katex is not defined; katex is not defined.

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, katex is not defined.

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

For katex is not defined, 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 katex is not defined by katex is not defined, then katex is not defined by katex is not defined and finally katex is not defined by katex is not defined.

Bhāskara I explains that one need not continue the repeated division till the stage katex is not defined. One can terminate at an intermediate stage katex is not defined if, having obtained katex is not defined, one can observe, by inspection, positive integers katex is not defined satisfying katex is not defined. One can then define katex is not defined recursively, as before, and obtain a solution of the equation katex is not defined.

For solving katex is not defined, one considers numbers katex is not defined (katex is not defined) and katex is not defined satisfying katex is not defined; the rest is as above. Or, one can take the approach of Bhāskara II: solve katex is not defined and use the fact that if katex is not defined is the minimum positive integral solution of katex is not defined, then katex is not defined is the minimum positive integral solution of katex is not defined.

To derive solutions of katex is not defined from the solution katex is not defined of katex is not defined, note that katex is not defined implies katex is not defined for all katex is not defined, i.e., katex is not defined for all katex is not defined. In particular, katex is not defined, i.e, katex is not defined.

Brahmagupta, Bhāskara II and Nārāyaṇa give similar rules for deriving integer solutions of katex is not defined (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 katex is not defined that we had earlier tried to illustrate through a numerical example. To fix our ideas, let us take the RHS to be katex is not defined. The key idea may be formulated as follows:

1. Assume the existence of a positive integral solution katex is not defined to the equation katex is not defined.
2. Then transform this equation in successive steps into equations with progressively smaller coefficients and solutions to eventually arrive at an equation katex is not defined with an obvious solution katex is not defined for any katex is not defined.
3. Then work backwards from this obvious solution katex is not defined of the reduced equation to determine the desired solution katex is not defined of the original equation.

To elaborate, assume that katex is not defined is a positive solution of the equation katex is not defined. Recall that we are assuming katex is not defined and katex is not defined are coprime.

If katex is not defined, then katex is not defined is a solution of katex is not defined. So we may further assume that katex is not defined. Then katex is not defined.

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

Recall the relation katex is not defined with katex is not defined. Each component of the pair katex is not defined is smaller than that of the pair katex is not defined.

Now one tries to transform the equation katex is not defined to get an equation with coefficients katex is not defined and katex is not defined. The relation katex is not defined leads to the relation katex is not defined.

Set katex is not defined. Then clearly katex is not defined and katex is not defined is a positive solution of the equation katex is not defined which is again a linear equation of the original form; but now the solution katex is not defined is coordinate-wise smaller than the original katex is not defined and, moreover, the coefficients (of the new equation) too have become smaller since katex is not defined and katex is not defined. The two pairs of solutions being linearly related, if one can determine the smaller pair katex is not defined, one can easily compute the original katex is not defined.

Denote katex is not defined by katex is not defined respectively. Proceeding as above (introducing katex is not defined, etc.), since katex is not defined (as per our earlier notation), one eventually arrives at the easily solvable equation katex is not defined. From this equation, one works backwards to arrive at the solution katex is not defined of the original equation katex is not defined.

For instance, in the example katex is not defined, the kuṭṭaka uses the fact that solving katex is not defined is equivalent to solving katex is not defined (where katex is not defined), which, in turn, is equivalent to solving katex is not defined (where katex is not defined); and the latter has the obvious positive integral solution katex is not defined.

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 katex is not defined. One proves that the equation katex is not defined has no positive integral solution. (Note that if katex is not defined does not have any positive integer solution, then katex is not defined cannot have any positive integer solution.)

The main idea of the proof is to assume the existence of a hypothetical positive integral solution katex is not defined; without loss of generality, one may assume that katex is not defined and katex is not defined are coprime and katex is not defined is even. Then katex is not defined for some positive integers katex is not defined; 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 katex is not defined with katex is not defined coprime positive integers and katex is not defined. But then, repeating the process, one gets an infinite chain (descent)

katex is not definedwhich is impossible! The contradiction proves that there does not exist any positive integral solution of katex is not defined.

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 katex is not defined) 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 katex is not defined is a positive integer coprime to katex is not defined. The problem of finding an integer katex is not defined satisfying the congruence problem katex is not defined (mod katex is not defined) is clearly equivalent to finding integers katex is not defined such that katex is not defined and hence can be solved by kuṭṭaka.

For readers familiar with the concept of ideals and quotient rings, if katex is not defined is the ring of integers, katex is not defined is a positive integer, and katex is not defined is a positive integer coprime to katex is not defined, then in the quotient ring katex is not defined, the image katex is not defined of katex is not defined is a unit (i.e., invertible) and the inverse can be explicitly computed by the kuṭṭaka.

We mention here a useful fact. Suppose katex is not defined is a solution of katex is not defined (mod katex is not defined). Then it can be seen that the congruence katex is not defined (mod katex is not defined) implies katex is not defined modulo katex is not defined. For instance, we have seen that katex is not defined is a solution of katex is not defined (mod katex is not defined). Therefore, the congruence katex is not defined (mod katex is not defined) implies katex is not defined modulo katex is not defined. 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 katex is not defined 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 katex is not defined, one computes quantities katex is not defined 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 katex is not defined, the authors construct sequences of numbers katex is not defined and katex is not defined 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 katex is not defined and katex is not defined (where katex is not defined is as before). Then it is asserted that katex is not defined, i.e., katex is not defined is a solution of one of the equations katex is not defined (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 katex is not defined; the quantities katex is not defined are the “quotients”, i.e., katex is not defined, and katex is not defined are the successive convergents (which are actually characterised by the above recurrence relations). The theory of continued fractions yields the identity katex is not defined. Since katex is not defined and katex is not defined, we have the relation katex is not defined.

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 katex is not defined, katex is not defined; katex is not defined, katex is not defined 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 katex is not defined.

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 katex is not defined for a fixed non-square positive integer katex is not defined. 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 katex is not defined 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 katex is not defined and encourages contemporary mathematicians to do so. While analyzing Brouncker’s solution to the equation katex is not defined, 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: katex is not defined. 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 katex is not defined (mod katex is not defined), so that the decoding function would be katex is not defined (mod katex is not defined). In the terminology of cryptography he used `shift cipher’ katex is not defined (mod katex is not defined) with `key’ katex is not defined; in the above example katex is not defined 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’ katex is not defined (mod katex is not defined) with keys katex is not defined, which we explain below.

First note that we call a transformation (or function) in one variable katex is not defined `linear’ if it is of the form katex is not defined and a `translation’ if it is of the form katex is not defined, where katex is not defined 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 katex is not defined. In a linear transformation, katex is not defined, i.e., the origin is preserved; in an affine transformation, the origin gets shifted by katex is not defined units.

In an `affine cipher’ katex is not defined (mod katex is not defined) with keys katex is not defined, if katex is not defined is the value attached to the letter to be coded, then its code will be katex is not defined (mod katex is not defined). Thus, if the keys are katex is not defined, and the letter E is to be coded, i.e., if katex is not defined, then the code for E will have value katex is not defined (mod katex is not defined); thus the code for E will be O.

The decoding algorithm will then be katex is not defined (mod katex is not defined), where katex is not defined is an integer such that katex is not defined (mod katex is not defined). As we noted before, the kuṭṭaka algorithm determines katex is not defined and mathematically, this is the only intricate computation involved in the entire procedure.

To see a numerical example, consider the coding function katex is not defined (mod katex is not defined) obtained by taking the keys katex is not defined. Since katex is not defined (mod katex is not defined), here katex is not defined so that katex is not defined. Thus the decoding function will be katex is not defined (mod katex is not defined). 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 katex is not defined:

1. Computation of the GCD katex is not defined of katex is not defined and katex is not defined.
2. Expression of katex is not defined as a linear combination of katex is not defined and katex is not defined.

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 katex is not defined 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 katex is not defined 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 katex is not defined and katex is not defined of katex is not defined with katex is not defined.

Formally, a Euclidean Domain is an integral domain katex is not defined on which there exists a (non-negative) integer-valued function katex is not defined on katex is not defined with katex is not defined such that given katex is not defined, there exist katex is not defined such that katex is not defined with either katex is not defined or katex is not defined. The ring of integers katex is not defined is a Euclidean Domain with katex is not defined.

A PID (Principal Ideal Domain) is an integral domain katex is not defined in which every ideal katex is not defined is principal, that is, every ideal katex is not defined is of the form katex is not defined for some katex is not defined. Note that if katex is not defined, then there exist katex is not defined such that katex is not defined. katex is not defined is a PID whereas the polynomial ring katex is not defined is not a PID, as the ideal katex is not defined is not principal.

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

(i) katex is not defined and katex is not defined for some katex is not defined, and

(ii) if katex is not defined is such that katex is not defined and katex is not defined for some katex is not defined, then katex is not defined for some katex is not defined.

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 katex is not defined and katex is not defined, Āryabhaṭa’s kuṭṭaka shows that the ideal generated by two non-zero elements katex is not defined and katex is not defined of a Euclidean Domain katex is not defined 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 katex is not defined, expressing the GCD katex is not defined as a linear combination of integers katex is not defined and katex is not defined, 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 katex is not defined which when divided by katex is not defined leaves a remainder katex is not defined, when divided by katex is not defined leaves a remainder katex is not defined, and so on. In the modern language of congruences, the problem is to find an integer katex is not defined 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 katex is not defined; Bhāskara I and Brahmagupta discuss the general case with examples. The katex is not defined are termed variously as cheda, bhājak or bhāgahāra (divisors) and the katex is not defined 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 katex is not defined is a number being sought in the latter problem then in the above notation,

katex is not definedApplying kuṭṭaka first on the equation katex is not defined, one can get a minimum positive as well as the general solution for katex is not defined. The general solution is in terms of a single parameter katex is not defined; both the expressions katex is not defined and katex is not defined take the form katex is not defined for some katex is not defined. The process is repeated with katex is not defined, 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 katex is not defined is the problem of simultaneous reminders stated above (what is known as the `Chinese Remainder’ problem) which has been discussed by Āryabhaṭa (for katex is not defined), Bhāskara I and Brahmagupta. It is not clear from the brief verses of Āryabhaṭa whether he considers only the case katex is not defined 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 katex is not defined events katex is not defined occur regularly with periods katex is not defined with katex is not defined happening at times katex is not defined, then the katex is not defined events occur simultaneously at time katex is not defined where katex is not defined is a number which, when divided by each katex is not defined, katex is not defined, leaves remainder katex is not defined. 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 katex is not defined, where katex is not defined are pairwise coprime, and if

katex is not definedthen katex is not defined is a solution of katex is not defined, katex is not defined, and other solutions differ by a multiple of katex is not defined.

When katex is not defined 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 katex is not defined is divisible by the GCD of katex is not defined and katex is not defined. Let katex is not defined be the LCM of katex is not defined and express katex is not defined as a product katex is not defined such that katex is not defined are pairwise coprime (includes 1) and each katex is not defined divides katex is not defined. If katex is not defined then katex is not defined is a solution of katex is not defined, katex is not defined, and other solutions differ by a multiple of katex is not defined.

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

Theorem 3. Let katex is not defined be a commutative ring with unity and katex is not defined be pairwise comaximal ideals of katex is not defined (i.e. katex is not defined for every pair katex is not defined with katex is not defined). Then the natural map

katex is not defineddefined by katex is not defined, is surjective.

That is, given any katex is not defined, there exists katex is not defined such that katex is not defined for every katex is not defined, katex is not defined.

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 katex is not defined to be the polynomial ring katex is not defined, one can see that the result gives a framework for Lagrange Interpolation:

To see this, one has to take katex is not defined to be the ideal katex is not defined, where katex is not defined denotes the field of rational numbers and katex is not defined 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 katex is not defined, with large integer coefficients katex is not defined. 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 katex is not defined denote the number of civil days in a certain epoch and katex is not defined the number of revolutions performed by a planet in that epoch. Let katex is not defined 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 katex is not defined denote the bhagaṇa, the number of complete revolutions performed by a planet during this period. Note that katex is not defined is the quotient obtained by dividing the product katex is not defined by katex is not defined.

The kuṭṭaka is applied to determine the ahargaṇa katex is not defined and the bhagaṇa katex is not defined from the residue katex is not defined (katex is not defined and katex is not defined 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 katex is not defined and katex is not defined, one gets the sthira-kuṭṭaka katex is not defined from which the solutions for katex is not defined and katex is not defined can be obtained depending on katex is not defined. In the case of Mars, one gets the sthira-kuṭṭaka katex is not defined.

Ā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: katex is not defined 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/Arabickatex is not definedSourceskatex is not definedJordanus.pdf.
3. The statement that katex is not defined has no positive integral solution if katex is not defined.
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.