# The kuttaka method: Aryabhata's extended Euclidean algorithm, in Python

> Aryabhata's kuttaka (499 CE) from the Sanskrit verses to tested Python, with a worked example from the 629 CE commentary and the RSA modular inverse.

Published 2026-11-01, 17 min read, Ancient algorithms

Source: https://prasad.tech/blog/kuttaka-method-extended-euclidean-algorithm/

---


Every RSA key pair needs a modular inverse: a private exponent `d` such that `e * d` leaves remainder 1 when divided by `phi(n)`. Libraries compute it with the extended Euclidean algorithm. Aryabhata's kuttaka, from 499 CE, does the same job: it solves `ax + c = by` in whole numbers by repeated division. His commentator Bhaskara I named it "the pulverizer".

I wanted to read the method in Aryabhata's own words. So I took his 2 verses, translated them word by word, checked my reading against published translations, and wrote the method in Python with tests ([code on GitHub](https://github.com/prasadus92/ancient-algorithms)). This is the first post in [Ancient algorithms, implemented](/ancient-algorithms/).

## What the kuttaka method solves

Here is the second example in Bhaskara I's commentary on the verses, written in 629 CE:

> Which number leaves 5 when divided by 12, and 7 when divided by 31?

Call the number `N`. Then `N = 12y + 5` and `N = 31x + 7` for some whole numbers `x` and `y`. Setting the 2 equal and moving terms around:

$$31x + 2 = 12y$$

This is a linear indeterminate equation: 1 equation, 2 unknowns, and we want whole-number answers. Mathematicians also call it a linear Diophantine equation. In modern notation the same question is a pair of congruences, `N ≡ 5 (mod 12)` and `N ≡ 7 (mod 31)`, which is the 2-divisor case of the Chinese remainder theorem.

The answer is 317.

Astronomers needed this. Indian astronomy counted time in long cycles: in the system Bhaskara I uses, the sun makes 4,320,000 revolutions in 1,577,917,500 days. If you know how far the sun is into its current revolution, the kuttaka gives the smallest day count that fits. Bhaskara I works this example: a leftover of 82,500 gives 199,066 days and 545 completed revolutions. Adding 210,389 days at a time gives the other day counts that fit. I ran his numbers through the code below and got the same answer. The first quotient in that division is 365, because 1,577,917,500 days divided by 4,320,000 revolutions is 365.26 days per year.

## Who wrote it, and when

- **Aryabhata**, in the *Aryabhatiya*. He says he was 23 years old when 3,600 years of the current age had passed, which is usually taken as the date of the text, 499 CE. The mathematics chapter, the Ganitapada, has 33 verses. The kuttaka is the last 2. Aryabhata gives the rule with no name and no example.
- **Bhaskara I**, in his commentary on the *Aryabhatiya*, written in 629 CE. He explains each word of the verses, calls the method *kuttakara*, and works 26 numbered examples under these 2 verses. 4 of them are the remainder problem above, 2 drop the remainders, and 20 come from astronomy. His is the oldest surviving explanation of the verses.
- **Brahmagupta**, in the *Brahmasphutasiddhanta* of 628 CE. His chapter 18 is named after the kuttaka, and his rule is worded close to Aryabhata's. Clark (1930) calls it the closest parallel.

The name *kuttaka* comes from a root meaning to crush or grind. The usual reading is that the method grinds large numbers down into small ones, which matches what it does: each division hands you a smaller version of the same problem.

## The verses

Aryabhata wrote in the *arya* meter. The text below follows K. S. Shukla's 1976 critical edition, as transcribed in GRETIL. GRETIL prints the words split apart; I have joined them with the usual sound changes (sandhi) so the lines read as they would be recited.

<p lang="sa">अधिकाग्रभागहारं छिन्द्यादूनाग्रभागहारेण ।<br />शेषपरस्परभक्तं मतिगुणमग्रान्तरे क्षिप्तम् ॥ ३२ ॥</p>

<p lang="sa">अधउपरिगुणितमन्त्ययुगूनाग्रच्छेदभाजिते शेषम् ।<br />अधिकाग्रच्छेदगुणं द्विच्छेदाग्रमधिकाग्रयुतम् ॥ ३३ ॥</p>

<span lang="sa-Latn">*adhikāgrabhāgahāraṃ chindyād ūnāgrabhāgahāreṇa |*<br />
*śeṣaparasparabhaktaṃ matiguṇam agrāntare kṣiptam || 32 ||*</span>

<span lang="sa-Latn">*adhaupariguṇitam antyayug ūnāgracchedabhājite śeṣam |*<br />
*adhikāgracchedaguṇaṃ dvicchedāgram adhikāgrayutam || 33 ||*</span>

### Word by word

5 words recur. *Agra* means remainder. *Bhagahara* and *cheda* both mean divisor. *Adhika* is greater and *una* is smaller. So *adhikagra-bhagahara* is "the divisor whose remainder is the greater one".

| Sanskrit | Parts | Meaning |
|---|---|---|
| *adhikāgrabhāgahāraṃ* | adhika + agra + bhāgahāra | the divisor of the greater remainder (object) |
| *chindyāt* | chid, "to cut" | one should divide |
| *ūnāgrabhāgahāreṇa* | ūna + agra + bhāgahāra | by the divisor of the smaller remainder |
| *śeṣaparasparabhaktaṃ* | śeṣa + paraspara + bhakta | the remainder, divided mutually (with that divisor) |
| *matiguṇam* | mati + guṇa | multiplied by a chosen number. Bhaskara I glosses *mati* as *svabuddhi*, "your own judgment" |
| *agrāntare* | agra + antara | in the difference of the remainders |
| *kṣiptam* | kṣip, "to throw" | thrown in, added |
| *adhaupariguṇitam* | adhas + upari + guṇita | the upper multiplied by the lower |
| *antyayug* | antya + yuj | joined with the last |
| *ūnāgracchedabhājite* | ūna + agra + cheda + bhājita | when divided by the divisor of the smaller remainder |
| *śeṣam* | | the remainder |
| *adhikāgracchedaguṇaṃ* | adhika + agra + cheda + guṇa | multiplied by the divisor of the greater remainder |
| *dvicchedāgram* | dvi + cheda + agra | the remainder-number for both divisors |
| *adhikāgrayutam* | adhika + agra + yuta | with the greater remainder added |

### My translation

> **32.** Divide the divisor of the greater remainder by the divisor of the smaller remainder. Divide the remainder and the divisor by each other in turn. Multiply by a number you choose, so that, with the difference of the remainders thrown in, it divides exactly.
>
> **33.** Multiply the upper by the lower and add the last. Divide by the divisor of the smaller remainder. Multiply the remainder by the divisor of the greater remainder and add the greater remainder. That is the number for both divisors.

The second half of verse 32 leaves words out, and I have filled them in the way Bhaskara I explains them. Compare W. E. Clark's 1930 translation, which also supplies the missing words in brackets:

> Divide the divisor which gives the greater agra by the divisor which gives the smaller agra. The remainder is reciprocally divided (that is to say, the remainder becomes the divisor of the original divisor, and the remainder of this second division becomes the divisor of the second divisor, etc.). (The quotients are placed below each other in the so-called chain.) (The last remainder) is multiplied by an assumed number and added to the difference between the agras. Multiply the penultimate number by the number above it and add the number which is below it. (Continue this process to the top of the chain.) Divide (the top number) by the divisor which gives the smaller agra. Multiply the remainder by the divisor which gives the greater agra. Add this product to the greater agra. The result is the number which will satisfy both divisors and both agras.
>
> W. E. Clark, *The Aryabhatiya of Aryabhata* (1930), p. 43

For a modern translation, see K. S. Shukla and K. V. Sarma's 1976 edition of the *Aryabhatiya*. Agathe Keller's *Expounding the Mathematical Seed* (2006) translates Bhaskara I's whole commentary on this chapter, and Kim Plofker's *Mathematics in India* (2009) places the rule in the wider history.

## What the verses leave open

The verses never say:

1. **How far to carry the divisions.** Clark notes that nothing in the text says whether to stop when a remainder reaches 1, or after an even number of steps.
2. **What the chosen number multiplies.** *Matigunam*, "multiplied by the chosen number", has no stated object. Clark supplies "the last remainder", following Brahmagupta's wording, and mentions a second reading that supplies "the quotient". He rejects G. R. Kaye's earlier translation of the phrase outright, because it drops the word for "multiplied".
3. **Whether to add or subtract.** The verse says *kshiptam*, "thrown in". Bhaskara I says to add the difference when the number of quotients is even and subtract it when it is odd, and he says this comes from the unbroken tradition of teachers. The rule is correct, as the derivation below shows. It comes from the commentary tradition, outside the verses.

The repo version follows Bhaskara I on all 3 points, because his commentary is the oldest surviving explanation and his examples let me check every step. The short version in this post always divides down to a residue of 1.

## Working the example on paper

Back to the number that leaves 5 with 12 and 7 with 31. The greater remainder is 7, so 31 is the divisor of the greater remainder and 12 is the divisor of the smaller.

**Step 1. Divide 31 by 12.** The remainder is 7. Bhaskara I says the quotient is of no use, so drop it. Write 7 above and 12 below.

**Step 2. Divide them by each other in turn.**

- 12 divided by 7 is 1, remainder 5.
- 7 divided by 5 is 1, remainder 2.

That gives quotients 1 and 1, and residues 2 above and 5 below. Bhaskara I stops here, because the numbers are small enough to see the next step in your head.

**Step 3. Choose the mati.** There are 2 quotients, an even count, so add the difference of the remainders, which is 7 - 5 = 2. Find a number `m` such that `2m + 2` divides exactly by 5. `m = 4` works: `2 × 4 + 2 = 10`, and 10 divided by 5 is 2.

**Step 4. Build the column and fold it up.** Write the quotients, then the mati, then the quotient of that exact division:

<figure class="dg" aria-label="Bhaskara I's column for the 317 example. The column holds the quotients 1 and 1, the mati 4, and 2, the quotient of the exact division. The first fold replaces the second 1 with 1 times 4 plus 2, which is 6. The second fold replaces the top 1 with 1 times 6 plus 4, which is 10.">
<div class="dg-canvas">
</div>
<figcaption>Each fold multiplies a number by the one below it and adds the one below that: "multiply the upper by the lower and add the last". The bottom row drops off after each fold, and the top of the column ends at 10.</figcaption>
</figure>

**Step 5. Finish.** Divide 10 by 12, the divisor of the smaller remainder: the remainder is 10. Multiply by 31 to get 310. Add the greater remainder, 7, to get **317**.

Check: 317 = 26 × 12 + 5, and 317 = 10 × 31 + 7. Bhaskara I gets the same 10, 310 and 317.

## Why it works

Step 1 is reducing modulo 12. We want `31x + 7` to leave 5 with 12, which means `31x + 2` divides by 12. Since 31 leaves 7 with 12, that is the same as asking for `7x + 2` to divide by 12:

$$7x + 2 = 12y$$

Each division in step 2 swaps this for a smaller equation of the same shape. Since 12 = 1 × 7 + 5, substitute and collect the multiples of 7:

$$7x + 2 = (7 + 5)y \quad\Longrightarrow\quad 7(x - y) + 2 = 5y$$

Name `u = x - y`. The equation becomes `5y - 2 = 7u`: smaller numbers, the 2 sides have traded places, and the sign of the 2 has flipped. Do it once more with 7 = 1 × 5 + 2, and name `v = y - u`:

$$5y - 2 = (5 + 2)u \quad\Longrightarrow\quad 2u + 2 = 5v$$

Now the sign is back to plus. This is the source of the add-when-even, subtract-when-odd rule: every division flips the sign once.

The last equation is small enough to solve by looking at it, which is all the mati is: `u = 4, v = 2`. Then undo the substitutions from the bottom up:

$$y = u + v = 1 \times 4 + 2 = 6, \qquad x = y + u = 1 \times 6 + 4 = 10$$

Each line is "the quotient times the number below, plus the one below that". The 1s are the quotients from step 2. The column in step 4 is a written record of this back-substitution, and that is why it works for any numbers, as long as the 2 divisors share no factor the difference of remainders lacks.[^gcd]

The mati is what makes stopping early possible. Carry the divisions until a residue is 1 and the last equation reads `u ± c = r*v`, so `u` is fixed by `c` and no search is needed. Stop sooner and you guess a small number instead. Bhaskara I stops sooner whenever the numbers are small.

## The Python

This is the method above in Python. It divides until a residue reaches 1, so the mati follows directly with no trial.

```python
from math import gcd


def kuttaka(a: int, b: int, c: int) -> int:
    """Smallest x >= 0 with a*x + c divisible by b."""
    g = gcd(a, b)
    if c % g:
        raise ValueError("no whole-number solution")
    a, b, c = a // g, b // g, c // g  # remove the common factor first
    if b == 1:
        return 0
    residues = [b, a % b]  # the first quotient is dropped
    quotients = []
    while residues[-1] > 1:  # divide each residue by the next, in turn
        q, r = divmod(residues[-2], residues[-1])
        quotients.append(q)
        residues.append(r)
    n = len(quotients)
    sign = 1 if n % 2 == 0 else -1  # even count: add c, odd count: subtract
    lower = residues[n]  # the latest residue is 1, so the mati needs no search
    mati = (-sign * c) % lower
    column = quotients + [mati, (mati + sign * c) // lower]
    for i in range(n - 1, -1, -1):  # multiply the upper by the lower, add the last
        column[i] = column[i] * column[i + 1] + column[i + 2]
    return column[0] % b


def two_remainders(r1: int, d1: int, r2: int, d2: int) -> int:
    """Smallest N >= 0 leaving r1 with divisor d1 and r2 with divisor d2."""
    if r1 < r2:  # start from the divisor with the greater remainder
        r1, d1, r2, d2 = r2, d2, r1, d1
    return d1 * kuttaka(d1, d2, r1 - r2) + r1


print(two_remainders(5, 12, 7, 31))  # 317
print(two_remainders(1, 5, 2, 7))  # 16
print(kuttaka(17, 3120, -1))  # 2753
```

The [repo version](https://github.com/prasadus92/ancient-algorithms/blob/main/src/ancient_algorithms/kuttaka.py) does more. With `trace=True` it records every fold of the column so you can print the working, it accepts a `stop_after` argument to stop early and search for the mati as Bhaskara I does, and it folds 3 or more remainders together. The tests check:

- Bhaskara I's 4 examples of the remainder problem: 16, 317, 85 for 3 divisors, and 301 for divisors 2 to 7, which share factors;
- his 2 examples without remainders, 9 and 17;
- the columns for 3 of his examples, step by step, against the commentary;
- his astronomical example 22, 199,066 days;
- the RSA textbook inverse, 2753;
- property tests with Hypothesis: on random inputs, the kuttaka's answer always satisfies the equation, matches the incremental Chinese remainder construction (`crt`), and equals `pow(a, -1, m)` for inverses of numbers up to 10<sup>30</sup>.

## Against the extended Euclidean algorithm

The extended Euclidean algorithm finds whole numbers `s` and `t` with `a*s + b*t = gcd(a, b)`. Here is the usual iterative version:

```python
def extended_gcd(a: int, b: int) -> tuple[int, int, int]:
    old_r, r, old_s, s, old_t, t = a, b, 1, 0, 0, 1
    while r:
        q = old_r // r
        old_r, r = r, old_r - q * r
        old_s, s = s, old_s - q * s
        old_t, t = t, old_t - q * t
    return old_r, old_s, old_t
```

Both methods perform the same divisions with the same quotients. The difference is the direction of the bookkeeping:

- **The extended Euclidean algorithm** updates the coefficients `s` and `t` at each division and throws the quotients away. It needs a fixed amount of memory.
- **The kuttaka** keeps every quotient in the column, then folds the column from the bottom once the divisions stop. It needs memory for the whole column, and in return it lets a person stop early and finish with a guess.

The fold is the same recurrence that builds the convergents of a continued fraction, run from the bottom of the column instead of the top.

I counted the divisions each method needs to compute a modular inverse, averaged over 100 random moduli of each size:

| Modulus size | Kuttaka divisions | Extended Euclid divisions |
|---|---|---|
| 16 bits | 8.6 | 9.6 |
| 256 bits | 148.9 | 149.9 |
| 2,048 bits | 1,194.7 | 1,195.7 |

The kuttaka count is 1 lower because it stops when a residue reaches 1 and settles the last step with the mati, where the Euclidean loop does 1 more division to reach 0. The work is the same. In pure Python 3.13 on an Apple M1 Pro, the repo version took about 3 times as long as my extended Euclid at 16 bits, the same at 256 bits, and about a fifth less at 2,048 bits. Python's built-in `pow(a, -1, m)`, which runs in C, was faster than both.[^timing]

## RSA and the modular inverse

RSA picks 2 primes, multiplies them to get the modulus, and needs a private exponent `d` that undoes the public exponent `e`. With the small textbook numbers `p = 61` and `q = 53`:

- `n = 61 × 53 = 3233`
- `phi(n) = 60 × 52 = 3120`
- `e = 17`
- `d` is the number with `17d - 1` divisible by 3120

That last line is the kuttaka with `c = -1`:

```python
>>> kuttaka(17, 3120, -1)
2753
>>> 17 * 2753 % 3120
1
>>> pow(17, -1, 3120)
2753
```

Real key generation does the same thing with 2,048-bit or larger numbers.[^lambda] The same chain of divisions produces `d`.

## Parallels and lineage

These are the connections I can support from sources:

- **Euclid's *Elements*, Book VII, propositions 1 and 2 (c. 300 BCE).** Repeated subtraction to test whether 2 numbers share a factor and to find their greatest common measure. It is the same chain of divisions. Euclid states no procedure for solving `ax + c = by`.
- **Sunzi Suanjing (China, 3rd to 5th century CE).** Asks for a number leaving 2 with 3, 3 with 5 and 2 with 7, and gives the answer 23 by a recipe with the multipliers 70, 21 and 15. The recipe does not explain how to find such multipliers for other divisors.
- **Qin Jiushao, *Mathematical Treatise in Nine Sections* (1247).** Gives a general method for the remainder problem.
- **Brahmagupta (628) and Bhaskara II (12th century).** Carry the kuttaka forward in Sanskrit. Bhaskara II uses it inside the *chakravala* method for Pell's equation, a later post in this series.
- **Claude-Gaspard Bachet de Meziriac (1624).** Solves `ax - by = ±1` in the second edition of his *Problemes plaisants et delectables*. André Weil remarked that Bachet did not see the connection with Euclid's Book VII.

What is debated or unknown:

- **The exact reading of verse 32.** Translators disagree on the second of the 3 open points above.
- **How much is already in Euclid.** Andrew Granville (2024) argues that the identity `a*m - b*n = gcd(a, b)`, the heart of the extended algorithm, is present in Euclid's Book VII once his arguments are read in context, as statements about lengths.
- **Transmission between India and China.** Aryabhata, Sunzi and Qin all solve versions of the remainder problem. The sources I have read document no route by which the method passed between them, and I treat them as separate developments.
- **Earlier sources.** Aryabhata cites none for this rule. The *Aryabhatiya* is the earliest surviving Sanskrit text that states it.

## Key takeaways

- The kuttaka is in 2 verses of the *Aryabhatiya* (499 CE). Bhaskara I's commentary (629 CE) explains it and supplies the rules the verses leave out.
- It solves `ax + c = by` in whole numbers, which covers the 2-divisor remainder problem and the modular inverse.
- Each division produces a smaller equation of the same shape with the sign flipped, and the column records the back-substitution that undoes them. That is why it works.
- It runs the same chain of divisions as the extended Euclidean algorithm, keeps the quotients in a column, and builds the answer from the bottom of that column.
- The code, tests and benchmarks are in [ancient-algorithms](https://github.com/prasadus92/ancient-algorithms). Next in the series: Madhava's series for pi, with his correction terms.

## Sources

- Aryabhata, *Aryabhatiya*, with the commentary of Bhaskara I and Someshvara, critically edited by K. S. Shukla. Indian National Science Academy, 1976. E-text: [GRETIL](https://gretil.sub.uni-goettingen.de/gretil/corpustei/sa_AryabhaTa-AryabhaTIya-comm.xml).
- K. S. Shukla and K. V. Sarma, *Aryabhatiya of Aryabhata*, critically edited with translation. Indian National Science Academy, 1976.
- W. E. Clark, [*The Aryabhatiya of Aryabhata*](https://archive.org/details/TheAryabhatiyaOfAryabhata). University of Chicago Press, 1930. Pages 42 to 50 cover verses 32 and 33.
- A. Keller, *Expounding the Mathematical Seed*, 2 volumes. Birkhäuser, 2006.
- K. Plofker, *Mathematics in India*. Princeton University Press, 2009.
- R. L. Rivest, A. Shamir and L. Adleman, "A method for obtaining digital signatures and public-key cryptosystems". *Communications of the ACM* 21(2), 1978.
- A. Granville, ["It is not Bézout's identity"](https://arxiv.org/abs/2406.15642), arXiv 2406.15642, 2024. On Euclid, and on Bachet with Weil's remark.

[^gcd]: If the divisors share a factor `g`, a solution exists only when `g` divides the difference of the remainders. Bhaskara I divides everything by the common factor first, and so does the code. His fourth example, divisors 2 to 7 with answer 301, needs this.

[^timing]: Timings vary by machine and Python version, and these come from 1 modulus per size. The division counts are exact for the moduli tested. The benchmark script is in the repo as `benchmarks/kuttaka_vs_euclid.py`.

[^lambda]: Current standards compute `d` modulo `lcm(p - 1, q - 1)` rather than `phi(n)`. The inverse is found the same way.

---

## Common questions

**What is the kuttaka method?**

The kuttaka (pulverizer) solves linear indeterminate equations: it finds whole numbers x and y with a*x + c = b*y, or a number that leaves given remainders with 2 divisors. Aryabhata stated it in the Aryabhatiya, Ganitapada 32 and 33, in 499 CE. Bhaskara I's commentary of 629 CE explains it with worked examples and names it.

**Is the kuttaka the same as the extended Euclidean algorithm?**

Both perform the same chain of divisions and solve the same equations. The kuttaka writes the quotients in a column and rebuilds the answer from the bottom up, and it lets you stop dividing early by choosing a small multiplier. The extended Euclidean algorithm carries the coefficients forward as it divides. Run to the end, the kuttaka does 1 division fewer, because it stops when a remainder reaches 1.

**Did Aryabhata discover the Chinese remainder theorem?**

Aryabhata's verses give a general procedure for the remainder problem with 2 divisors, and Bhaskara I applies it to 3 or more. The Chinese text Sunzi Suanjing (3rd to 5th century) poses a remainder problem with a worked recipe, and Qin Jiushao gave a general method in 1247. The sources cited in this post document no transmission of the method between India and China.

**How do you compute a modular inverse with the kuttaka?**

Ask for x with a*x - 1 divisible by m, which is the kuttaka with the constant -1. For the RSA textbook example, e = 17 and phi(n) = 3120, it returns d = 2753, the same as Python's pow(17, -1, 3120).
