On this page
Aryabhata was born in 476 and finished the Aryabhatiya in 499, writing in Kusumapura when Pataliputra was the capital, according to his MacTutor biography at the University of St Andrews. Most of the book is astronomy, and we covered its place value, pi and spinning Earth in our piece on Aryabhata's Aryabhatiya. This post is about a few lines in its mathematics section that solve a puzzle you can state in one line: find whole numbers x and y with ax − by = c.
What is the kuttaka method?
Kuttaka is a step-by-step method for finding integer solutions of linear equations such as ax − by = c, where a, b and c are known integers (Kuttaka, Wikipedia). Such an equation is called indeterminate: one equation with two unknowns has a whole family of answers, and the job is to find the ones that are whole numbers.
The method sits in verses 32 and 33 of the Ganitapada, the mathematics section of the Aryabhatiya, in a form so compressed that later readers needed help with it (Kuttaka, Wikipedia). Bhaskara I, writing in the 600s, explained it in detail with examples from astronomy in his commentary and gave the method its name.
Why is it called the pulveriser?
The Sanskrit word kuttaka means to pulverise (St Andrews). The name describes what happens: you take two large numbers and grind them down by repeated division until they are so small the answer is obvious. Then you climb back up.
How do you solve a kuttaka problem step by step?
Here is a classic puzzle, the one worked on the Wikipedia Kuttaka page: find a number N that leaves remainder 15 when divided by 29 and remainder 19 when divided by 45. Write N = 29x + 15 = 45y + 19. Rearranged, that is 29x − 45y = 4.
Step 1: grind down. Divide the larger number by the smaller, then the divisor by the remainder, and repeat.
45 = 1 × 29 + 16
29 = 1 × 16 + 13
16 = 1 × 13 + 3
13 = 4 × 3 + 1
The last remainder is 1, so the HCF of 29 and 45 is 1 and the puzzle has answers.
Step 2: climb back. Start from the last line and substitute each remainder upwards.
1 = 13 − 4 × 3
1 = 13 − 4 × (16 − 13) = 5 × 13 − 4 × 16
1 = 5 × (29 − 16) − 4 × 16 = 5 × 29 − 9 × 16
1 = 5 × 29 − 9 × (45 − 29) = 14 × 29 − 9 × 45
So 29 × 14 − 45 × 9 = 1. You can check it: 406 − 405 = 1.
Step 3: scale up. Multiply by 4 to get 29 × 56 − 45 × 36 = 4.
Step 4: make it small. Taking 45 off x and 29 off y together changes nothing, because 29 × 45 − 45 × 29 = 0. That gives x = 11 and y = 7. Then N = 29 × 11 + 15 = 334, and also 45 × 7 + 19 = 334. Adding 1305 (that is, 29 × 45) gives the next answers: 1639, 2944 and so on.
This is the modern way to set out the steps; the verses and Bhaskara I's commentary present them in their own form.
How is kuttaka related to Euclid's algorithm for HCF?
Step 1 is Euclid's algorithm, which is described in Book 7 of Euclid's Elements, written around 300 BC (Euclidean algorithm, Wikipedia). The St Andrews biography says Aryabhata's method is essentially the use of the Euclidean algorithm to find the highest common factor. If you have found an HCF this way, our guide to real numbers in Class 10, with HCF and LCM covers the same ground.
The difference is what you do afterwards. Euclid stops at the HCF. Kuttaka climbs back to write c using a and b, which today is called the extended Euclidean algorithm; kuttaka can be considered a precursor of it (Kuttaka, Wikipedia). For a different ancient tradition of number puzzles, read about Diophantus and the Arithmetica.
When does ax − by = c have no whole-number solution?
If the HCF of a and b does not divide c, there is no solution, because both ax and by are multiples of the HCF, so their difference must be too (Euclidean algorithm, Wikipedia). Try 6x − 9y = 4: the left side is always a multiple of 3, and 4 is not, so you can stop before you start.
A quick checklist for any kuttaka problem:
Find the HCF of a and b by repeated division; if it does not divide c, stop.
Keep every division line; the climb back uses all of them.
Multiply by c divided by the HCF, then reduce x and y together.
Substitute to check.
The climb back is where a sign is easiest to drop. The Fermi Problem Library has worked problems with a step-by-step solver that explains the reasoning rather than printing an answer, so you can compare each line with yours. If HCF itself feels shaky, the Fermi Concept Library gives every mathematics concept its own lesson.
Try it yourself next: find a number that leaves remainder 2 when divided by 7 and remainder 3 when divided by 11.
