Top
Learning Spot
Menu

Chapter 11 The World of Algorithms (Class 9 - Latest Maths NCERT (Ganita Manjari II) Solutions)

Looking for clear and accurate NCERT Solutions for Chapter 11: The World of Algorithms? You’ve come to the right place! This page provides step-by-step answers to help you understand algorithms and the importance of following a logical sequence of instructions to solve problems. Through structured explanations, you can learn how mathematical procedures are organised and how each step contributes to reaching a correct result.

Our solutions break down problem-solving procedures into manageable steps, making it easier to understand the logic behind a method. You will learn to follow instructions in the correct order, examine the results of each step, and recognise the importance of accuracy when applying a procedure. The worked solutions are designed to help you approach algorithm-based exercises systematically rather than memorising steps without understanding them.

Whether you are practising textbook questions or developing a stronger foundation in logical and computational thinking, these resources will help you work through problems with greater confidence. Curated by learningspot.co based on the Ganita Manjari II textbook, our solutions provide clear explanations and step-by-step answers to support your Class 9 Mathematics preparation.

Content On This Page
Exercise Set 11.1 Exercise Set 11.2 Exercise Set 11.3
End-of-Chapter Exercises


Exercise Set 11.1

Question 1. 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?

Answer:

Given:

Let us take two $4$-digit numbers: $4582$ and $3764$.

To Find:

The sum of $4582$ and $3764$ by following the standard addition algorithm step by step, and verify whether the result obtained is correct.


Solution:

Write the two numbers one below the other, aligning the digits from right to left:

$$\begin{array}{ccccc} & 4 & 5 & 8 & 2 \\ + & 3 & 7 & 6 & 4 \\ \hline \end{array}$$

Step 1: The digits are aligned from right to left (units under units, tens under tens, hundreds under hundreds, and thousands under thousands).

Step 2: Add the units digits:

$2 + 4 = 6$

Write $6$ in the units place.

Step 3: Add the tens digits:

$8 + 6 = 14$

Write $4$ in the tens place and carry $1$ over to the hundreds place.

Step 4: Add the hundreds digits along with the carry:

$5 + 7 + 1 = 13$

Write $3$ in the hundreds place and carry $1$ over to the thousands place.

Step 5: Now add the thousands digits along with the carry:

$4 + 3 + 1 = 8$

Write $8$ in the thousands place.


Final Addition with Carries:

$$\begin{array}{ccccc} & \overset{1}{4} & \overset{1}{5} & 8 & 2 \\ + & 3 & 7 & 6 & 4 \\ \hline & 8 & 3 & 4 & 6 \\ \hline \end{array}$$

Therefore, $4582 + 3764 = \mathbf{8346}$.

Yes, following the algorithm precisely gives the correct result.

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

Answer:

Analysis:

When we add a $5$-digit number to a $3$-digit number and align the digits from right to left, the $3$-digit number only fills the units, tens, and hundreds places, leaving the thousands and ten-thousands places empty (blank).

Yes, our steps handle this situation correctly, provided two essential details are followed in the algorithm:

1. Any blank spaces to the left of the shorter ($3$-digit) number are treated as $0$.

2. The step of adding column-by-column (along with any carry) continues up to the leftmost digit of the $5$-digit number (and writes down a new leftmost digit if a final carry remains).

(Note: If an algorithm were written strictly for $4$-digit numbers without mentioning blank places as $0$ or repeating for all digits of the longer number, it would stop too early or fail at the thousands and ten-thousands places.)


Example Demonstration:

Let us add a $5$-digit number $29874$ and a $3$-digit number $658$:

$$\begin{array}{cccccc} & 2 & 9 & 8 & 7 & 4 \\ + & 0 & 0 & 6 & 5 & 8 \\ \hline \end{array}$$

Step 1: Align the digits from right to left. Treat the blank thousands and ten-thousands places of $658$ as $0$ (i.e., $00658$).

Step 2: Add the units digits:

$4 + 8 = 12$

Write $2$ in the units place and carry $1$ over to the tens place.

Step 3: Add the tens digits along with the carry:

$7 + 5 + 1 = 13$

Write $3$ in the tens place and carry $1$ over to the hundreds place.

Step 4: Add the hundreds digits along with the carry:

$8 + 6 + 1 = 15$

Write $5$ in the hundreds place and carry $1$ over to the thousands place.

Step 5: Add the thousands digits (treating the blank space as $0$) along with the carry:

$9 + 0 + 1 = 10$

Write $0$ in the thousands place and carry $1$ over to the ten-thousands place.

Step 6: Add the ten-thousands digits (treating the blank space as $0$) along with the carry:

$2 + 0 + 1 = 3$

Write $3$ in the ten-thousands place.


Final Addition with Carries:

$$\begin{array}{cccccc} & \overset{1}{2} & \overset{1}{9} & \overset{1}{8} & \overset{1}{7} & 4 \\ + & 0 & 0 & 6 & 5 & 8 \\ \hline & 3 & 0 & 5 & 3 & 2 \\ \hline \end{array}$$

Therefore, $29874 + 658 = \mathbf{30532}$.

Notice that the carry from the hundreds place ($1$) propagates into the thousands place and even into the ten-thousands place! Thus, treating blank places on the left as $0$ and continuing the addition step across all columns gives the exact, correct sum.

Question 3. Why is it important to align the columns from right to left?

Answer:

Key Reason (Matching Place Values):

It is important to align the columns from right to left so that digits having the same place value lie directly in the same vertical column.

In our decimal (base-$10$) number system, the rightmost digit of any whole number is always the units place ($10^0$), the next digit to the left is the tens place ($10^1$), followed by the hundreds place ($10^2$), thousands place ($10^3$), and so on.


Detailed Explanation:

1. Adding only like place values: We can only add units to units, tens to tens, hundreds to hundreds, and so on. Aligning from right to left guarantees that each column represents the same place value, even when the two numbers have different numbers of digits.

2. Proper carry propagation: When the sum of digits in any column is $10$ or more, the carry moves to the next higher place value (one column to the left). Right-to-left alignment ensures that carries are always added to the correct place value.

3. What goes wrong if we align from left to right:

Consider adding $1234$ and $56$:

If aligned incorrectly from left to right, the tens digit $5$ would sit under the thousands digit $1$, and the units digit $6$ would sit under the hundreds digit $2$, giving the wrong sum $6834$ (effectively adding $1234 + 5600$):

$\begin{array}{ccccc} & 1 & 2 & 3 & 4 \\ + & 5 & 6 & & \\ \hline & 6 & 8 & 3 & 4 \\ \hline \end{array} \quad \text{(Incorrect alignment)}$

When aligned properly from right to left, units line up with units and tens with tens, giving the exact sum $1290$:

$\begin{array}{ccccc} & 1 & 2 & \overset{1}{3} & 4 \\ + & & & 5 & 6 \\ \hline & 1 & 2 & 9 & 0 \\ \hline \end{array} \quad \text{(Correct alignment)}$


Conclusion:

Aligning columns from right to left ensures that digits of equal place value are added together and carries move accurately to the next higher place value.

Question 4. In Step 3, why cannot the value of carry be more than 1?

Answer:

Given:

We are adding two numbers column by column from right to left, where every digit in a number lies between $0$ and $9$.

To Explain:

Why the carry generated in Step 3 (the tens place, or any column when adding two numbers) cannot be greater than $1$.


Solution:

In the decimal (base-$10$) number system, the largest possible single digit is $9$.

1. Maximum carry from the units place (Step 2):

In the units column, there is no incoming carry. Even in the largest case ($9 + 9$), the sum is:

$9 + 9 = 18$

Since $18 < 20$, the carry passed from the units place to the tens place is at most $1$.

2. Maximum possible sum in Step 3 (tens place):

In Step 3, we add the two tens digits together with the incoming carry from the units place.

Even if both tens digits are the maximum possible digit ($9$) and the incoming carry is the maximum possible carry ($1$), the largest possible sum in Step 3 is:

$9 + 9 + 1 = 19$

(Maximum possible sum in Step 3)

For the carry to be $2$ or more, the sum in the column would have to be at least $20$.

Since the maximum sum $19$ is strictly less than $20$ ($19 < 20$), the sum in Step 3 can only lie in one of two ranges:

$\bullet$ From $0$ to $9$: carry $= 0$.

$\bullet$ From $10$ to $19$: carry $= 1$.

Example (Extreme Maximum Case): Adding $99$ and $99$:

$\begin{array}{cccc} & \overset{1}{9} & 9 \\ + & 9 & 9 \\ \hline 1 & 9 & 8 \\ \hline \end{array}$

Even with the largest possible $2$-digit numbers, the carry from the tens place is still only $1$.


Conclusion:

Because the sum of two digits and an incoming carry of at most $1$ can never reach $20$ ($9 + 9 + 1 = 19 < 20$), the value of the carry in Step 3 can never be more than $1$.

(Note: This holds when adding two numbers; if three or more numbers are added simultaneously, the carry can be $2$ or greater.)

Question 5. 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.

Answer:

Role of the Fifth Step:

In the addition algorithm, the fifth step checks whether a non-zero carry ($1$) remains after adding the leftmost column of digits and, if so, writes that carry as a new leftmost digit in the sum.

If we do not include the fifth step, any final carry generated from the leftmost column is ignored (dropped).

$\bullet$ The algorithm will work correctly whenever the sum of the leftmost digits (plus any incoming carry) is less than $10$ (so the final carry is $0$).

$\bullet$ The algorithm will fail to work whenever the sum of the leftmost digits (plus any incoming carry) is $10$ or more (so the final carry is $1$), because the extra leftmost digit $1$ will be missing from the answer.


Example 1: Where the Algorithm Works Correctly (Final Carry $= 0$)

Consider adding $4582$ and $3764$:

$\begin{array}{ccccc} & \overset{1}{4} & \overset{1}{5} & 8 & 2 \\ + & 3 & 7 & 6 & 4 \\ \hline & 8 & 3 & 4 & 6 \\ \hline \end{array}$

Here, in the leftmost (thousands) column, $4 + 3 + 1 = 8 < 10$, so there is no final carry.

Even without the fifth step, the algorithm outputs $8346$, which is the exact correct sum.


Example 2: Where the Algorithm Fails to Work (Final Carry $= 1$)

Consider adding $6582$ and $5764$:

Step-by-step up to the leftmost column:

$\bullet$ Units place: $2 + 4 = 6$ (write $6$, carry $= 0$).

$\bullet$ Tens place: $8 + 6 = 14$ (write $4$, carry $= 1$).

$\bullet$ Hundreds place: $5 + 7 + 1 = 13$ (write $3$, carry $= 1$).

$\bullet$ Thousands (leftmost) place: $6 + 5 + 1 = 12$ (write $2$, final carry $= 1$).

Without the fifth step (Incorrect Result): The final carry $1$ is not written down, so the algorithm stops and gives $2346$:

$\begin{array}{ccccc} & \overset{1}{6} & \overset{1}{5} & 8 & 2 \\ + & 5 & 7 & 6 & 4 \\ \hline & 2 & 3 & 4 & 6 \\ \hline \end{array} \quad \text{(Wrong: missing leading } 1\text{)}$

With the fifth step (Correct Result): Writing the final carry $1$ in the ten-thousands place gives the true sum $12346$:

$\begin{array}{cccccc} & & \overset{1}{6} & \overset{1}{5} & 8 & 2 \\ + & & 5 & 7 & 6 & 4 \\ \hline & 1 & 2 & 3 & 4 & 6 \\ \hline \end{array} \quad \text{(Correct sum)}$


Conclusion:

Omitting the fifth step causes the algorithm to lose the leftmost digit $1$ whenever the addition produces a final carry, making the result incorrect (for example, $6582 + 5764$ gives $2346$ instead of $12346$).



Exercise Set 11.2

Question 1. 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.

Answer:

Given:

Suppose List 1 is $L_1$ and List 2 is $L_2$, and both lists are arranged in increasing order.


(i) Algorithm to find elements in List 1 that are not present in List 2:

We can use two positions (pointers), one for each list.

Algorithm I:

Step 1: Start with the first element of List 1 and the first element of List 2.

Step 2: Compare the current elements of the two lists.

Step 3: If the element in List 1 is smaller than the element in List 2, add the List 1 element to the answer list and move to the next element of List 1.

Step 4: If the two elements are equal, do not add the element and move to the next element in both lists.

Step 5: If the element in List 1 is greater than the element in List 2, move to the next element of List 2 (do not add the List 1 element yet, as it may appear later in List 2).

Step 6: Repeat Steps 2–5 until either list is exhausted.

Step 7: If elements of List 1 are still left, add all of them to the answer list.

Example: Let $L_1 = [2, 4, 6, 8, 12, 15]$ and $L_2 = [3, 4, 7, 12, 14]$.

The elements of $L_1$ not present in $L_2$ are: $[2, 6, 8, 15]$.


(ii) Algorithm to find elements in List 2 that are not present in List 1:

The same idea can be reversed by interchanging List 1 and List 2.

Algorithm II:

Step 1: Start with the first element of List 2 and the first element of List 1.

Step 2: Compare the current elements of the two lists.

Step 3: If the element in List 2 is smaller than the element in List 1, add the List 2 element to the answer list and move to the next element of List 2.

Step 4: If the two elements are equal, do not add the element and move to the next element in both lists.

Step 5: If the element in List 2 is greater than the element in List 1, move to the next element of List 1 (do not add the List 2 element yet, as it may appear later in List 1).

Step 6: Repeat Steps 2–5 until either list is exhausted.

Step 7: If elements of List 2 are still left, add all of them to the answer list.

For the same example:

$L_1 = [2, 4, 6, 8, 12, 15]$ and $L_2 = [3, 4, 7, 12, 14]$.

The elements of $L_2$ not present in $L_1$ are: $[3, 7, 14]$.

Question 2. Describe an algorithm to compute the least common multiple ($\text{lcm}$) of two numbers.

Answer:

Given:

Let the two positive integers be $m$ and $n$.

To Describe:

An algorithm to compute $\text{lcm}(m, n)$.


Algorithm to Find $\text{lcm}(m, n)$ (By Generating Multiples):

One direct algorithm is to generate the multiples of $m$ one by one and find the first multiple that is divisible by $n$.

Step 1: Start with $j = 1$.

Step 2: Compute $j \times m$.

Step 3: Check whether $j \times m$ is divisible by $n$.

Step 4: If $j \times m$ is divisible by $n$, report $j \times m$ as the $\text{lcm}$ and stop.

Step 5: Otherwise, increase $j$ by $1$ ($j \leftarrow j + 1$).

Step 6: Repeat Steps 2–5.


Example: Find the $\text{lcm}$ of $12$ and $18$

Here, $m = 12$ and $n = 18$.

Iteration 1 ($j = 1$):

$j \times m = 1 \times 12 = 12$

$12 \div 18 = \frac{\cancel{12}^{2}}{\cancel{18}_{3}} = \frac{2}{3}$ (Not divisible by $18$)

Increase $j$ to $2$.

Iteration 2 ($j = 2$):

$j \times m = 2 \times 12 = 24$

$24 \div 18 = \frac{\cancel{24}^{4}}{\cancel{18}_{3}} = \frac{4}{3}$ (Not divisible by $18$)

Increase $j$ to $3$.

Iteration 3 ($j = 3$):

$j \times m = 3 \times 12 = 36$

$36 \div 18 = \frac{\cancel{36}^{2}}{\cancel{18}_{1}} = 2$ (Yes, divisible by $18$)

Stop and report $36$ as the $\text{lcm}$.

Therefore, $\text{lcm}(12, 18) = 36$.


Alternate Method / Verification (Common Division Method & GCD Formula):

Using the common division method for $12$ and $18$:

$$\begin{array}{c|cc} 2 & 12 \;, & 18 \\ \hline 3 & 6 \; , & 9 \\ \hline & 2 \; , & 3 \end{array}$$

$\text{lcm}(12, 18) = 2 \times 3 \times 2 \times 3 = 36$

(Note: For large numbers, a faster algorithm is to compute $\gcd(m, n)$ using Euclid's algorithm and then use $\text{lcm}(m, n) = \frac{m \times n}{\gcd(m, n)}$.)

Question 3. 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?

Answer:

Given:

Divisors of a positive integer $n$ occur in pairs $(d, \frac{n}{d})$.

To Find:

(i) How many numbers between $1$ and $n$ must be examined to find all divisors of $n$.

(ii) Whether the earlier $\gcd$ algorithm still works if divisors are listed in pairs.


Part (i): Number of Values to Examine

Suppose $d$ is a divisor of $n$. Then its paired (partner) divisor is $\frac{n}{d}$.

Once we find a divisor $d$, we automatically know its partner $\frac{n}{d}$.

In any pair $(d, \frac{n}{d})$, if one factor is greater than $\sqrt{n}$, the other factor must be less than $\sqrt{n}$.

The two factors in the pair meet when they are equal:

$d = \frac{n}{d} \implies d^2 = n \implies d = \sqrt{n}$

Therefore, we only need to examine the whole numbers from $1$ up to $\lfloor \sqrt{n} \rfloor$ (i.e., the greatest integer less than or equal to $\sqrt{n}$), rather than all numbers from $1$ to $n$.

Example: For $n = 18$, we have $\sqrt{18} \approx 4.24$.

So we only need to examine $4$ numbers: $1, 2, 3,$ and $4$.

$\bullet$ $d = 1$ divides $18$ $\rightarrow$ pair $(1, 18)$

$\bullet$ $d = 2$ divides $18$ $\rightarrow$ pair $(2, 9)$

$\bullet$ $d = 3$ divides $18$ $\rightarrow$ pair $(3, 6)$

$\bullet$ $d = 4$ does not divide $18$.

Thus, all divisors of $18$ are obtained: $1, 2, 3, 6, 9, 18$.


Part (ii): Will Our $\gcd$ Algorithm Still Work?

No, not in the exact manner described earlier in the chapter.

Reason: The earlier $\gcd$ algorithm assumes that the divisor lists of both numbers are arranged in increasing order, allowing it to scan them together (or pick the rightmost common element).

If we list the divisors of $18$ in pairs as they are found—$(1, 18)$, $(2, 9)$, $(3, 6)$—the resulting list is:

$1, 18, 2, 9, 3, 6$

This list is not in increasing order, which breaks the assumption that the original $\gcd$ algorithm relies on.

How it can still be used (Modification):

We can adapt the paired method successfully in either of two ways:

1. Keep track of the largest common divisor found so far while checking all divisors from the pairs, or

2. Write the smaller divisors ($1, 2, 3$) in increasing order and append the larger partner divisors ($6, 9, 18$) in reverse order so the combined list is in increasing order.



Exercise Set 11.3

Question 1. 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$?

Answer:

Comparison with the Original Algorithm:

In the original algorithm, we examine the numbers from $1$ to $n$ in increasing order ($1, 2, 3, \dots, n$) and add a number to the divisor list whenever it divides $n$. Therefore, the divisors are obtained in increasing order.

If we instead examine the numbers in reverse order ($n, n - 1, n - 2, \dots, 1$), the main change is simply the direction of the loop and the order of the output: the divisors of $n$ will now be obtained in decreasing order.

Example: For $n = 18$, instead of obtaining $1, 2, 3, 6, 9, 18$, we obtain:

$18, 9, 6, 3, 2, 1$


Modified Algorithm (To Find Divisors of $n$ in Decreasing Order):

Step 1: Start with an empty list called list-of-divisors.

Step 2: For each number $j$ in the sequence $n, n - 1, n - 2, \dots, 1$:

If $j$ divides $n$ (i.e., remainder when $n$ is divided by $j$ is $0$), add $j$ to list-of-divisors.

Step 3: Output list-of-divisors and stop. The resulting list contains all divisors of $n$ in decreasing order.


Effect on Finding the $\gcd$:

Because the divisors are now listed from largest to smallest (decreasing order), if we use this in our $\gcd$ algorithm for two numbers, the very first (leftmost) common divisor encountered while scanning the two lists from left to right will directly be the greatest common divisor ($\gcd$), allowing the search to stop immediately.

Question 2. 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$?

Answer:

Key Observation:

The largest possible common divisor of two positive integers $m$ and $n$ cannot be greater than $\min(m, n)$.

When we check common divisors starting from $1$ up to $\min(m, n)$, we have to check every number up to $\min(m, n)$ to make sure we do not miss a larger common divisor.

However, if we start from $\min(m, n)$ and work backwards toward $1$, the very first number that divides both $m$ and $n$ is guaranteed to be their greatest common divisor ($\gcd$), so we can stop immediately without checking any smaller numbers or storing a list of divisors.


Modified Algorithm (Working Backwards from $\min(m, n)$ to $1$):

Step 1: Let $k = \min(m, n)$.

Step 2: Check whether $k$ divides both $m$ and $n$.

Step 3: If $k$ divides both $m$ and $n$, report $k$ as the $\gcd(m, n)$ and stop.

Step 4: Otherwise, decrease $k$ by $1$ ($k \leftarrow k - 1$).

Step 5: Repeat Steps 2–4 until a common divisor is found (in the worst case, $k = 1$ always divides both $m$ and $n$).


Example: Find $\gcd(375, 825)$

Here, $m = 375$ and $n = 825$, so $\min(375, 825) = 375$.

Starting from $k = 375$ and working backwards ($375, 374, 373, \dots$):

The first number that divides both $375$ and $825$ is $75$:

$\frac{\cancel{375}^{5}}{\cancel{75}_{1}} = 5 \quad \text{and} \quad \frac{\cancel{825}^{11}}{\cancel{75}_{1}} = 11$

At $k = 75$, the algorithm stops immediately without having to test $74, 73, \dots, 1$.

Therefore, $\gcd(375, 825) = 75$.



End-of-Chapter Exercises

Question 1. Compute the following using the improved version of Euclid’s algorithm.

(i) $\gcd(375, 825)$

(ii) $\gcd(51000, 81000)$

(iii) $\gcd(1789287, 237656)$

(iv) $\gcd(2587392, 157656)$

Answer:

Rule of Improved Euclid's Algorithm:

Write the larger number first as $m$ and the smaller number second as $n$.

Replace $(m, n)$ with $(n, m \bmod n)$ repeatedly until the second number becomes $0$.

When the pair becomes $(g, 0)$, the value $g$ is the $\gcd$.


Part (i): $\gcd(375, 825)$

Start with $\gcd(825, 375)$.

1. $825 = 2 \times 375 + 75 \implies 825 \bmod 375 = 75$.

So, $\gcd(825, 375) = \gcd(375, 75)$.

2. $375 = 5 \times 75 + 0 \implies 375 \bmod 75 = 0$.

So, $\gcd(375, 75) = \gcd(75, 0) = 75$.

Therefore, $\gcd(375, 825) = \mathbf{75}$.


Part (ii): $\gcd(51000, 81000)$

Start with $\gcd(81000, 51000)$.

1. $81000 = 1 \times 51000 + 30000 \implies \gcd(51000, 30000)$

2. $51000 = 1 \times 30000 + 21000 \implies \gcd(30000, 21000)$

3. $30000 = 1 \times 21000 + 9000 \implies \gcd(21000, 9000)$

4. $21000 = 2 \times 9000 + 3000 \implies \gcd(9000, 3000)$

5. $9000 = 3 \times 3000 + 0 \implies \gcd(3000, 0) = 3000$

Therefore, $\gcd(51000, 81000) = \mathbf{3000}$.


Part (iii): $\gcd(1789287, 237656)$

Start with $\gcd(1789287, 237656)$.

1. $1789287 = 7 \times 237656 + 125695 \implies \gcd(237656, 125695)$

2. $237656 = 1 \times 125695 + 111961 \implies \gcd(125695, 111961)$

3. $125695 = 1 \times 111961 + 13734 \implies \gcd(111961, 13734)$

4. $111961 = 8 \times 13734 + 2089 \implies \gcd(13734, 2089)$

5. $13734 = 6 \times 2089 + 1200 \implies \gcd(2089, 1200)$

6. $2089 = 1 \times 1200 + 889 \implies \gcd(1200, 889)$

7. $1200 = 1 \times 889 + 311 \implies \gcd(889, 311)$

8. $889 = 2 \times 311 + 267 \implies \gcd(311, 267)$

9. $311 = 1 \times 267 + 44 \implies \gcd(267, 44)$

10. $267 = 6 \times 44 + 3 \implies \gcd(44, 3)$

11. $44 = 14 \times 3 + 2 \implies \gcd(3, 2)$

12. $3 = 1 \times 2 + 1 \implies \gcd(2, 1)$

13. $2 = 2 \times 1 + 0 \implies \gcd(1, 0) = 1$

Therefore, $\gcd(1789287, 237656) = \mathbf{1}$.


Part (iv): $\gcd(2587392, 157656)$

Start with $\gcd(2587392, 157656)$.

1. $2587392 = 16 \times 157656 + 64896 \implies \gcd(157656, 64896)$

2. $157656 = 2 \times 64896 + 27864 \implies \gcd(64896, 27864)$

3. $64896 = 2 \times 27864 + 9168 \implies \gcd(27864, 9168)$

4. $27864 = 3 \times 9168 + 360 \implies \gcd(9168, 360)$

5. $9168 = 25 \times 360 + 168 \implies \gcd(360, 168)$

6. $360 = 2 \times 168 + 24 \implies \gcd(168, 24)$

7. $168 = 7 \times 24 + 0 \implies \gcd(24, 0) = 24$

Therefore, $\gcd(2587392, 157656) = \mathbf{24}$.

Question 2. Assume that $m \ge n$. Verify that $d$ divides $m$ and $n$ if and only if $d$ divides both $n$ and $m \bmod n$.

Answer:

Given:

Two positive integers $m$ and $n$ such that $m \ge n$, and a positive integer $d$.

To Prove:

$d$ divides $m$ and $n$ $\iff$ $d$ divides $n$ and $(m \bmod n)$.


Proof:

By the division algorithm, on dividing $m$ by $n$, there exist a quotient $q$ and a remainder $r$ such that:

$m = qn + r$

(where $r = m \bmod n$ and $0 \le r < n$)           ... (i)

To prove an “if and only if” statement, we prove both directions:

1. Forward Direction (If $d$ divides $m$ and $n$, then $d$ divides $n$ and $r$):

Suppose $d$ divides both $m$ and $n$.

Then $m = da$ and $n = db$ for some integers $a$ and $b$.

From equation (i), we have:

$r = m - qn$

$r = da - q(db)$

$r = d(a - qb)$

Since $(a - qb)$ is an integer, $d$ divides $r$, i.e., $d$ divides $(m \bmod n)$.

Hence, $d$ divides both $n$ and $(m \bmod n)$.

2. Converse Direction (If $d$ divides $n$ and $r$, then $d$ divides $m$ and $n$):

Conversely, suppose $d$ divides both $n$ and $r = m \bmod n$.

Then $n = db$ and $r = dc$ for some integers $b$ and $c$.

From equation (i), we have:

$m = qn + r$

$m = q(db) + dc$

$m = d(qb + c)$

Since $(qb + c)$ is an integer, $d$ divides $m$.

Hence, $d$ divides both $m$ and $n$.


Conclusion:

Combining both parts, we conclude:

$d \mid m$ and $d \mid n \iff d \mid n$ and $d \mid (m \bmod n)$

(Remark: Since $(m, n)$ and $(n, m \bmod n)$ have the exact same set of common divisors, their greatest common divisor is also the same, i.e., $\gcd(m, n) = \gcd(n, m \bmod n)$, which is the foundation of Euclid's algorithm.)

Question 3. Write an algorithm $\text{prime}(n)$ to check if $n$ is prime.

(Hint: A prime number $p$ has exactly two distinct factors, $1$ and $p$. Can you make use of $\text{divisors}(n)$ to write out $\text{prime}(n)$?)

Answer:

Given:

An integer $n$, and an existing algorithm $\text{divisors}(n)$ that returns the list of all positive divisors of $n$.

To Write:

An algorithm $\text{prime}(n)$ to check whether $n$ is a prime number.


Solution:

By definition, a prime number has exactly two distinct positive divisors: $1$ and itself.

For $n < 2$ (such as $n = 1$ or $n \le 0$), $n$ does not have two distinct positive divisors, so we report False.

For $n \ge 2$, we compute $\text{divisors}(n)$. If the resulting list contains exactly $2$ elements, we report True; otherwise, we report False.

Algorithm $\text{prime}(n)$:

Step 1: If $n < 2$, report False and stop.

Step 2: Let $L = \text{divisors}(n)$.

Step 3: If the number of elements in $L$ is equal to $2$, report True.

Step 4: Otherwise, report False.


Examples:

1. For $n = 7$:

$L = \text{divisors}(7) = [1, 7]$

The list $L$ has exactly $2$ elements.

Therefore, $\text{prime}(7) = \text{True}$.

2. For $n = 12$:

$L = \text{divisors}(12) = [1, 2, 3, 4, 6, 12]$

The list $L$ has $6$ elements (more than $2$).

Therefore, $\text{prime}(12) = \text{False}$.

3. For $n = 1$:

Since $1 < 2$, Step 1 immediately reports $\text{prime}(1) = \text{False}$.


Alternate Algorithm (Faster Check Without Generating the Full Divisor List):

Step 1: If $n < 2$, report False and stop.

Step 2: For each integer $d$ from $2$ up to $\lfloor \sqrt{n} \rfloor$:

If $d$ divides $n$ (i.e., $n \bmod d = 0$), report False and stop.

Step 3: If no divisor was found in Step 2, report True.

Question 4. Write an algorithm $\text{prime divisors}(n)$ to compute the list of divisors of $n$ that are prime numbers.

(Hint: Compute $\text{divisors}(n)$ and then filter out the primes in this list.)

Answer:

Given:

A positive integer $n$, along with existing algorithms $\text{divisors}(n)$ (which returns all positive divisors of $n$) and $\text{prime}(d)$ (which checks whether $d$ is prime).

To Write:

An algorithm $\text{prime divisors}(n)$ to compute the list of all prime divisors of $n$.


Algorithm $\text{prime divisors}(n)$:

Step 1: Let $L$ be the list obtained by computing $\text{divisors}(n)$.

Step 2: Start with an empty list called prime-divisors.

Step 3: For each number $d$ in $L$:

If $\text{prime}(d)$ is True, add $d$ to prime-divisors.

Step 4: Report prime-divisors and stop.


Example: Find $\text{prime divisors}(60)$

First, compute all divisors of $60$:

$L = \text{divisors}(60) = [1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60]$

Now, filter out the prime numbers from $L$ by checking $\text{prime}(d)$ for each divisor $d$:

$\bullet$ $\text{prime}(2) = \text{True}$, $\text{prime}(3) = \text{True}$, $\text{prime}(5) = \text{True}$.

$\bullet$ For all remaining divisors ($1, 4, 6, 10, 12, 15, 20, 30, 60$), $\text{prime}(d) = \text{False}$.

Thus, $\text{prime divisors}(60) = [2, 3, 5]$.


Alternate Method / Verification (Repeated Division / Prime Factorisation):

We can also find the prime divisors of $n$ directly by dividing $n$ repeatedly by the smallest prime $d \ge 2$ that divides it (without listing composite divisors first).

For $n = 60$, performing prime factorisation:

$$\begin{array}{c|cc} 2 & 60 \\ \hline 2 & 30 \\ \hline 3 & 15 \\ \hline 5 & 5 \\ \hline & 1 \end{array}$$

$60 = 2 \times 2 \times 3 \times 5$

Taking each distinct prime factor once gives the prime divisors of $60$: $[2, 3, 5]$.

Question 5. 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 $2^2 \times 3^2 \times 5^1$. How would you represent this?

(ii) How would you compare the prime factorisations of two numbers?

Answer:

Algorithm to Compute the Prime Factorisation of a Number $n$ ($n \ge 2$):

Step 1: Start with an empty list called prime-factors and set $d = 2$.

Step 2: While $n > 1$:

(a) If $d$ divides $n$, set $\text{count} = 0$.

(b) While $d$ divides $n$, divide $n$ by $d$ ($n \leftarrow \frac{n}{d}$) and increase $\text{count}$ by $1$.

(c) If $\text{count} > 0$, add the pair $(d, \text{count})$ to prime-factors.

(d) Increase $d$ by $1$ ($d \leftarrow d + 1$).

Step 3: Report prime-factors and stop.

(Note: Because we test divisors in increasing order starting from $2$ and divide out each factor completely, every $d$ added to the list is guaranteed to be a prime number.)

Example ($n = 180$):

$$\begin{array}{c|cc} 2 & 180 \\ \hline 2 & 90 \\ \hline 3 & 45 \\ \hline 3 & 15 \\ \hline 5 & 5 \\ \hline & 1 \end{array}$$

$180 = 2^2 \times 3^2 \times 5^1$


Part (i): Representing the Prime Factorisation of $180$

We are given: $180 = 2^2 \times 3^2 \times 5^1$.

A convenient representation is as a list of $(\text{prime}, \text{exponent})$ pairs (arranged in increasing order of primes):

$[(2, 2),\ (3, 2),\ (5, 1)]$

Here, prime $2$ has exponent $2$, prime $3$ has exponent $2$, and prime $5$ has exponent $1$.

Another possible representation is as a key-value mapping (dictionary) associating each prime with its exponent:

$\{2 : 2,\ 3 : 2,\ 5 : 1\}$


Part (ii): Comparing the Prime Factorisations of Two Numbers

Suppose two numbers have prime factorisations of the form $A = 2^a \times 3^b \times 5^c \dots$ and $B = 2^d \times 3^e \times 5^f \dots$

To compare their prime factorisations:

1. List all the primes appearing in either factorisation (in increasing order).

2. For each prime, compare its exponent in $A$ and in $B$.

3. Any prime missing from one of the factorisations is treated as having exponent $0$.

4. For finding the $\gcd$, take the smaller (minimum) exponent for every prime.

5. For finding the $\text{lcm}$, take the larger (maximum) exponent for every prime appearing in either number.

Example: Suppose $A = 2^3 \times 3^2 \times 5^1$ and $B = 2^2 \times 3^1 \times 7^1$.

Prime Exponent in $A$ Exponent in $B$ Smaller Exponent (for $\gcd$) Larger Exponent (for $\text{lcm}$)
$2$$3$$2$$2$$3$
$3$$2$$1$$1$$2$
$5$$1$$0$$0$$1$
$7$$0$$1$$0$$1$

Therefore:

$\gcd(A, B) = 2^2 \times 3^1 \times 5^0 \times 7^0 = 2^2 \times 3 = 12$

$\text{lcm}(A, B) = 2^3 \times 3^2 \times 5^1 \times 7^1 = 2520$

Thus, prime factorisations provide another systematic way to compute both the $\gcd$ and the $\text{lcm}$ alongside Euclid's algorithm.