UPSKILL MATH PLUS
Learn Mathematics through our AI based learning portal with the support of our Academic Experts!
Learn moreThe term "algorithm" comes from the Persian mathematician Al-Khwarizmi, who lived in the \(9^{\text{th}}\) century. An algorithm is a step-by-step plan that uses the results of previous steps to calculate the next step until the desired result is reached.
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.
An 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 the 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 the new divisor \(20\) and the new remainder \(8\).
\(20 = 8 \times 2 + 4\)
Since the remainder \(4 \ne 0\), apply the division lemma to the 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)\).
The 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 the smaller from the larger.
Step 4: When the numbers are equal, stop the process.
Step 2: Subtract the smaller from the larger from the remaining numbers.
Step 3: Repeat the subtraction process by subtracting the 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 the Theorem \(3\) in earlier classes as Euclid's game.
Register for free to see more content