### Theory:

Procedure to play Euclid's game:
Step 1: Two players should take any two natural numbers $$(a, b)$$.

Step 2: First player subtracts the smaller number $$(b)$$ from larger number $$(a)$$, you will get the difference $$(c)$$. In the next line, write the smaller number $$(b)$$ with the difference $$(c)$$ as $$(b, c)$$.

Step 3: Now, the second player find a difference between $$(b)$$ and $$(c)$$, name it as $$(d)$$. In the next line, write $$(c)$$ and $$(d)$$ as $$(c, d)$$.

Step 4: Now, the first player find a difference between $$(c)$$ and $$(d)$$, name it as $$(e)$$. In the next line, write $$(d)$$ and $$(e)$$ as $$(d, e)$$.

Step 5: This process goes on until they get the difference, and the numbers have become equal.
Rahu and Guru are playing a game.

Rahu choose $$48$$ and Guru choose $$56$$.

 Name $$a > b$$ Difference $$(a, b)$$ (Greatest, Smallest) $$(48, 56)$$ $$(56, 48)$$ Rahu $$56 > 48$$ $$56 - 48$$ $$(8, 48)$$ $$(48, 8)$$ Guru $$48 > 8$$ $$48 - 8$$ $$(40, 8)$$ $$(40, 8)$$ Rahu $$40 > 8$$ $$40 - 8$$ $$(32, 8)$$ $$(32, 8)$$ Guru $$32 > 8$$ $$32 - 8$$ $$(24, 8)$$ $$(24, 8)$$ Rahu $$24 > 8$$ $$24 - 8$$ $$(16, 8)$$ $$(16, 8)$$ Guru $$16 > 8$$ $$16 - 8$$ $$(8, 8)$$ Same numbers

Guru got the same numbers, and he wins the game.

By the above Euclid's game, we can find that $$8$$ is the highest common factor of $$(48, 56)$$.

So, the above iterative process leads to the HCF of two starting numbers.

The HCF of $$a$$ and $$b$$ (here $$a > b$$) is the same as for $$a$$ and $$a-b$$.
Example:
Find the HCF of two numbers $$12$$ and $$28$$.

Solution:

We can find HCF in two ways.

Method I:

Let's do in the usual way of finding common factors between the two numbers.

$$12 = 2 \times 2 \times 3$$

$$28 = 2 \times 2 \times 7$$

HCF of $$(12, 28) = 2 \times 2 = 4$$ - - - - - (I)

Method II:

Now, we find HCF by the conclusion of Euclid's game.

Here, $$28 > 12$$. So, $$a = 28$$ and $$b = 12$$.

To find the HCF of $$(a, a-b)$$ $$=$$ $$(28, 28 - 12)$$.

$$28 = 2 \times 2 \times 7$$

$$28 - 12 = 16 = 2 \times 2 \times 2 \times 2$$

HCF of $$(28, 28 - 12) = 2 \times 2 = 4$$ - - - - - (II)

From (I) and (II), we observe that:

HCF of $$(12, 28) =$$ HCF of $$(28, 28 - 12) = 4$$.
Euclidean algorithm:
Let $$a$$ and $$b$$ can be any number but $$a > b$$.

Now, we randomly take $$a = 27$$ and $$b = 4$$.

Let us divide a number $$a$$ by $$b$$.

$\begin{array}{l}\phantom{\rule{1.176em}{0ex}}6\\ 4\overline{)27}\\ \phantom{\rule{0.147em}{0ex}}-24\\ \overline{\underset{¯}{\phantom{\rule{1.176em}{0ex}}3\phantom{\rule{0.735em}{0ex}}}}\end{array}$

Quotient $$(q)$$ $$=$$ $$6$$ and Remainder $$(r)$$ $$=$$ $$3$$

So, $$27$$ can be written as $$27 = (4 \times 6) + 3$$.

Therefore, $$a = (b \times q) + r$$.

From the above example, we observe that, if a number '$$a$$' is divided by another number '$$b$$', we get quotient '$$q$$' and remainder '$$r$$'.

$$a = (b \times q) + r$$ or $$a = bq + r$$

That is, $$\text{Dividend}$$ $$=$$ $$(\text{Divisor} \times \text{Quotient}) + \text{Remainder}$$.

This is called Euclidean algorithm.

Important!
The HCF of $$a$$ and $$b$$ (here $$a > b$$) is the same as for $$a$$ and $$a-b$$.

$$a = (b \times q) + r$$ or $$a = bq + r$$