Theory:

The term "algorithm" comes from the Persian mathematician Al-khwarizmi, who lived in the \(9^{\text{th}}\) century. An algorithm is a methodical step-by-step process that involves calculating successively on the results of previous steps until the desired result is obtained.
 
Euclid's division algorithm is based on the Euclid's division lemma.
Theorem 2
If \(a\) and \(b\) are positive integers such that \(a = bq + r\), then every common divisor of \(a\) and \(b\) is a common divisor of \(b\) and \(r\) and vice-versa.
 
Algorithm to find the HCF of two numbers:
Consider two positive numbers, \(a\) and \(b\), \(a > b\).
 
Step 1: Apply Euclid’s division lemma to \(a\) and \(b\). So, we find whole numbers, \(q\) and \(r\) such that, \(a = bq + r\), \(0 ≤ r < b\).
 
Step 2: If \(r = 0\), \(b\) is the HCF of \(a\) and \(b\). If \(r ≠ 0\), apply the division lemma to \(b\) and \(r\) to obtain another set of quotient and remainder.
 
Step 3: Repeat the procedure until the remainder is zero. The divisor at this stage will be the required HCF of given numbers.
Example:
1. Use Euclid’s algorithm to find the HCF of \(1524\) and \(236\).
 
Solution:
 
Step 1: Since \(1524 > 236\), apply Euclid's division lemma to \(1524\) and \(236\).
 
\(1524 = 236 \times 6 + 108\)
 
Step 2: Since the remainder \(108 \ne 0\), apply the division lemma to \(236\) and the remainder \(108\).
 
\(236 = 108 \times 2 + 20\)
 
Step 3: Since the remainder \(20 \ne 0\), apply the division lemma to the new divisor \(108\) and the new remainder \(20\).
 
\(108 = 20 \times 5 + 8\)
 
Since the remainder \(8 \ne 0\), apply the division lemma to new divisor \(20\) and the new remainder \(8\).
 
\(20 = 8 \times 2 + 4\)
 
Since the remainder \(4 \ne 0\), apply the division lemma to new divisor \(8\) and the new remainder \(4\).
 
\(8 = 4 \times 2 + 0\)
 
Now, the remainder has become zero, so stop the procedure.
 
The divisor at this stage is \(4\).
 
Therefore, the HCF of \((1524, 236)\) is \(4\).
 
Also, note that:
 
HCF \((8, 4)\) \(=\) HCF \((20, 8)\) \(=\) HCF \((108, 20)\) \(=\) HCF \((236, 108)\) \(=\) HCF \((1524, 236) = 4\).
 
 
2. If \(d\) is the Highest Common Factor of \(16\) and \(30\), find \(x\) and \(y\) satisfying \(d = 16x + 30y\).
 
Solution:
 
Since \(30 > 16\), apply the Euclid's division lemma.
 
\(30 = 16 \times 1 + 14\) - - - - - (I)
 
Since \(14 \ne 0\), apply the division lemma to \(16\) and the remainder \(14\).
 
\(16 = 14 \times 1 + 2\) - - - - - (II)
 
Since \(2 \ne 0\), apply the division lemma to \(14\) and the new remainder \(2\).
 
\(14 = 2 \times 7 + 0\)
 
The remainder is \(0\), so stop the procedure.
 
Thus, the HCF of \(16\) and \(30\) is \(6\).
 
Given that \(d = 16x + 30y\).
 
From equation (II):
 
\(16 = 14 \times 1 + 2\)
 
\(2 = 16 - 14 \times 1\)
 
\(2 = 16 - (30 - 16 \times 1) \times 1\) [Using equation (I)]
 
\(2 = 16 - 30 + 16\)
 
\(2 = 16 \times 2 - 30\)
 
\(2 = 16 \times 2 - 30 \times 1\)
 
\(2 = 16 \times 2 + 30 \times (-1)\)
 
Therefore, the value of \(x = 2\) and \(y = -1\).
Important!
Although Euclid’s Division Algorithm is stated for only positive integers, it can be extended for all integers except zero, that is, \(b \ne 0\).
Theorem 3
If \(a\) and \(b\) are two positive integers with \(a > b\), then G.C.D of \((a, b) =\) G.C.D of \((a - b, b)\).
 
Procedure to determine the HCF through the difference between the numbers.
 
Step 1: Subtract the smaller number from the larger number.
 
Step 2: Subtract the smaller from the larger from the remaining numbers.
 
Step 3: Repeat the subtraction process by subtracting smaller from the larger.
 
Step 4: When the numbers are equal, stop the process.
 
Step 5: The HCF of the given numbers will be the number representing equal numbers obtained in step (iv).
Important!
We already learned Theorem \(3\) in earlier classes as Euclid's game.