Āryabhaṭa's division method

Subtracting 2 from 99 again and again just finds the remainder when 99 is divided by 2. So jump straight there: replace gcd(m, n) by gcd(n, m mod n), where m mod n is the remainder (17 mod 5 = 2; 33 mod 7 = 5).

Why it is allowed: m = qn + r, so a number divides both m and n exactly when it divides both n and r.

Now gcd(99, 2) → gcd(2, 1) → gcd(1, 0) = 1: two steps instead of about 49.

This is the long-division method in Āryabhaṭa's Āryabhaṭīya (499 CE): divide, then divide the divisor by the remainder, until the remainder is 0. The last divisor is the gcd:

• 60 ÷ 16 leaves 12;
• 16 ÷ 12 leaves 4;
• 12 ÷ 4 leaves 0;
• so gcd(60, 16) = 4.

Its number of steps grows only with the number of digits, not with the size of the numbers. That is why it is still used today.

Where the word comes from. 'Algorithm' comes from Al-Khwārizmī (780–850 CE), whose book on Indian numerals, translated into Latin, spread Indian arithmetic through Europe.