UPSKILL MATH PLUS

Learn Mathematics through our AI based learning portal with the support of our Academic Experts!

Learn more### 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.