NCERT Solutions Class 9 Maths Chapter 11 the World of Algorithms

F R E E S T U D Y M AT E R I A L F O R E V E R Y S T U D E N T

C L A S S 9 · M AT H S

NCERT Solutions + ×
Chapter 11: The
World of Algorithms

NCERT Textbook — Ganita Manjari

BOOK PAGES SECTIONS QUESTIONS MEDIUM

Part II, 37 – 50 7 19 English

Every question Step by step Exam ready
Activities, in-text questions The working shown, not Written to match how
and all exercises. just the final answer. marks are awarded.

Solutions, notes, sample papers & more at 30 pages

Class 9 Maths Chapter 11 The World of Algorithms AglaSem · NCERT Solutions

CLASS 9 · MATHS · GANITA MANJARI

NCERT Solutions — Chapter 11: The World of Algorithms
Chapter 11 explains what an algorithm is: a precise, step-by-step procedure built from basic steps we can
already do. It starts with the column method of addition, then builds algorithms for listing divisors and finding
the gcd, improves them one by one, and compares how much work each needs. It ends with Euclid’s
subtraction method and Āryabhaṭa’s much faster division method. You will learn to write algorithms clearly,
execute them, check that they are correct and judge how efficient they are.

TEXTBOOK BOOK PAGES
Ganita Manjari (Class 9) Part II, 37 – 50

SECTIONS QUESTIONS
7 19

MEDIUM
English

Exercise Set 11.1 — Page 38

Page 1 of 30

Class 9 Maths Chapter 11 The World of Algorithms AglaSem · NCERT Solutions

Section 11.1.1 Adding Numbers Digit by Digit

Q1 Add two 4-digit numbers using the steps we have written down. Make sure you follow
the steps precisely; do not perform any action that is not explicitly mentioned. Are you
able to obtain the correct result?

Algorithm to add two numbers
1. Write the numbers one below the other in the Indian base-ten place-value
system so that the digits are aligned from right to left.
2. Add the rightmost digits.
– If the sum is less than 10, write the sum directly below the two digits. Set
the value of carry to 0.
– If the sum is more than 10, write the units digit of the sum directly below
the two digits. Set the value of carry to 1.
3. Move to the next column of digits on the left. Add the two digits and the
current value of carry.
– If the sum is less than 10, write the sum directly below the two digits. Set
the value of carry to 0.
– If the sum is more than 10, write the units digit of the sum directly below
the two digits. Set the value of carry to 1.
4. Repeat Step 3 until there are no more digits on the left.
5. If the value of carry is 1, write 1 to the left of the bottom row.
The algorithm as written in the book, pages 37–38

Example 1: 3486 + 2759

Step 1: write 3486 above 2759, right digits aligned
Step 2: 6 + 9 = 15, more than 10 → write 5, carry = 1

Step 3: 8 + 5 + 1 = 14 → write 4, carry = 1
Step 3: 4 + 7 + 1 = 12 → write 2, carry = 1

Step 3: 3 + 2 + 1 = 6, less than 10 → write 6, carry = 0
Step 5: carry is 0, nothing more to write → 6245 ✓

Page 2 of 30

Class 9 Maths Chapter 11 The World of Algorithms AglaSem · NCERT Solutions

Example 2: 2735 + 4175. Step 2 gives 5 + 5 = 10. The steps cover only “less than 10” and
“more than 10”, so a strict follower is stuck.
So we get the correct result only when no column adds up to exactly 10. To make the steps
always work, the second case should read “if the sum is 10 or more”. With this fix, 2735 + 4175
= 6910.

Why: an algorithm must cover every case that can happen. A column sum can
be any whole number from 0 to 19, and 10 is one of them. The running text on
page 37 correctly says to carry “if the total was equal to or more than 10”, but
the boxed steps leave out “equal to”. A person might quietly fill the gap, but a
strict follower (like a computer) cannot.

Check it yourself: 4768 + 5397. Columns: 8 + 7 = 15 (write 5, carry 1); 6 + 9 + 1
= 16 (write 6, carry 1); 7 + 3 + 1 = 11 (write 1, carry 1); 4 + 5 + 1 = 10 — stuck
again in Step 3. With “10 or more”: write 0, carry 1, and Step 5 writes 1, giving
10165.

About the book: in Steps 2 and 3, “more than 10” should be “10 or more” (equal
to or more than 10), as the text on page 37 says. This exercise is a good test of
reading steps exactly as written.

Q2 What happens if you add a 5-digit number to a 3-digit number. Do our steps handle
this situation correctly?

Example: 45678 + 789 (right digits aligned)

Units: 8 + 9 = 17 → write 7, carry 1
Tens: 7 + 8 + 1 = 16 → write 6, carry 1

Hundreds: 6 + 7 + 1 = 14 → write 4, carry 1
Thousands: 5 + (no digit) + 1 → ?

Page 3 of 30

as e
Class 9 Maths Chapter 11 The World of Algorithms
ag l AglaSem · NCERT Solutions

Step 3 says “add the two digits”, but the thousands and ten-thousands columns have m
o
only one
m .c
e
digit. So, strictly, our steps do not handle this case.
om as
treat each empty place as the digit 0, that is, write 789 as l00789:
.c ag
They work if we
se m
gla
aThousands: 5 + 0 + 1 = 6 → write 6, carry 0

com
Ten-thousands: 4 + 0 + 0 = 4 → write 4

m . ag
se
45678 + 789 = 46467 ✓
la
ag
So we must add a rule: “if a column has only one digit, take the missing digit as 0”.

com
e m.
m l as
.co ag
a sem 0 is the right choice: 789 has no thousands and no ten-thousands, so its
agl digits in those places really are 0. Writing the zeros does not change the
Why

number, but it makes every column have two digits, which is what Step 3
m a s
expects. .co
em agl
a s
gl
Tip: Step 4, “repeat untilathere are no more digits on the left”, must also be read
m
as “until there are no more digits in the longer number”. Otherwise we might
stop after the 3 columns of 789 and lose the 4 and 5 of 45678. .co
m as em
. co agl
a semCheck it yourself: 99999 + 999 = 100998. Here the padding with zeros and
agl Step 5 are both needed.

se m
com g l a
m . a
e
g las
a align the columns from right to left?
Q3 Why is it important to

com
m .
se

com the rightmost digit of every whole number is its units a Lining up the right ends
gldigit.
.
Because
a
a s emputs units under units, tens under tens, hundreds under hundreds, and so on. The algorithm
agl adds one column at a time, so each column must hold digits of the same place value. This c
matters most when the numbers have different numbers of digits.
m .
a s e
. com agl
52 + 314, aligned on the right:em
a s 2 + 4 = 6, 5 + 1 = 6, 0 + 3 = 3 → 366 ✓
aglleft: 5 under 3, 2 under 1 → 520 + 314 = 834 ✗
52 + 314, aligned on the

co m
m .
m as e
.co

ag l Page 4 of 30

Class 9 Maths Chapter 11 The World of Algorithms AglaSem · NCERT Solutions

Aligning on the left treats 52 as if it were 520.

Why: in the base-ten system the value of a digit depends on its place. In 52 the
5 means 5 tens; in 314 the 3 means 3 hundreds. Adding 5 and 3 would mix tens
with hundreds, which is like adding 5 rupees to 3 hundred-rupee notes and
calling it 8 hundred rupees.

Tip: we also work from right to left, because a carry always moves one place to
the left. A column’s carry must be known before we add the next column.

Q4 In Step 3, why cannot the value of carry be more than 1?
(Step 3: Move to the next column of digits on the left. Add the two digits and the current
value of carry.)

The largest possible column sum is

largest digit + largest digit + largest carry
= 9 + 9 + 1 = 19

Since a column sum is never 20 or more, its tens digit is at most 1, so the carry is at most 1.
This works step by step. In Step 2 there is no carry yet, so the sum is at most 9 + 9 = 18 and the
carry is 0 or 1. Then each Step 3 column is at most 9 + 9 + 1 = 19, so it again passes on a carry
of 0 or 1, and so on for every column.

Why: the carry is the number of complete tens in the column sum. From 0 to 9
there are no tens; from 10 to 19 there is exactly one ten. To get a carry of 2 we
would need a column sum of 20 or more, which two digits and a carry of 1 can
never reach.

Page 5 of 30

Class 9 Maths Chapter 11 The World of Algorithms AglaSem · NCERT Solutions

Check it yourself: 99 + 99 = 198 uses the largest sums possible: 9 + 9 = 18
(carry 1), then 9 + 9 + 1 = 19 (carry 1).

Did you know? When you add three numbers in columns, the carry can be 2:
for example 9 + 9 + 9 = 27. So “carry is at most 1” is true only for adding two
numbers.

Q5 What happens if we do not include the fifth step in the algorithm above? Give examples
where the algorithm will work correctly and where it will fail to work.
(Step 5: If the value of carry is 1, write 1 to the left of the bottom row.)

Without Step 5, a carry of 1 left over from the leftmost column is thrown away, so the answer
loses its first digit.
Works correctly when the leftmost column adds up to less than 10, so the final carry is 0:

3486 + 2759 → 6245 ✓
2105 + 3462 → 5567 ✓

Fails when the leftmost column produces a carry of 1:

473 + 695: 3 + 5 = 8; 7 + 9 = 16 → 6, carry 1; 4 + 6 + 1 = 11 → 1, carry 1

Bottom row = 168, but 473 + 695 = 1168 ✗
5 + 7: 12 → write 2, carry 1 → answer 2 instead of 12 ✗

Why: the final carry is one group of ten in the leftmost place, which makes one
unit of a new place further left (for example, 10 hundreds = 1 thousand). There
is no column left in which to add it, so Step 5 writes it down on its own.

Page 6 of 30

Class 9 Maths Chapter 11 The World of Algorithms AglaSem · NCERT Solutions

Tip: because the carry is never more than 1, the sum of two numbers has at
most one digit more than the longer number, and that extra digit is always 1.

Think and Reflect — Page 39
Section 11.1 Adding Numbers
THINK AND REFLECT

Q1 See if you can complete the argument about grouping by units, tens, hundreds, … to
justify why the addition algorithm works.

Write each number as groups of units, tens and hundreds, and add like groups:

473 = 4 hundreds + 7 tens + 3 units

695 = 6 hundreds + 9 tens + 5 units
Sum = 10 hundreds + 16 tens + 8 units

= 10 hundreds + (1 hundred + 6 tens) + 8 units [carry 1]

= 11 hundreds + 6 tens + 8 units
= 1 thousand + 1 hundred + 6 tens + 8 units [carry 1]

= 1168

The algorithm makes exactly these moves. Each column is one group (units, tens, hundreds,
…). Each carry exchanges ten of one group for one of the next group, since 10 units = 1 ten, 10
tens = 1 hundred, and so on. Exchanging never changes the total. So the digits we write give
the same total as counting all the dots.

Why we may add group by group: counting dots in any order or in any grouping
gives the same total (addition is commutative and associative). So we can put
all the hundreds together, all the tens together and all the units together, and
count each pile separately.

Page 7 of 30

Class 9 Maths Chapter 11 The World of Algorithms AglaSem · NCERT Solutions

In general, a number with digits a2a1a0 means a2 × 100 + a1 × 10 + a0. Adding two such
numbers gives (a2 + b2) × 100 + (a1 + b1) × 10 + (a0 + b0). If a column total is 10 or more,
we rewrite 10 of that place as 1 of the next place: that is the carry. After all exchanges,
every place holds a single digit, and those digits are the answer.

Tip: this is also why we write only the units digit of a column sum: the tens digit
of the column sum has already moved left as the carry.

Q2 How would you modify the algorithm to add two decimal fractions?

Change Step 1: line up the decimal points (not the rightmost digits). If one number has fewer
digits after the decimal point, write zeros at its right end so both have the same number of
decimal places. Then add the columns from the right exactly as before (Steps 2–5), and put the
decimal point in the answer directly below the other decimal points.

3.75 + 12.6 → write as 3.75 + 12.60
Hundredths: 5 + 0 = 5

Tenths: 7 + 6 = 13 → write 3, carry 1

Units: 3 + 2 + 1 = 6
Tens: 0 + 1 = 1

Answer: 16.35

The carry works across the decimal point because 10 hundredths = 1 tenth and 10 tenths = 1
unit.

Why: lining up the decimal points is the same idea as lining up the right ends of
whole numbers: it puts digits of the same place value (units, tenths, hundredths,
…) in the same column. For whole numbers the decimal point sits just after the
units digit, so lining up the right ends is a special case of this rule.

Page 8 of 30

ase
Class 9 Maths Chapter 11 The World of Algorithms
ag l AglaSem · NCERT Solutions

m5
cothe
.
Common mistake: aligning the rightmost digits of 3.75 and 12.6 would put
m as
hundredths under the 6 tenths and give a wrong answer. Always alignemthe
o
decimal.cpoints.
em agl
a s
gl modified algorithm, written out:
aThe

com point, write zeros at its right end until
1. Write the numbers one below the other so that the decimal points are aligned.
2. If one number has fewer digits after the .decimal
em ag
a s
agl out Steps 2–5 of the addition algorithm.
both have the same number.
3. Ignoring the decimal points, carry
4. Put the decimal point in the answer directly below the decimal points of the numbers.
co m
em.
m l as
m .co ag
la seand Reflect — Page 41
g
Think
a
Section 11.2.1 Computing the Divisors of a Number
m a s
.co agl
THINK AND REFLECT

a s em
Q1 agl to compute the divisors of 15, 135, and 775. How does the
Try to execute the algorithm
amount of work increase as the numbers grow?
co m
m .
as e
comfor 15 (list-of-divisors starts empty, [ ]):
. agl
em
Executing
a s
agl
m
j = 1 divides 15 → [1]

a se
j = 2 does not divide 15 → [1]
.com a g l
e m
las
j = 3 divides 15 → [1, 3]

j = 4 does not → [1, 3] ag

co m
.
j = 5 divides 15 → [1, 3, 5]

se m
m la
.jc=o 15 divides 15 → [1, 3, 5, 15]
j = 6, 7, …, 14 do not → [1, 3, 5]

em ag
a s
agl c
m .
e
In the same way:
m a s
. co agl
a sem
agl

co m
m .
m as e
.co

ag l Page 9 of 30

Class 9 Maths Chapter 11 The World of Algorithms AglaSem · NCERT Solutions

divisors(15) = [1, 3, 5, 15] — 15 checks

divisors(135) = [1, 3, 5, 9, 15, 27, 45, 135] — 135 checks
divisors(775) = [1, 5, 25, 31, 155, 775] — 775 checks

Work: the algorithm tests every j from 1 to n, so it makes n checks for the number n. The work
grows in proportion to the number itself: 135 needs 9 times as many checks as 15. Each extra
digit makes the work about 10 times bigger, just like adding by counting dots.

Check it yourself: 135 = 3 × 3 × 3 × 5, and its divisors pair up as 1 × 135, 3 ×
45, 5 × 27, 9 × 15. Also 775 = 5 × 5 × 31, with pairs 1 × 775, 5 × 155, 25 × 31.

Why the work does not depend on how many divisors there are: the algorithm
checks every j, whether it turns out to be a divisor or not. For 775 it makes 775
checks to find just 6 divisors. The amount of work depends only on the size of
n.

Tip: Exercise Set 11.2, Q3 shows a shortcut: because divisors come in pairs, we
only need to check j up to √n. For 775 that is up to 27 (since 27 × 27 = 729 and
28 × 28 = 784), instead of up to 775.

Exercise Set 11.2 — Pages 43–44
Sections 11.2 Greatest Common Divisor and 11.3 Data Structures

Q1 Suppose List 1 and List 2 are two lists of numbers in increasing order.
(i) Write an algorithm to find elements in List 1 that are not present in List 2.
(ii) Write an algorithm to find elements in List 2 that are not present in List 1.

(i)

Page 10 of 30

Class 9 Maths Chapter 11 The World of Algorithms AglaSem · NCERT Solutions

Algorithm to find the elements of List 1 not in List 2
1. Start with an empty list only-in-1 .
2. For each number x in List 1
– if x does not appear in List 2, add x to only-in-1 .
3. Report only-in-1 .

(ii) The same algorithm with the lists swapped:

Algorithm to find the elements of List 2 not in List 1
1. Start with an empty list only-in-2 .
2. For each number x in List 2
– if x does not appear in List 1, add x to only-in-2 .
3. Report only-in-2 .

Example: List 1 = divisors(375) = [1, 3, 5, 15, 25, 75, 125, 375], List 2 = divisors(825) = [1, 3, 5,
11, 15, 25, 33, 55, 75, 165, 275, 825]. Then (i) gives [125, 375] and (ii) gives [11, 33, 55, 165, 275,
825], both in increasing order.

Why: this is the gcd algorithm’s Step 4 turned round: there we kept x if it did
appear in the other list; here we keep x if it does not.

A faster version that uses the increasing order. Keep two markers, a in List 1 and b in List
2, both starting at the first element.
1. Start with an empty list only-in-1 .
2. Repeat until marker a has passed the end of List 1:
If b has passed the end of List 2, or the number at a is smaller than the number at b:
add the number at a to only-in-1 and move a one place right.
If the two numbers are equal: move both a and b one place right.
If the number at a is larger than the number at b: move b one place right.
3. Report only-in-1 .
When the number at a is smaller than the number at b, it cannot appear later in List 2,
because List 2 only gets bigger from there. Each comparison moves at least one marker,
so we make at most (length of List 1 + length of List 2) comparisons, instead of searching
the whole of List 2 for every x.

Page 11 of 30

Class 9 Maths Chapter 11 The World of Algorithms AglaSem · NCERT Solutions

Check it yourself: run the faster version on the example above. You should
again get [125, 375].

Q2 Describe an algorithm to compute the least common multiple (lcm) of two numbers.

The lcm of m and n is the smallest number that both m and n divide. Straight from this
definition: go through the multiples of the larger number in order, and stop at the first one that
the other number divides.

Algorithm to find lcm(m, n)
1. If m < n, swap the numbers, so that m is the larger one.
2. For each number k in the sequence 1, 2, 3, …, n
– if n divides k × m, report k × m as lcm(m, n) and stop.

The algorithm always stops by k = n, because n × m is a multiple of both numbers.

lcm(12, 18): m = 18, n = 12

k = 1: 12 does not divide 18
k = 2: 12 divides 36 → lcm(12, 18) = 36

Why the first one found is the least: the multiples m, 2m, 3m, … are checked in
increasing order, so the first common multiple we meet is the smallest.

Tip: starting with the larger number means fewer multiples to check. For lcm(12,
18), the multiples of 12 would need 3 checks (12, 24, 36), the multiples of 18
only 2.

A faster method using gcd. For any two numbers, lcm(m, n) × gcd(m, n) = m × n. So we
can find the gcd with Euclid’s algorithm and then

Page 12 of 30

Class 9 Maths Chapter 11 The World of Algorithms AglaSem · NCERT Solutions

lcm(m, n) = (m × n) ÷ gcd(m, n)
lcm(375, 825) = (375 × 825) ÷ 75 = 309375 ÷ 75 = 4125

Check it yourself: 4125 ÷ 375 = 11 and 4125 ÷ 825 = 5, so 4125 is a common
multiple.

*Q3 Divisors occur in pairs. For instance, the divisors of 18 are (1, 18), (2, 9) and (3, 6).
(i) If we write out divisors in pairs, how many numbers do we have to examine
between 1 and n to find all the divisors of n?
(ii) If we list out the divisors in pairs, will our gcd algorithm still work in the manner we
have described?

(i) In each pair (j, n ÷ j), the smaller number is at most √n; if both were bigger than √n, their
product would be bigger than n. So we only examine j = 1, 2, 3, … up to √n, that is, up to the
largest whole number whose square is not more than n. Each j that divides n gives a pair (j, n ÷
j).

n = 18: √18 ≈ 4.24 → examine 1, 2, 3, 4 only (4 numbers, not 18)
→ pairs (1, 18), (2, 9), (3, 6)

(ii) Not as described. Written in pairs, the list is not in increasing order: [1, 18, 2, 9, 3, 6]. But the
last step, “report the rightmost element of common-divisors”, needs increasing order.

gcd(18, 9): divisors-of-18 = [1, 18, 2, 9, 3, 6], divisors-of-9 = [1, 9, 3]
common-divisors = [1, 9, 3] → rightmost = 3 ✗ (true gcd = 9)

Fix: report the largest element of common-divisors instead.

Page 13 of 30

ase
Class 9 Maths Chapter 11 The World of Algorithms
ag l AglaSem · NCERT Solutions

co m
m.

m as e
.co ag l
se m
la
ag

co m
m . ag
la se
ag
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

co m
m.
check √18 ≈ 4.24

e
as pair lies to the left
1 to 4
m18 joined in pairs (1, 18), (2, 9), (3, 6). The smaller number ofgevery
Divisorsoof
c l
se m. of √18. a
la
ag
Why √n is enough: if j × k = n with j ≤ k, then j × j ≤ j × k = n, so j ≤ √n. Every
a s
.
pair therefore has its smaller membercom
among 1, 2, …, √n, and finding the smaller
agl
member gives us the larger one sem a
by one division.
agl
Check it yourself: for 375, √375 ≈ 19.4, so we examine 1 to 19 (19 numbers
m
.co
em
instead of 375) and find the pairs (1, 375), (3, 125), (5, 75), (15, 25).
m as
. co agl
a semTip: if n is a perfect square, one pair has equal members, for example (6, 6) for
agl 36. Write 6 only once in the list.

se m
com g l a
m
Another fix for (ii): keep the small . members in one list and the large members a
e
as 9, 6]. Reverse the second and join: [1, 2, 3] + [6, 9,
l
in another: [1, 2, 3] and [18,
g
18] = [1, 2, 3, 6, 9, 18].a Now the list is in increasing order and the original gcd
algorithm works unchanged.
co m
m .
m la se
.co ag
a s em
agl Exercise Set 11.3 — Page 45 c
m .
m a s e
. co agl
asem
agl

co m
m .
m as e
.co

ag l Page 14 of 30

Class 9 Maths Chapter 11 The World of Algorithms AglaSem · NCERT Solutions

Section 11.3.1 Improving the Algorithm

Q1 How would our original algorithm change if we computed the divisors of n by
examining the numbers from 1 to n in reverse order, from n down to 1?

Algorithm to find gcd(m, n)
1. Let divisors-of-m be the list obtained by computing divisors(m)
2. Let divisors-of-n be the list obtained by computing divisors(n)
3. Start with an empty list common-divisors
4. For each number x in the list of divisors-of-m
– If x also appears in the list of divisors-of-n , add x to the list common-
divisors
5. Report the rightmost element of the list common-divisors as gcd(m, n)
The original gcd algorithm, pages 42–43. It uses: Algorithm to find the divisors of n — 1. Start
with an empty list-of-divisors . 2. For each number j in the sequence 1, 2, 3, …, n: if j
divides n, add j to the list-of-divisors .

The divisor lists would come out in decreasing order, for example divisors(375) = [375, 125, 75,
25, 15, 5, 3, 1]. Then common-divisors is also in decreasing order, so the gcd is its leftmost
(first) element, not the rightmost. Step 5 must change to: “Report the leftmost element of the
list common-divisors as gcd(m, n).” If Step 5 were left unchanged, it would always report 1.

gcd(375, 825):

divisors-of-375 = [375, 125, 75, 25, 15, 5, 3, 1]
divisors-of-825 = [825, 275, 165, 75, 55, 33, 25, 15, 11, 5, 3, 1]
common-divisors = [75, 25, 15, 5, 3, 1] → leftmost = 75 ✓

Why: the gcd is the largest common divisor. In a list in increasing order the
largest element is at the right end; in a list in decreasing order it is at the left
end. Reversing the scan reverses every list, so the position of the gcd moves
from right to left.

Page 15 of 30

Class 9 Maths Chapter 11 The World of Algorithms AglaSem · NCERT Solutions

Tip: with the reverse order, Step 4 can stop early. The first x in divisors-of-m
that also appears in divisors-of-n is already the largest common divisor, so we
can report it at once and skip the rest of the list.

Common mistake: keeping “rightmost” in Step 5. In the reversed list the
rightmost element is always 1, since 1 divides every number.

Q2 What about the last algorithm described above? What happens when we look at
common divisors starting from min(m, n) and work backwards to 1?

Do away with lists (page 45)
Start with most-recent-common-divisor set to 1. Then scan all numbers from 2
to min(m, n):
For each k from 2 to min(m, n), if k divides both m and n, update most-
recent-common-divisor to k.

At the end of this scan, most-recent-common-divisor directly gives us the
gcd.
The last algorithm of Section 11.3.1, page 45

Going downwards, the first k that divides both m and n is the largest common divisor, that is,
the gcd. So we can stop as soon as we find it. We no longer need most-recent-common-
divisor at all.

Algorithm to find gcd(m, n), scanning downwards
1. For each k from min(m, n) down to 1
– if k divides both m and n, report k as gcd(m, n) and stop.

It always stops, because k = 1 divides both numbers.

Page 16 of 30

Class 9 Maths Chapter 11 The World of Algorithms AglaSem · NCERT Solutions

gcd(6, 12): min(6, 12) = 6
k = 6 divides both 6 and 12 → gcd(6, 12) = 6, after just 1 check
(scanning upwards needed 5 checks, k = 2 to 6)

This is much faster when the gcd is large. But when the gcd is small, for example gcd(35, 36) =
1, we still go all the way down to 1, so in the worst case it is no better.

Why the upward scan cannot stop early: when scanning upwards, a bigger
common divisor might still come later, so we must go all the way to min(m, n)
and remember the latest one found. Scanning downwards, nothing bigger is left
to find once we meet a common divisor.

Check it yourself: for gcd(375, 825), the downward scan checks k = 375, 374,
…, 75, which is 301 checks, and stops at 75. The upward scan checks k = 2 to
375, which is 374 checks.

Tip: the number of checks is min(m, n) − gcd + 1. It is still proportional to the
size of the numbers, which is why the chapter next looks for a faster idea
(Euclid).

In-text Questions — Page 48
Section 11.3.4 Āryabhaṭa’s Division Algorithm

Q1 Using the improved algorithm (reduce gcd(m, n) to gcd(n, m mod n)), gcd(99, 2)
needed only two reduction steps: gcd(99, 2) → gcd(2, 1) → gcd(1, 0), answer 1. Check
that this would happen for any similar problem of the form gcd(2k + 1, 2).

For k ≥ 1, 2k + 1 is bigger than 2, so no reversal is needed.

Page 17 of 30

Class 9 Maths Chapter 11 The World of Algorithms AglaSem · NCERT Solutions

gcd(2k + 1, 2): 2k + 1 = k × 2 + 1, so (2k + 1) mod 2 = 1 → reduce to gcd(2, 1)
gcd(2, 1): 2 = 2 × 1 + 0, so 2 mod 1 = 0 → reduce to gcd(1, 0)

gcd(1, 0): n = 0 → answer 1

An odd number always leaves remainder 1 when divided by 2, whatever k is. So every problem
gcd(2k + 1, 2) takes exactly two reductions and gives the answer 1.
Example: gcd(2001, 2) → gcd(2, 1) → gcd(1, 0) = 1. The subtraction version would need 1002
reductions here.

Why: repeatedly subtracting 2 from 2k + 1 takes away k twos and leaves 1.
Division does all those k subtractions in one step, because the remainder is
exactly what is left after subtracting as many 2s as possible.

Check it yourself: k = 0 gives gcd(1, 2). Step 1 reverses it to gcd(2, 1), and a
single reduction gives gcd(1, 0) = 1. So the “two reductions” pattern is for k ≥ 1,
that is, for the odd numbers 3, 5, 7, … (Reversing is not a reduction.)

End-of-Chapter Exercises — Page 50

Page 18 of 30

as e
Class 9 Maths Chapter 11 The World of Algorithms
ag l AglaSem · NCERT Solutions

Whole chapter
co m
se m.
Compute
. a gla
comthe following using the improved version of Euclid’s algorithm.
m
Q1
(i)egcd(375,
a s 825)
agl (ii) gcd(51000, 81000)
(iii) gcd(1789287, 237656)
(iv) gcd(2587392, 157656)
com
m . ag
se
glofa Euclid’s algorithm for gcd(m, n)
Improved (division) version
a
1. If m < n, reverse the numbers and compute gcd(n, m)
2. If n = 0, report the answer as m . com
sen)m
glmais divided by n.
com As printed on page 48. Here m mod n is the remainder when
3. Otherwise, reduce the problem to computing gcd(n, m mod
. a
a sem
ag l

m a s
.co agl

a s em
By Step 1, the larger number goes first. Each row gcd(m, n) reduces to gcd(n, m mod n), which
l we have reached gcd(n, 0), so the gcd is n.
is the next row. When m mod na=g0,
(i) gcd(375, 825) = 75
co m
m .
m n m mod n
as e
. com agl
a s em
825 375 75

agl 375 75 0

se m
com g l a
.
(ii) gcd(51000, 81000) = 3000
e m a
m
ag lnas m mod n

m
81000 51000 30000
. co
51000 30000 21000
se m
com la
em
.30000 ag
s
21000 9000
a
agl c
.
21000 9000 3000

s e m
com a
agl
9000 3000 0
.
(iii) gcd(1789287, 237656)l=a1 sem
ag

co m
m .
m as e
.co

ag l Page 19 of 30

Class 9 Maths Chapter 11 The World of Algorithms AglaSem · NCERT Solutions

m n m mod n

1789287 237656 125695

237656 125695 111961

125695 111961 13734

111961 13734 2089

13734 2089 1200

2089 1200 889

1200 889 311

889 311 267

311 267 44

267 44 3

44 3 2

3 2 1

2 1 0

(iv) gcd(2587392, 157656) = 24

m n m mod n

2587392 157656 64896

157656 64896 27864

64896 27864 9168

27864 9168 360

9168 360 168

360 168 24

168 24 0

Page 20 of 30

Class 9 Maths Chapter 11 The World of Algorithms AglaSem · NCERT Solutions

Check each row: m = quotient × n + (m mod n). The quotients are: (i) 2, 5; (ii) 1,
1, 1, 2, 3; (iii) 7, 1, 1, 8, 6, 1, 1, 2, 1, 6, 14, 1, 2; (iv) 16, 2, 2, 3, 25, 2, 7. For example,
in (iii) the first row is 1789287 = 7 × 237656 + 125695.

Āryabhaṭa’s long-division layout for (i) and (ii), as on page 49:

375)825(2
750
---
75)375(5
375
---
0
gcd = 75

51000)81000(1
51000
-----
30000)51000(1
30000
-----
21000)30000(1
21000
-----
9000)21000(2
18000
-----
3000)9000(3
9000
----
0
gcd = 3000

Check it yourself (by prime factorisation):
(ii) 51000 = 23 × 3 × 53 × 17 and 81000 = 23 × 34 × 53, so the gcd is 23 × 3 × 53
= 3000.
(iii) 1789287 = 3 × 19 × 31391 and 237656 = 23 × 61 × 487 have no common
prime factor, so the gcd is 1.
(iv) 2587392 = 28 × 32 × 1123 and 157656 = 23 × 3 × 6569, so the gcd is 23 × 3
= 24.

Page 21 of 30

Class 9 Maths Chapter 11 The World of Algorithms AglaSem · NCERT Solutions

How much faster is division? Division needed 2, 5, 13 and 7 reductions. Euclid’s
subtraction version needs 7, 8, 51 and 57 reductions for the same four
problems.

Tip: when the last non-zero remainder is 1, as in (iii), the two numbers have no
common factor other than 1. Such numbers are called co-prime.

Q2 Assume that m ≥ n. Verify that d divides m and n if and only if d divides both n and m
mod n.

Divide m by n: m = q × n + r, where q is the quotient and r = m mod n, with 0 ≤ r < n.
If d divides m and n: write m = ad and n = bd for whole numbers a, b. Then

r = m − q × n = ad − qbd = (a − qb)d

so d divides r, that is, d divides m mod n. It already divides n.
If d divides n and m mod n: write n = bd and r = cd. Then

m = q × n + r = qbd + cd = (qb + c)d

so d divides m. It already divides n.
Both directions hold, so d divides m and n if and only if d divides n and m mod n. The two
pairs have the same common divisors, hence gcd(m, n) = gcd(n, m mod n).

Page 22 of 30

Class 9 Maths Chapter 11 The World of Algorithms AglaSem · NCERT Solutions

m = 60

d d d d d d d d d d d d d d d

d d d d d d d d d d d d d d d

n = 16 n = 16 n = 16 m mod n
each tile d = 4 = 12

m = 60 = 3 × 16 + 12. Tiles of size d = 4 fill m and n exactly, so they also fill the leftover piece m
mod n = 12 (same idea as Fig. 11.1, page 46).

Check it yourself: 60 = 3 × 16 + 12. Common divisors of 60 and 16: 1, 2, 4.
Common divisors of 16 and 12: 1, 2, 4. The same list, as the result says.

Why (in pictures): m mod n is what is left of m after cutting off q pieces of
length n. If tiles of size d fit m exactly and also fit each piece n exactly, then
they must fit the leftover piece exactly too. In the other direction, if the tiles fit n
and the leftover, they fit q copies of n plus the leftover, which is m.

Tip: a − qb is never negative, because a − qb = r ÷ d and r ≥ 0. If r = 0, then a −
qb = 0, and we say d divides 0 (0 = 0 × d), which is true for every d. This is why
the algorithm can stop at gcd(m, 0) = m.

Link with the subtraction version: m mod n is what we get by subtracting n
from m again and again (q times). Each subtraction keeps the common divisors
the same (page 46), so the remainder keeps them the same too.

Page 23 of 30

ase
Class 9 Maths Chapter 11 The World of Algorithms
ag l AglaSem · NCERT Solutions

Write an algorithm prime(n) to check if n is prime. . com
em make use of
Q3
(Hint: A prime number p has exactly two distinct factors, 1 and p. Cansyou
m a
m .co to write out prime(n)?)
divisors(n) agl
la se
ag

co m
Algorithm prime(n)
m . ag
la se
g
1. Let divisors-of-n be the list obtained by computing divisors(n).
2. Count the number of elements a
in divisors-of-n .
3. If the count is exactly 2, report “n is prime”. Otherwise, report “n is not prime”.
co m
em.
m l as
.co ag
a s em
prime(31): divisors(31) = [1, 31] → 2 elements → 31 is prime

agl prime(15): divisors(15) = [1, 3, 5, 15] → 4 elements → 15 is not prime
m a s
agl
prime(1): divisors(1) = [1] → 1 element → 1 is not prime
.co
em
as than 1 has at least the two divisors 1 and n. It is prime
g
Why it works: every number n greater l
a so its list has exactly 2 elements. The number 1 has only one
exactly when there are no others,
divisor, so it is correctly reported as not prime.
com
m .
m
o l ase
g
.c version. We do not need the whole list. Using the pairing
a
seAmfaster idea of Exercise Set 11.2,
a
agl Q3, any divisor other than 1 and n has a partner, and the smaller of the two is at most √n.
1. If n = 1, report “n is not prime”.
se m
comn, report “n is not prime” and stop. g l a
.
2. For each j from 2 up to √n: if j divides
a
3. Report “n is prime”. em a s
agl
Check it yourself: for n = 97, √97 ≈ 9.8, so we test j = 2, 3, …, 9. None divides
97, so 97 is prime: 8 checks instead of 97. om .c
s e m
.
m
coCommon a la is not enough,
gn?”
em because every number’s list contains 1 and n. We must check that there is
mistake: testing “does the list contain 1 and
a s
agl c
nothing else.
m .
m a s e
. co agl
a sem
agl

co m
m .
m as e
.co

ag l Page 24 of 30

Class 9 Maths Chapter 11 The World of Algorithms AglaSem · NCERT Solutions

*Q4 Write an algorithm primedivisors(n) to compute the list of divisors of n that are prime
numbers.
(Hint: Compute divisors(n) and then filter out the primes in this list.)

Algorithm primedivisors(n)
1. Let divisors-of-n be the list obtained by computing divisors(n).
2. Start with an empty list prime-divisors .
3. For each number x in divisors-of-n
– if prime(x) reports “x is prime”, add x to prime-divisors .
4. Report prime-divisors .

n = 180:
divisors(180) = [1, 2, 3, 4, 5, 6, 9, 10, 12, 15, 18, 20, 30, 36, 45, 60, 90, 180]
keep only the primes → primedivisors(180) = [2, 3, 5]

Similarly, primedivisors(825) = [3, 5, 11]. The answer list is in increasing order, because
divisors(n) is.

Why: this algorithm is built from two smaller algorithms we already have,
divisors(n) and prime(x), just as the gcd algorithm was built from divisors(n).
Writing big algorithms out of smaller ones keeps each step simple and easy to
check.

Tip: 1 is never added, because prime(1) reports “not prime”. The number n itself
is added only if n is prime.

About efficiency: each call prime(x) itself runs divisors(x), so this algorithm
does a lot of checking. Using the faster prime test (checking only up to √x) cuts
the work a great deal.

Page 25 of 30

Class 9 Maths Chapter 11 The World of Algorithms AglaSem · NCERT Solutions

*Q5 We can also find the gcd of two numbers by computing prime factorisation of both
the numbers. Try to write an algorithm to compute the prime factorisation of a
number.
(i) The prime factorisation of 180 is 22 × 32 × 51. How would you represent this?
(ii) How would you compare the prime factorisations of two numbers?

Algorithm factorise(n)
1. Let x = n, and start with an empty list factors .
2. For each prime p in primedivisors(n), from left to right
– set count to 0;
– while p divides x: replace x by x ÷ p and add 1 to count ;
– add the pair (p, count ) to factors .
3. Report factors .

n = 180, primedivisors = [2, 3, 5]
p = 2: 180 → 90 → 45, count = 2
p = 3: 45 → 15 → 5, count = 2
p = 5: 5 → 1, count = 1

(i) As a list of pairs (prime, power), primes in increasing order: 180 → [(2, 2), (3, 2), (5, 1)].
(ii) Compare the lists prime by prime (a missing prime has power 0). For the gcd, take each
prime with the smaller power.

375 → [(3, 1), (5, 3)], 825 → [(3, 1), (5, 2), (11, 1)]

gcd = 31 × 52 × 110 = 75 ✓

Why the smaller power: a common divisor can use each prime at most as many
times as it appears in both numbers. 375 has 5 three times but 825 has it only
twice, so the gcd can contain 5 only twice. The 11 appears in 825 but not in 375
(power 0), so it is left out.

Page 26 of 30

Class 9 Maths Chapter 11 The World of Algorithms AglaSem · NCERT Solutions

Another representation for (i): list only the powers of the primes 2, 3, 5, 7, … in order.
Then 180 → [2, 2, 1]. This is a little like place value: the position tells you which prime is
meant.
More comparisons:
Two numbers are equal exactly when their lists are the same, because every number
has only one prime factorisation.
For the lcm, take each prime with the larger power. Example: 180 → [(2, 2), (3, 2), (5, 1)]
and 168 → [(2, 3), (3, 1), (7, 1)] give gcd = 22 × 3 = 12 and lcm = 23 × 32 × 5 × 7 = 2520.
m divides n exactly when every prime of m has power in n at least as large as in m.

Tip: since both lists are in increasing order of primes, the comparison can be
done with two markers moving left to right, exactly like the faster algorithm in
Exercise Set 11.2, Q1.

Check it yourself: 22 × 32 × 5 = 4 × 9 × 5 = 180, and 12 × 2520 = 30240 = 180
× 168.

Chapter at a glance
An algorithm is a step-by-step procedure, written so precisely that it can be followed
without guessing. It is built from basic steps we can do directly, such as adding two single
digits or checking whether one number divides another.
Column addition: align the digits on the right, add column by column from the right, and
carry 1 when a column adds up to 10 or more; at the end write any leftover carry (473 +
695 = 1168). The carry is never more than 1, because 9 + 9 + 1 = 19.
Column addition needs work in proportion to the number of digits, while counting dots
needs work in proportion to the value: 3347 + 2729 takes about a minute by columns but
over 1 hour 40 minutes by counting dots.
divisors(n): start with an empty list and, for each j from 1 to n, add j if it divides n. This
takes n checks and gives the divisors in increasing order, e.g. divisors(18) = [1, 2, 3, 6, 9,
18]. A list is an example of a data structure.
First gcd algorithm: list the common divisors and report the rightmost (largest), e.g.
gcd(375, 825) = 75. Improvements: scan once up to min(m, n), and keep only the most
recent common divisor instead of whole lists. The work is still proportional to the size of the
numbers.
Euclid’s subtraction algorithm: for m ≥ n, gcd(m, n) = gcd(n, m − n), and gcd(m, 0) = m. It
is correct because m, n and n, m − n have the same common divisors. It can still be slow:

Page 27 of 30

Class 9 Maths Chapter 11 The World of Algorithms AglaSem · NCERT Solutions

gcd(2k + 1, 2) needs about k reductions.
Āryabhaṭa’s division algorithm (Āryabhaṭīya, 499 CE): gcd(m, n) = gcd(n, m mod n), done
as repeated long division. gcd(99, 2) takes only 2 reductions, and in general the number of
reductions grows with the number of digits.
The word algorithm comes from Al-Khwārizmī, whose book on Indian numerals (around
820 CE) spread Indian arithmetic to Europe. With every algorithm we must justify that it is
correct and analyse how many steps it takes.

Page 28 of 30

as e
Class 9 Maths Chapter 11 The World of Algorithms
ag l AglaSem · NCERT Solutions

co m
m.
Quick revision
m l ase
.co IN SYMBOLS / ag STUDENTS SLIP
em
IDEA WHAT IT SAYS WHERE
a s
agl
STATEMENT

Algorithm Finite list of precise A step-by-step procedure, Doing an action the steps do

co m
built from basic steps, that not mention, or not noticing a
ag
steps

m .
se
solves every case of a case the steps miss

la problem

Column addition Carry 1 if column
ag Add digits of the same place Book’s box says “more than
sum ≥ 10 value from right to left,
co m
10”; a sum of exactly 10 also

m.
passing tens to the left gives a carry

m l ase it can be 2 (only
m .co
Size of the carry 9 + 9 + 1 = 19 When adding two numbers
agwhen adding three or more
Thinking

la se the carry is always 0 or 1

ag
numbers)

Final carry (Step 5) A leftover carry becomes a Writing 168 by dropping the
a s
com
473 + 695 = 1168

. agl
new leftmost digit 1 last carry
e m
Units under units as Right ends (or decimal points)
agl must line up
Alignment Aligning numbers of different
lengths on the left

co m
.
divisors(n) for j = 1, 2, …, n: if j Takes n checks; list comes Forgetting 1 or n itself
divides n, add j out in increasing order
se m
com l a
Divisor .pairs
em
(j, n ÷ j) with j ≤ √n ag Writing the middle divisor of
Only j up to √n need checking
a s
agl
a perfect square twice

m
First gcd algorithm Works because the lists are in Using “rightmost” when the
se
gcd = rightmost of
common-divisors
com
increasing order list is in pairs or reversed
g l a
.
k = 2, …, min(m, n)em No lists needed; the last
a
l as
Scan with most- Scanning up to max(m, n)
recent-common-
a g common divisor found is the when min(m, n) is enough
divisor gcd

co m
Euclid (subtraction) gcd(m, n) = gcd(n, m Same common divisors,
m .
Forgetting to swap when m <

m
− n), m ≥ n smaller numbers
la se n
.co ag
a s em
Stopping rule gcd(m, 0) = m Every d divides 0, so the Stopping one step early and

ag l common divisors of m and 0 reporting the wrong number
are those of m
.c
s e m
comreductions grow with the a
. agl
Āryabhaṭa gcd(m, n) = gcd(n, m m mod n is the remainder; Using the quotient instead of

sem number of digits
(division) mod n) the remainder
a
agl

co m
m .
m as e
.co

ag l Page 29 of 30

Class 9 Maths Chapter 11 The World of Algorithms AglaSem · NCERT Solutions

IDEA IN SYMBOLS / WHAT IT SAYS WHERE STUDENTS SLIP
STATEMENT

Efficiency work ∝ value vs Counting dots and checking Thinking “correct” also
work ∝ digits every j are slow; columns and means “fast”
division are fast

prime(n) divisors(n) has 1 and n are the only divisors Calling 1 a prime (it has only 1
exactly 2 elements divisor)

Page 30 of 30