MathsCBSE Class 9 · The World of Algorithms

GCD Algorithms: Euclid's Subtraction and Āryabhaṭa's Division

Q: Why does the division method always stop?

Because the remainder is smaller than the divisor, so the second number strictly decreases until it reaches 0.

Q: Does the order of m and n matter?

No. If m < n the first step simply swaps them.

Q: Is the gcd the same as the HCF?

Yes, they are two names for the greatest common divisor.

Updated 17 October 2026 · Fact-checked

The gcd (greatest common divisor, also called HCF) of two numbers can be found by listing divisors, by Euclid's subtraction method $\gcd(m, n) = \gcd(n, m - n)$, or by the faster division method $\gcd(m, n) = \gcd(n, m \bmod n)$. Each rule works because the common divisors of the old and the new pair are exactly the same. The division version needs very few steps even for big numbers.

Both methods keep the same common divisors and end at gcd 6, but the division method gets there in far fewer steps.

Illustration drawn for QuestionBuddy.

Understand Computing the GCD: Definition, Euclid's Subtraction and Āryabhaṭa's Division

*Note: this chapter of the textbook series is not listed in CBSE's Class 9 course structure for 2026-27, so check with your school whether it is examined. It develops the idea of an algorithm, which supports CBSE's computational-thinking goal.*

An algorithm is a precise, step-by-step procedure that gives the correct answer for every input of a given kind. For every algorithm we ask two questions: is it correct (does it always give the right answer?) and how much work does it need as the input grows?

GCD from the definition. The gcd of $m$ and $n$ is the largest number that divides both. A direct algorithm lists the divisors of $m$ and of $n$ , keeps the common ones and reports the largest. For $48$ and $18$ : divisors of $48$ are $1, 2, 3, 4, 6, 8, 12, 16, 24, 48$ ; of $18$ : $1, 2, 3, 6, 9, 18$ ; common divisors $1, 2, 3, 6$ ; so the gcd is $6$ . This is clearly correct, but it checks every number up to $m$ and $n$ , so the work grows with the size of the numbers.

Euclid's subtraction algorithm. *Key fact:* if $m \geq n$ , then $g cd (m, n) = g cd (n, m - n)$ . *Why:* if $d$ divides both $m$ and $n$ it divides $m - n$ (since $m - n = d (a - b)$ when $m = d a$ and $n = d b$ ), and if $d$ divides both $n$ and $m - n$ it divides their sum $m$ . The two pairs have exactly the same common divisors, so they have the same greatest one.

*The steps:* (1) if $m < n$ , swap them; (2) if $n = 0$ , the answer is $m$ ; (3) otherwise replace $(m, n)$ by $(n, m - n)$ and repeat. For $(60, 24)$ : $(60, 24) \to (24, 36) \to$ swap $(36, 24) \to (24, 12) \to (12, 12) \to (12, 0)$ , so the gcd is $12$ , in $4$ subtractions. It is correct but slow for numbers far apart: $g cd (99, 2)$ needs about $49$ subtractions.

Āryabhaṭa's division algorithm. Repeated subtraction of $n$ from $m$ ends with the remainder $m mod n$ , so one division does many subtractions at once: $g cd (m, n) = g cd (n, m mod n)$ . The steps are the same as Euclid's, except that step (3) uses the remainder. For $(1071, 462)$ : $1071 mod 462 = 147$ ; $462 mod 147 = 21$ ; $147 mod 21 = 0$ ; so the gcd is $21$ in only $3$ steps. The number of steps grows with the number of digits of the numbers, not with their size, just as column addition does.

Using the gcd. The lcm follows from $lcm (m, n) = \frac{m \times n}{g c d ( m , n )}$ : for $252$ and $105$ , $g cd = 21$ and $lcm = \frac{252 \times 105}{21} = 1260$ . Packing problems use the gcd: the largest square tile that exactly covers a floor $2160$ cm by $1260$ cm has side $g cd (2160, 1260) = 180$ cm, giving $12 \times 7 = 84$ tiles. For three numbers apply the gcd twice: $g cd (84, 126, 210) = g cd (g cd (84, 126), 210) = g cd (42, 210) = 42$ .

Scanning downwards. Another improvement of the definition-based method checks candidates from $min (m, n)$ down to $1$ and stops at the first common divisor: this is already the largest. For $(1000, 625)$ it checks $625, 624, \dots, 125$ , which is $501$ numbers, whereas the division method finishes in $4$ steps: $1000 mod 625 = 375$ , $625 mod 375 = 250$ , $375 mod 250 = 125$ , $250 mod 125 = 0$ .

How to present an algorithm answer. Write the input and output, list the numbered steps, run the example in a table (one row per step), state the stopping rule, and give a one-line reason why the rule keeps the gcd unchanged.

Computing the GCD: Definition, Euclid's Subtraction and Āryabhaṭa's Division: formulas to remember

Euclid's reduction: $g cd (m, n) = g cd (n, m - n), m \geq n$; Same common divisors.
Āryabhaṭa's reduction: $g cd (m, n) = g cd (n, m mod n)$; Many subtractions in one division.
Stopping rule: $g cd (m, 0) = m$; When the second number reaches 0.
Remainder notation: $m mod n = m - n ⌊ \frac{m}{n} ⌋$; Example: $17 mod 5 = 2$ .
lcm from gcd: $lcm (m, n) = \frac{mn}{g c d ( m , n )}$; Product of the two numbers divided by the gcd.
Three numbers: $g cd (a, b, c) = g cd (g cd (a, b), c)$; Apply the two-number rule twice.

How to solve Computing the GCD: Definition, Euclid's Subtraction and Āryabhaṭa's Division questions

Choose the algorithm, run it in a table and state the answer.

1Write the pair $(m, n)$ with $m \geq n$ (swap if needed).
2For the definition method, list the divisors of both numbers and pick the largest common one.
3For the subtraction method, replace $(m, n)$ by $(n, m - n)$ , swapping when the first number is smaller, until the second number is 0.
4For the division method, replace $(m, n)$ by $(n, m mod n)$ until the remainder is 0; the last non-zero number is the gcd.
5Count the steps and compare methods.
6Use the gcd for lcm, equal grouping and tiling problems.

Computing the GCD: Definition, Euclid's Subtraction and Āryabhaṭa's Division in real life

Each concept, met in an everyday situation. Read the situation, try the problem, then check the solution. The one-line hook is what to remember.

GCD for equal packing

Suppose a craft shop has ribbons of length 84 cm and 126 cm that are to be cut into pieces of the same greatest possible length with nothing left over.

Find the length of each piece and the number of pieces.

Try it first, then show the solutionSolution

Piece length $= g cd (84, 126)$ . $126 mod 84 = 42$ , $84 mod 42 = 0$ , so the gcd is $42$ cm.
Pieces: $\frac{84}{42} + \frac{126}{42} = 2 + 3 = 5$ .

Answer: Each piece is 42 cm long, and there are 5 pieces.

Memory hook: The greatest equal cut is the gcd.

Tricks to remember Computing the GCD: Definition, Euclid's Subtraction and Āryabhaṭa's Division

Short memory aids. Say each one aloud once, then use it on a question the same day.

Subtract or divide
Subtraction keeps the gcd; division is many subtractions at once and leaves the remainder.
Use it when: Choosing the algorithm.
Stop at zero
The answer is the last non-zero number before the second entry becomes 0.
Use it when: Reading the final answer.
Product over gcd
Multiply the two numbers and divide by their gcd to get the lcm.
Use it when: lcm questions.

Computing the GCD: Definition, Euclid's Subtraction and Āryabhaṭa's Division: solved examples

Ordered from board level to HOTS. Try each one before you open the solution.

Example 1: GCD from the definition · 3 marks · Short answerBoard level

Find $g cd (48, 18)$ by listing the divisors of each number.

Try it first, then show the solutionSolution

Divisors of $48$ : $1, 2, 3, 4, 6, 8, 12, 16, 24, 48$ . (1)
Divisors of $18$ : $1, 2, 3, 6, 9, 18$ . (½)
Common divisors: $1, 2, 3, 6$ ; the greatest is $6$ . (1½)

Answer: $g cd (48, 18) = 6$ .

Example 2: Euclid's subtraction method · 3 marks · Short answerBoard level

Use Euclid's subtraction algorithm to find $g cd (60, 24)$ , showing every step, and count the subtractions.

Try it first, then show the solutionSolution

$(60, 24) \to (24, 36)$ since $60 - 24 = 36$ ; then $24 < 36$ , so swap to $(36, 24)$ . (1)
$(36, 24) \to (24, 12) \to (12, 12) \to (12, 0)$ . (1)
The second number is 0, so $g cd = 12$ ; there were $4$ subtractions: $60 - 24$ , $36 - 24$ , $24 - 12$ and $12 - 12$ (the swap is not a subtraction). (1)

Answer: $g cd (60, 24) = 12$ .

Example 3: Āryabhaṭa's division method · 5 marks · Long answerHarder board level

Find $g cd (1071, 462)$ using the division algorithm, showing each step, and explain why the answer is correct.

Try it first, then show the solutionSolution

$1071 = 2 \times 462 + 147$ , so $g cd (1071, 462) = g cd (462, 147)$ . (1)
$462 = 3 \times 147 + 21$ , so $g cd (462, 147) = g cd (147, 21)$ . (1)
$147 = 7 \times 21 + 0$ , so $g cd (147, 21) = g cd (21, 0) = 21$ . (1)
Each step is a block of repeated subtractions, which keeps the common divisors unchanged (a number dividing $m$ and $n$ divides $m - k n$ ). (1)
Only $3$ division steps were needed; subtraction would need many more. (1)

Answer: $g cd (1071, 462) = 21$ .

Example 4: gcd and lcm · 3 marks · Short answerHarder board level

Use the division algorithm to find $g cd (252, 105)$ and then the lcm of $252$ and $105$ .

Try it first, then show the solutionSolution

$252 mod 105 = 42$ ; $105 mod 42 = 21$ ; $42 mod 21 = 0$ . (1)
So $g cd = 21$ . (1)
$lcm = \frac{252 \times 105}{21} = 12 \times 105 = 1260$ . (1)

Answer: $g cd = 21$ and $lcm = 1260$ .

Example 5: Tiling a floor · 4 marks · Case-basedHOTS / competency

Case: a rectangular floor is 2160 cm long and 1260 cm wide and is to be covered with identical square tiles, as large as possible, with no cutting. (i) Find the side of the tile using the division algorithm and show the steps. (ii) How many tiles are needed? (iii) How many division steps were used? (iv) Why is the division method better than listing the divisors of 2160 and 1260?

Try it first, then show the solutionSolution

(i) $2160 mod 1260 = 900$ ; $1260 mod 900 = 360$ ; $900 mod 360 = 180$ ; $360 mod 180 = 0$ . The tile side is $180$ cm. (1½)
(ii) $\frac{2160}{180} \times \frac{1260}{180} = 12 \times 7 = 84$ tiles. (1)
(iii) Four division steps. (½)
(iv) Listing divisors means testing over a thousand candidates for each number; the division method needed only four steps. (1)

Answer: (i) 180 cm; (ii) 84 tiles; (iii) 4 steps; (iv) far fewer steps.

Where students lose marks in Computing the GCD: Definition, Euclid's Subtraction and Āryabhaṭa's Division

The slips examiners see most often, and what to write instead.

Mistake: Stopping at the remainder instead of the divisor
Giving the last remainder (0) as the answer.
Wrong working
$g cd (105, 45) = 0$ .
Right working
The last non-zero value, $15$ , is the gcd.
Do this: The answer is the number paired with 0.
Usually costs: The whole answer.
Mistake: Not swapping when the first number is smaller
Subtracting a larger number from a smaller one.
Wrong working
$(24, 36) \to (36, - 12)$ .
Right working
Swap to $(36, 24)$ first.
Do this: Check $m \geq n$ at every step.
Usually costs: 2 marks.
Mistake: Forgetting to justify correctness
Showing steps but giving no reason.
Wrong working
Only computations.
Right working
Add "the new pair has the same common divisors, so the same gcd".
Do this: Write the reason in one line.
Usually costs: 1 mark.

Exam tips

Show each step as a pair in a table.
State the stopping rule: second number $= 0$ .
Mention why the rule is correct (same common divisors).
Count steps when asked to compare algorithms.

Practice questions on Computing the GCD: Definition, Euclid's Subtraction and Āryabhaṭa's Division

Write each answer on paper first. Open the hint only if you are stuck, and the answer only when you have finished.

Q1 · 1 mark · MCQBoard level
$g cd (81, 54)$ is
(a) 9
(b) 18
(c) 27
(d) 54
Hint
$81 mod 54 = 27$ ; then $54 mod 27 = 0$ .
Answer
(c) 27.
Q2 · 3 marks · Short answerBoard level
Find $g cd (105, 45)$ by the division method and by the subtraction method (swapping when the first number is smaller), and count the steps in each.
Hint
Write each pair in a table.
Answer
Division: $105 mod 45 = 15$ ; $45 mod 15 = 0$ , so $g cd = 15$ in $2$ steps. Subtraction: $(105, 45) \to (45, 60) \to (60, 45) \to (45, 15) \to (15, 30) \to (30, 15) \to (15, 15) \to (15, 0)$ , so $g cd = 15$ with $5$ subtractions.
Q3 · 3 marks · Short answerHarder board level
Show that $g cd (m, n) = g cd (n, m - n)$ for $m \geq n$ , and use it to find $g cd (91, 35)$ .
Hint
Show that the pairs have the same common divisors.
Answer
If $d$ divides $m$ and $n$ , then $d$ divides $m - n$ . If $d$ divides $n$ and $m - n$ , then $d$ divides $(m - n) + n = m$ . So both pairs have the same common divisors, hence the same greatest one. $91 mod 35 = 21$ ; $35 mod 21 = 14$ ; $21 mod 14 = 7$ ; $14 mod 7 = 0$ . $g cd (91, 35) = 7$ .
Q4 · 5 marks · Long answerHarder board level
A teacher has 84 pencils, 126 erasers and 210 sharpeners. They are packed into identical kits using all items. Find the greatest number of kits and the contents of one kit, using the gcd algorithm.
Hint
Find $g cd (g cd (84, 126), 210)$ .
Answer
$g cd (84, 126)$ : $126 mod 84 = 42$ ; $84 mod 42 = 0$ , so $42$ . $g cd (42, 210)$ : $210 mod 42 = 0$ , so $42$ . The greatest number of kits is $42$ . Each kit has $\frac{84}{42} = 2$ pencils, $\frac{126}{42} = 3$ erasers and $\frac{210}{42} = 5$ sharpeners.
Q5 · 4 marks · Case-basedHOTS / competency
Case: to find $g cd (1000, 625)$ a student scans the numbers from 625 downwards and stops at the first common divisor of 1000 and 625. (i) What is the gcd? (ii) How many numbers does the student examine? (iii) How many division steps does the division method need? (iv) State which method grows more slowly if the numbers become much larger, and why.
Hint
The first common divisor met while scanning down is the largest.
Answer
(i) $125$ (the first number from 625 downwards dividing both). (ii) The numbers $625, 624, \dots, 125$ : $625 - 125 + 1 = 501$ . (iii) $1000 mod 625 = 375$ ; $625 mod 375 = 250$ ; $375 mod 250 = 125$ ; $250 mod 125 = 0$ : four steps. (iv) The division method: its number of steps grows with the number of digits, while the scan grows with the size of the numbers.

Test your recall

Answer in your head or on paper first, then open the card. Pulling an answer out of memory makes it stick far better than re-reading.

1.Euclid's reduction?Show answer
$g cd (m, n) = g cd (n, m - n)$ .
2.Āryabhaṭa's reduction?Show answer
$g cd (m, n) = g cd (n, m mod n)$ .
3.gcd(m, 0)?Show answer
$m$ .
4.lcm in terms of gcd?Show answer
$\frac{mn}{g c d ( m , n )}$ .
5.What does the division method's work depend on?Show answer
The number of digits of the numbers.

Computing the GCD: Definition, Euclid's Subtraction and Āryabhaṭa's Division: frequently asked questions

Why does the division method always stop?

Because the remainder is smaller than the divisor, so the second number strictly decreases until it reaches 0.

Does the order of m and n matter?

No. If m < n the first step simply swaps them.

Is the gcd the same as the HCF?

Yes, they are two names for the greatest common divisor.