• Foundation
  • About 16 min
  • 5 practice questions

Āryabhaṭa's division method and what makes a good algorithm

Replace repeated subtraction by the remainder (m mod n), find the gcd quickly by the long-division method, explain why it is correct, and summarise the ideas of algorithms, from basic steps to efficiency.

If something looks wrong, please tell us.

By the end of this lesson you can

  • Compute m mod n and use the rule gcd(m, n) = gcd(n, m mod n).
  • Find a gcd by the long-division method in a few steps.
  • Summarise what every algorithm needs: basic steps, repetition, conditions, a correctness argument and an efficiency analysis.

In the last lesson, gcd(101, 2) took about 50 subtractions of 2. But subtracting 2 from 101 until you cannot subtract any more simply leaves the remainder when 101 is divided by 2. Division does all those subtractions in one go. Indian mathematicians used exactly this idea: Āryabhaṭa's Āryabhaṭīya (499 CE) finds a gcd by repeated division, using the place-value numerals.

The remainder: m mod n

m mod n means the remainder when m is divided by n. For example, 29 mod 6 = 5 (since 29 = 6 × 4 + 5), 40 mod 8 = 0 (since 40 = 8 × 5), and 7 mod 10 = 7 (since 7 = 10 × 0 + 7).

If m ≥ n > 0, then gcd(m, n) = gcd(n, m mod n). Keep dividing the last divisor by the last remainder; when the remainder is 0, the last divisor is the gcd.

Why it is correct. If m = q × n + r, then r = m − q × n, which is m with n subtracted q times. Each subtraction keeps the common divisors the same (last lesson), so m, n and n, r have the same common divisors. Directly: if d divides m and n, it divides m − q × n = r; if d divides n and r, it divides q × n + r = m.

The improved algorithm

  1. If m < n, swap the numbers and compute gcd(n, m) instead.
  2. If n = 0, report m as the answer.
  3. Otherwise, replace the problem by gcd(n, m mod n) and go back to step 1.

Only step 3 has changed. For gcd(101, 2): 101 mod 2 = 1, giving gcd(2, 1); then 2 mod 1 = 0, giving gcd(1, 0); answer 1. Two reductions instead of about 50.

Worked example 1: gcd(252, 198) by long division

Each divisor becomes the next dividend; each remainder becomes the next divisor
DividendDivisorQuotientRemainderProblem becomes
252198154gcd(198, 54)
19854336gcd(54, 36)
5436118gcd(36, 18)
361820gcd(18, 0)

Working: 252 = 198 × 1 + 54; 198 = 54 × 3 + 36 (54 × 3 = 162, 198 − 162 = 36); 54 = 36 × 1 + 18; 36 = 18 × 2 + 0. The remainder is 0, so gcd(252, 198) = 18. Check by prime factors: 252 = 2² × 3² × 7 and 198 = 2 × 3² × 11, so the gcd is 2 × 3² = 18.

Worked example 2: gcd(1071, 462)

1071 = 462 × 2 + 147 (462 × 2 = 924, 1071 − 924 = 147) → gcd(462, 147).
462 = 147 × 3 + 21 (147 × 3 = 441, 462 − 441 = 21) → gcd(147, 21).
147 = 21 × 7 + 0 → gcd(21, 0).
Answer: gcd(1071, 462) = 21. Check: 1071 = 21 × 51 and 462 = 21 × 22, and 51 = 3 × 17 and 22 = 2 × 11 share no factor.

The subtraction method needs 12 reductions for this pair; division needs only 3.

It can be shown that the number of division steps grows only with the number of digits of the numbers, just as column addition beat counting dots. The proof is left for higher classes.

Where the word 'algorithm' comes from

The Persian scholar Muḥammad ibn Mūsā al-Khwārizmī (about 780–850 CE), working in Baghdad, learnt the Indian place-value numerals and wrote, around 820 CE, a book explaining them and the Indian methods for adding, subtracting, multiplying and dividing. His original is lost, but a 12th-century Latin translation spread these methods across Europe. The Latin form of his name, Algoritmi, gave the word 'algorism' for these Indian methods of calculation, which later became 'algorithm', now meaning any well-defined step-by-step procedure.

What makes a good algorithm

An algorithm

  • Basic steps
    • Things we can already do, e.g. add two digits, test whether j divides n
  • Repetition
    • Do a step for each j from 1 to n
    • Repeat until a stopping rule is met
  • Conditions
    • Do a step only if something is true
  • Correctness
    • An argument that it always gives the right answer
  • Efficiency
    • How the number of steps grows with the size of the input

Key takeaways

  • m mod n is the remainder when m is divided by n; it replaces many subtractions at once.
  • gcd(m, n) = gcd(n, m mod n); stop when the remainder is 0, and the last divisor is the gcd.
  • This division method, found in Āryabhaṭa's work, needs a number of steps that grows with the digits, not the value.
  • The word 'algorithm' comes from al-Khwārizmī, who wrote about Indian methods of calculation.

Check your understanding

  1. 1. What is 47 mod 6?

    1. 7
    2. 5
    3. 1
    4. 41
    Show answer

    Answer: B. 47 = 6 × 7 + 5, so the remainder is 5. The quotient 7 is not the remainder.

  2. 2. Using gcd(m, n) = gcd(n, m mod n), what does gcd(252, 198) become after one step?

    1. gcd(198, 54)
    2. gcd(198, 252)
    3. gcd(54, 36)
    4. gcd(252, 54)
    Show answer

    Answer: A. 252 = 198 × 1 + 54, so 252 mod 198 = 54 and the problem becomes gcd(198, 54). gcd(54, 36) comes one step later.

  3. 3. Find gcd(1071, 462) by the division method.

    1. 7
    2. 147
    3. 21
    4. 3
    Show answer

    Answer: C. 1071 mod 462 = 147, then 462 mod 147 = 21, then 147 mod 21 = 0. The last non-zero divisor is 21, so gcd(1071, 462) = 21. Check: 1071 = 21 × 51 and 462 = 21 × 22.

  4. 4. Why is the division method much faster than the subtraction method for gcd(101, 2)?

    1. It uses smaller numbers from the start
    2. It does not need a stopping rule
    3. It finds the answer by guessing
    4. One division gives the same remainder as about 50 subtractions of 2
    Show answer

    Answer: D. Subtracting 2 from 101 again and again ends at the remainder 1 after 50 subtractions. 101 mod 2 = 1 gives that in one step, so the whole calculation takes 2 reductions: gcd(2, 1), then gcd(1, 0).

  5. 5. The word 'algorithm' comes from the name of which scholar?

    1. Euclid
    2. Āryabhaṭa
    3. Al-Khwārizmī
    4. Brahmagupta
    Show answer

    Answer: C. Al-Khwārizmī wrote about the Indian numerals and methods of calculation around 820 CE. The Latin form of his name, Algoritmi, gave 'algorism' and then 'algorithm'.

Privacy · Terms · Refunds · Delivery