Shortcut Method for Euclid’s Division Algorithm
We also have a shortcut method of finding the HCF of two numbers this method uses the concept of division to find the HCF. We know that,
Dividend = Divisor × Quotient + Remainder
Now we divide the given numbers (say and b) accordingly the bigger number with the smaller number and we obtained a quotient and a remainder. Now this remainder becomes the divisor and the previous divisor becomes the dividend and further, the division process is carried out.
This process is repeated till the remainder of the division is zero. And the quotient when the remainder becomes zero is the HCF of the two numbers a and b.
The following illustration shows the calculation of HCF of 132 and 320 using the shortcut method.
- Thus, the HCF of 132 and 320 is 4.
Euclid’s Division Lemma
Euclid’s Division Lemma is one of the fundamental theorems proposed by the ancient Greek mathematician Euclid. This theorem explains that for any two integers a and b, we have other two positive integers q and r such that, a = bq + r.
With the help of Euclid’s Division Lemma an algorithm is defined i.e., Euclid’s Division Algorithm which is used to find the HCF of any two numbers. In this algorithm, apply Euclid’s Division Lemma multiple times to get the Highest Common Factor (HCF) of two numbers.
To understand Euclid’s Division Algorithm we first need to understand Euclid’s Division Lemma. Lemma is like a theorem and we will learn about Euclid’s Division Lemma, Euclid’s Division Algorithm, and others in detail in this article.
Euclid’s Division Lemma
Table of Content
- What is Euclid’s Division Lemma?
- Euclid’s Division Lemma Definition
- Statement of Euclid’s Division Lemma
- Example of Euclid’s Division Lemma
- Proof of Euclid’s Division Lemma
- What is Euclid’s Division Algorithm?
- Generalizing Euclid’s Division Algorithm
- Shortcut Method for Euclid’s Division Algorithm
- Solved Examples on Euclid’s Division Lemma