Chapter Overview
Chapter 11 develops the idea of an algorithm as an exact sequence of steps. The chapter applies this idea to addition, lists, divisors, least common multiples and greatest common divisors.
These worked solutions show the mathematical reasoning behind selected exercise questions and end-of-chapter problems.
Textbook-check note: Use the exact question numbers and diagrams in your copy of Ganita Manjari. Where data are read from a graph, answers are marked as estimates. This page does not reproduce every printed exercise verbatim.
Important Concepts
| Concept | Explanation |
|---|---|
| Algorithm | A finite sequence of precise steps that solves a problem. |
| Carry in addition | When a column total is 10 or more, write its units digit and carry the tens digit. |
| Divisor | A positive integer d is a divisor of n when n divided by d has remainder 0. |
| LCM | The least positive integer that is a multiple of each of the given integers. |
| Euclid’s algorithm | Repeatedly replace (m,n) by (n, remainder of m÷n); the last non-zero remainder is the GCD. |
Exercise Solutions — Chapter 11
Exercise Set 11.1 — Addition algorithms
Question 1 — The missing case when a column total equals 10
If the instructions separately say “less than 10” and “greater than 10”, they omit the case exactly equal to 10. Replace the condition by “10 or more”: write the units digit and carry 1.
Example: 4586 + 3414. The units-column total is 6 + 4 = 10, so write 0 and carry 1. Continuing the addition gives 8000.
Question 2 — Adding numbers with different digit counts
Align the numbers at the units column and treat missing leading digits as zero.
12345 + 321 = 12345 + 00321 = 12666.
Question 4 — Why is carry at most 1?
Adding two digits and a carry gives at most 9 + 9 + 1 = 19. The tens digit of any total from 10 through 19 is 1, so the carry can only be 0 or 1.
Question 5 — Omitting the final-carry step
Without the step that writes the final carry at the left, the algorithm works only when the last column creates no carry. Example that works: 1234 + 4321 = 5555. Example that fails: 9999 + 9999 should be 19998; if the final carry is omitted, the result is incorrectly written as 9998.
Exercise Set 11.2 — Divisors and lists
Question — Divisors of 135 and 775
For 135, the positive divisors are 1, 3, 5, 9, 15, 27, 45, 135.
For 775 = 5²×31, the positive divisors are 1, 5, 25, 31, 155, 775.
The straightforward algorithm tests every integer from 1 to n, so it performs n divisibility checks; this can be improved by checking only to √n and listing factor pairs.
Question — Difference of two sorted lists
To find items in List A that are absent from List B, move through both sorted lists in order. If the current A item is smaller than the current B item, output it; if they match, advance both without output; if A is larger, advance B. Reverse the roles to find B\A. Since the lists are sorted, each list needs to be scanned only once.
Exercise Set 11.3 — GCD and LCM algorithms
Question — GCD by descending common divisors
For 12 and 18, check candidate divisors from min(12,18)=12 downwards. 12, 11, 10, 9, 8 and 7 do not divide both numbers; 6 divides both. Therefore gcd(12,18)=6, and the search may stop immediately.
Question — An algorithm for the LCM
List the positive multiples of each number in increasing order and find the first common one. For 4 and 6, the lists begin [4,8,12,16,…] and [6,12,18,…]; the first common multiple is 12, so lcm(4,6)=12.
End-of-Chapter Exercises
Question 1 — Use Euclid’s algorithm
(i) 825 = 375×2 + 75; 375 = 75×5 + 0. Hence gcd(375,825)=75.
(ii) 81000 = 51000×1 + 30000; 51000 = 30000×1 + 21000; 30000 = 21000×1 + 9000; 21000 = 9000×2 + 3000; 9000 = 3000×3 + 0. Hence gcd(51000,81000)=3000.
(iii) Repeated division ends with 3 = 2×1 + 1 and 2 = 1×2 + 0, so gcd(1789287,237656)=1.
(iv) 2587392 = 157656×16 + 64896; 157656 = 64896×2 + 27864; 64896 = 27864×2 + 9168; 27864 = 9168×3 + 360; 9168 = 360×25 + 168; 360 = 168×2 + 24; 168 = 24×7 + 0. Thus gcd(2587392,157656)=24.
Question 2 — Why the remainder keeps the same common divisors
Write m = qn + r, where r = m mod n. If d divides both m and n, it divides r = m − qn. Conversely, if d divides n and r, it divides m = qn + r. Thus d is a common divisor of m,n exactly when it is a common divisor of n,r, so gcd(m,n)=gcd(n,r).
One Minute Revision
- An algorithm must be unambiguous and must stop after finitely many steps.
- In column addition, the carry may be 0 or 1 when adding two digits and an earlier carry.
- Missing leading digits are treated as zeros.
- For m≥n>0, gcd(m,n)=gcd(n,m mod n).
- The last non-zero remainder of Euclid’s algorithm is the GCD.
Frequently Asked Questions
1. Why does the carry never exceed 1 when adding two numbers?
The largest column total is 9 + 9 + 1 = 19, so the carry is only 0 or 1.
2. Why does Euclid’s algorithm work?
The common divisors of m and n are exactly the common divisors of n and the remainder m mod n.
3. What is an algorithm?
An ordered, finite set of unambiguous instructions for solving a problem.