UPSKILL MATH PLUS
Learn Mathematics through our AI based learning portal with the support of our Academic Experts!
Learn moreProcedure 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\).
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\)
Register for free to see more content