NCERT Ganita Manjari Part II • Computational Mathematics & GCD Algorithms
1. The Foundation of Algorithmic Thinking
The word algorithm originates from the 9th-century Persian mathematician Muḥammad ibn Mūsā al-Khwārizmī, whose foundational texts introduced Hindu-Arabic positional numerals and systematic methods of algebraic computation to the world.
Core Definition
Algorithm: A well-defined, ordered, finite sequence of unambiguous instructions designed to solve a specific problem or compute an output from given inputs.
Five Fundamental Characteristics of an Algorithm
1. Finiteness: The procedure must always terminate after a countable number of execution steps. It cannot run into an infinite loop.
2. Definiteness (Unambiguity): Each step must be clearly and unambiguously specified without guesswork.
3. Inputs: Quantities supplied externally before the algorithm begins ($0$ or more inputs).
4. Outputs: Definite resulting quantities produced that have a specified relationship to the inputs.
5. Effectiveness: All operations must be sufficiently basic so that they can be performed exactly in a finite amount of time (by hand or machine).
2. Place-Value System and Arithmetic Algorithms
When we add two multi-digit numbers such as $387 + 258$, we perform a standard arithmetic algorithm based on the decimal positional system ($N = \sum d_k 10^k$):
Step-by-Step Anatomy of Column Addition
Align: Write digits aligned by place values (Units, Tens, Hundreds).
Compute Units: $7 + 8 = 15$.
Write $5$ in the units place; carry over $1$ to the tens column ($15 = 1 \times 10^1 + 5 \times 10^0$).
Compute Tens: $1\text{ (carry)} + 8 + 5 = 14$.
Write $4$ in the tens place; carry over $1$ to the hundreds column.
Compute Hundreds: $1\text{ (carry)} + 3 + 2 = 6$.
Write $6$ in the hundreds column. Final Result: $645$.
Why this is an algorithm: It decomposes any large arithmetic problem into identical, finite sub-operations on single-digit pairs.
3. Divisors and the Greatest Common Divisor (GCD)
Mathematical Concept
Divisor (Factor): An integer $d$ is a divisor of $n$ if $n = d \times q$ for some integer $q$ (meaning the remainder is zero, $n \bmod d = 0$).
Greatest Common Divisor (GCD / HCF): The largest positive integer that divides both $a$ and $b$ without a remainder, written as $\gcd(a, b)$.
The traditional method of listing all factors or using prime factorisation becomes extremely slow as numbers grow to hundreds or thousands of digits. We need systematic, algorithmic methods!
4. Euclid's Subtraction Algorithm
Over 2300 years ago, Euclid discovered a profound mathematical truth:
$$\text{Euclid's Subtraction Principle: } \text{If } a > b \text{, then } \gcd(a, b) = \gcd(a - b, b)$$
WHY DOES IT WORK? (DEDUCTIVE PROOF)
Let $d$ be any common divisor of $a$ and $b$. Then $a = d \cdot m$ and $b = d \cdot n$.
Subtracting them gives: $a - b = d \cdot m - d \cdot n = d(m - n)$.
Therefore, $d$ also divides $(a - b)$! Thus, the common divisors of $(a, b)$ are exactly identical to the common divisors of $(a - b, b)$. Hence, their greatest common divisor must be identical.
Geometric Meaning: Tiling a Rectangle with Squares
Imagine a rectangle of length $a$ and width $b$. Finding $\gcd(a, b)$ corresponds geometrically to finding the largest square tile that can tile the entire rectangle perfectly without cutting!
Figure 11.1: Geometric visualization of Euclid's algorithm through square tiling.
5. Aryabhata's Division Algorithm & Modern Euclidean Division
While repeated subtraction is simple, subtracting a small number from a very large number takes thousands of steps (e.g., $\gcd(1000000, 3)$ would require over 333,000 subtractions!).
In the 5th century CE, the great Indian astronomer-mathematician Aryabhata I introduced the famous Kuttaka (The Pulverizer) method, which replaces repeated subtractions with Division with Remainder.
$$\text{Division Algorithm Invariant: } a = bq + r \quad (0 \le r < b) \implies \gcd(a, b) = \gcd(b, r)$$
The process repeats until the remainder becomes $0$. The last non-zero remainder is the GCD!
Feature
Euclid's Subtraction Algorithm
Aryabhata's Division Algorithm
Core Operation
Repeated subtraction ($a - b$)
Division with remainder ($a \bmod b$)
Number of Steps
Can be very large when $a \gg b$
Logarithmic (extremely fast, usually $< 10$ steps)
Halting Condition
When both numbers become equal ($a = b$)
When remainder $r = 0$
6. Algorithmic Flowcharts
A flowchart represents an algorithm visually using standardized geometric shapes:
Oval: Start or Stop terminal.
Parallelogram: Input or Output.
Rectangle: Computational process step (e.g., $r = a \bmod b$).
Since the remainder has reached $0$, the last non-zero remainder is $31$. Answer: $\gcd(1147, 899) = 31$, computed in exactly $6$ division steps.
Example 3: Practical Courtyard Tiling Problem NCERT
Problem: A rectangular courtyard is $18\text{ m } 72\text{ cm}$ long and $13\text{ m } 20\text{ cm}$ broad. It is to be paved with square tiles of the maximum possible size. Find:
The side length of the largest square tile that can be used.
VARDAAN COMET