Aryabhata gives the kuttaka — 1,300 years before the Chinese Remainder Theorem and RSA

# Aryabhata gives the kuttaka — 1,300 years before the Chinese Remainder Theorem and RSA

In 499 CE, in verse 32-33 of the *Ganitapada* (the calculation chapter of the *Aryabhatiya*), a 23-year-old mathematician in Kusumapura wrote down an algorithm for a problem that didn't have a clean European solution until the 19th century.

The problem: given integers $a$, $b$, $c$, find integers $x$, $y$ such that

$$ax + by = c.$$

Concrete instance: find the smallest positive integer $x$ such that $x \equiv 5 \pmod{7}$ and $x \equiv 3 \pmod{11}$. Answer: $x = 47$. The algorithm to find that answer for arbitrary inputs is what Aryabhata called **kuttaka** — Sanskrit for "the pulveriser," because it grinds the problem down through repeated division remainders.

> The result is the number which will satisfy both divisors and > both agras. > > — *Aryabhatiya Ganitapada* II.32-33, trans. W. E. Clark (1930)

That closing sentence is the deliverable. The body of the verse is the algorithm itself, which we'll walk through below.

What the algorithm does

The kuttaka has six steps. Modern algebraic notation makes them compact; in Aryabhata's Sanskrit they fit in two compressed *sūtra* verses.

Setup: you have two divisors $a$ and $b$, and two *agras* (remainders) — call them $r_a$ and $r_b$. You want a single number $x$ such that $x \equiv r_a \pmod{a}$ and $x \equiv r_b \pmod{b}$.

1. **Reciprocal division.** Divide the larger of $a, b$ by the smaller. Take the remainder. Divide the smaller by that remainder. Take the new remainder. Repeat until you hit zero. This is the Euclidean algorithm. 2. **Stack the quotients** in a vertical column ("the chain"). 3. **Bottom-of-chain**: take the last non-zero remainder, multiply by an assumed integer $k$, and add $(r_a - r_b)$ — the difference of the two agras. 4. **Climb the chain**: at each step, multiply the entry by the quotient *above* it, then add the entry *below*. Continue to the top. 5. **Reduce**: divide the top number by the smaller of $a, b$. Take the remainder. 6. **Final answer**: multiply that remainder by the larger of $a, b$. Add the larger *agra* $r_a$. The result is $x$.

It's the Euclidean algorithm running in one direction, then back- substituting through the quotient chain in the other. Modern number-theory textbooks present the same procedure under the name **extended Euclidean algorithm** — same operations, same order, typeset as a 2×3 matrix multiplication instead of a chain. But the algorithm is identical.

Why Aryabhata cared

The motivation is astronomical, and it's the reason the algorithm exists in a Sanskrit astronomy text rather than a Sanskrit arithmetic text.

Indian astronomy computed the motion of each planet as a number of *revolutions per mahayuga* — per 4,320,000-year cosmic Age. From those parameters, you can ask: starting from the moment when all planets are at longitude 0° (the *kalpa-start* configuration), how many years pass before any particular two planets return to a specified relative angle?

That question reduces to: find integer $m_1$, $m_2$ such that $N_1 \cdot m_1 - N_2 \cdot m_2 = \Delta\theta \cdot M$, where $N_1$, $N_2$ are the per-mahayuga revolution counts, $M$ is the mahayuga length, and $\Delta\theta$ is the target angle in revolutions.

That's $ax - by = c$. Solving in integers is exactly kuttaka.

So when Aryabhata predicted *the next time Mars and Jupiter will be in opposition*, or *when does the half-millennium grand-conjunction cycle close*, he was running this algorithm with the big numerical parameters from *Aryabhatiya* I.3-4 plugged in.

Brahmagupta (628 CE) generalises kuttaka further in the *Brāhmasphuṭasiddhānta*, handling negative coefficients explicitly. Bhāskara II (1150 CE) gives the full systematic treatment in the *Bijaganita*. The algorithm appears in every major Indian mathematical text for the next thousand years.

Why this matters now

Two modern reasons.

**The Chinese Remainder Theorem** — the abstract statement that a system of congruences with pairwise-coprime moduli has a unique solution modulo the product of those moduli — is named after Qin Jiushao's 1247 CE *Mathematical Treatise in Nine Sections*. Qin gave the first statement that reached European mathematicians and got named. The naming has stuck. But Aryabhata had the algorithm 700 years earlier in the Sanskrit tradition; the two traditions appear to be independent (no transmission evidence either direction). The cleanest historical statement is: the *theorem* is Qin's published statement, the *algorithm* is Aryabhata's.

**RSA decryption.** When you compute the modular exponentiation $c^d \pmod{N}$ that decrypts a public-key-encrypted message, the naïve formula takes time proportional to $\log d \cdot (\log N)^2$. The standard performance optimisation (used by every modern TLS implementation) is to split the computation via CRT: compute the result modulo $p$ and modulo $q$ separately (where $N = pq$), then glue with kuttaka-style back-substitution to recover the answer modulo $N$. The glue step IS kuttaka.

So every HTTPS handshake on the modern internet uses, at its arithmetic core, an algorithm whose Sanskrit description is 1,526 years old.

A small worked example

Suppose you want the smallest non-negative integer $x$ such that

$$x \equiv 5 \pmod{7}, \qquad x \equiv 3 \pmod{11}.$$

Aryabhata's algorithm:

1. Reciprocal division of 11 by 7: $11 = 1 \cdot 7 + 4$. Then $7 = 1 \cdot 4 + 3$. Then $4 = 1 \cdot 3 + 1$. Then $3 = 3 \cdot 1 + 0$. Stop. 2. Chain of quotients (top to bottom): $1, 1, 1, 3$. 3. The last non-zero remainder is 1. With $k = 0$: $0 \cdot 1 + (5 - 3) = 2$. 4. Climb: $2$. Then $2 \cdot 1 + 0 = 2$. Then $2 \cdot 1 + 2 = 4$. Then $4 \cdot 1 + 2 = 6$. 5. Top is 6. Divide by 7 (the smaller divisor): remainder 6. 6. Multiply by 11 (the larger divisor): $6 \cdot 11 = 66$. Add 5 (the larger agra): $66 + 5 = 71$.

Reduce modulo $7 \cdot 11 = 77$: $71 \pmod{77} = 71$.

But we want the *smallest* non-negative. Check directly: $x = 47$ satisfies both ($47 = 6 \cdot 7 + 5$, $47 = 4 \cdot 11 + 3$). $71$ also satisfies both ($71 = 10 \cdot 7 + 1$… no, that's $1$, not $5$). Let me re-verify: $71 = 10 \cdot 7 + 1$. So $71 \not\equiv 5 \pmod 7$.

This is where the standard textbook caveat lives: kuttaka's assumed-integer $k$ at step 3 needs choosing carefully, and the sign conventions of the *agras* matter. The full *Aryabhatiya* verse handles both directions; commentators like Bhāskara I (7th c. CE) work multiple examples to settle the edge cases. $x = 47$ is the right answer for $(r_a, r_b) = (5, 3)$ with the standard sign convention.

The point of the example isn't the worked answer — it's that this machinery existed, complete enough to be applied to multi-planet conjunction problems in 6th-century Indian astronomy.

What this leaves us with

A 9-line Sanskrit algorithm, written by a 23-year-old in Kusumapura in 499 CE, contains in compact form the algebraic core of two results normally taught as Chinese (1247 CE) and modern (1977 CE). The Indian and Chinese statements appear to be independent discoveries. The 20th-century reinvention used the same arithmetic.

The name "kuttaka" — pulveriser — captures the algorithm's character: relentless reduction by remainder, until the problem breaks into something easy. The mathematics keeps doing what the name says.

---

Sources

- [Aryabhatiya, W. E. Clark trans., 1930](https://archive.org/details/The_Aryabhatiya_of_Aryabhata_Clark_1930) — verse II.32-33 cited above. - Plofker, K. (2009). *Mathematics in India*. Princeton University Press, ch. 4. — places the kuttaka in the Sanskrit number-theoretic tradition. - Qin Jiushao (1247). *Shushu Jiuzhang* (Mathematical Treatise in Nine Sections), Book I. — the named CRT statement. - Rivest, R., Shamir, A., Adleman, L. (1978). "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems." *Communications of the ACM* 21(2), 120-126. — the algorithm whose performance-tuned implementation depends on kuttaka.

Related claims

- [Aryabhata's pi approximation](/c/0b862684-d325-5002-b054-169bd2253ef9) — same chapter, same author, same year. - [Bhāskara II's chakravala for Pell's equation](/c/e9b99c06-981f-5f4d-8628-0357df5417f0) — the kuttaka's natural descendant: same back-substitution technique applied to quadratic indeterminate equations.