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