Profile
Settings
Refer your friends
Sign out
Euclidean Algorithm is a specific algorithm that comes under the umbrella of Euclid’s Division Lemma. Now, what is a lemma? A Lemma is a statement that has been proven to prove other subsequent statements. As per Euclid’s Division Lemma, if there are two positive numbers let’s say p and q, then there will be another pair of two integers let’s say a and b, p = qa + b, 0 < b < q. Euclid’s Division Algorithm is applied in problems where the highest common factor (HCF) is unknown, and only two positive numbers are provided. After reading this guide on Euclid’s Division Algorithm, you’ll be left with no questions on Euclidean algorithm, what is an extended Euclidean algorithm?
What is Euclid’s Division Algorithm?
Euclid’s Division Algorithm is a significant algorithm in the number system that is applied to obtain the highest common factor (HCF) between two non-negative numbers.
Before getting straight to all the theorems, proofs, and problems based on Euclid’s Division Algorithm, we should recall what is the highest common factor?
An HCF is also a number that is derived by some operations operated on two positive numbers, the condition for any number (let’s say k ) to become the HCF of two other numbers ( let’s say p, and q) is that k should be the highest number that can divide both p and q rationally which means the remainder must be zero.
Euclidean Algorithm is the process of repetitive usage of Euclid’s Division Lemma several times to obtain the greatest common divisor (another name for highest common factor).
Euclid’s Divison Algorithm Proof
Euclid’s Division Theorem:- If p and q are positive integers such that p = qa + b, where 0 < b < q. then there exist two more integers a and b which are common divisors of p and q, and vice-versa.
In simple terms, Euclid’s Division Lemma is the method we can use to check the accuracy probability of division, we know it that [Dividend = Quotient × Divisor + Remainder]. When we divide p = 38 by q = 5, the quotient will be a = 7, whereas the remainder will be b = 3. Here is an example:
Proof: Let s be the common divider of p and q.
Now, we will prove the converse of the euclidean algorithm.
We can do that by showing that d is a common divisor of p and q.
We know,
Example 1. Find the HCF of 55 and 210 using the Euclidean algorithm.
Step1. First, we should check which is greater out of the two numbers given to us.
55 is smaller than 210.
Step2. Second, writing both the numbers in the format of Euclid’s Division Lemma format.
[Dividend = Quotient × Divisor + Remainder]
210 = 55 * 3 + 45
Step3: Checking whether the remainder is equal to zero or not.
45 is not equal to 0.
Step4: We need to apply the Euclidean algorithm once again, this time the divisor is 55 and the remainder will be 45.
55 = 45 * 1 + 10
Step5: Again we have to check whether the remainder is equal to zero.
10 is not equal to 0.
Step6: We need to apply the Euclidean algorithm once again, this time the divisor is 10 and the remainder will be 5.
10 = 5 * 2 + 0
Step7: This is the final step now since the remainder is zero.
The HCF is going to be the final divisor 5.
The highest common factor or greatest common divisor of 55 and 210 is 5.
Extended Euclidean Algorithm
Extended Euclidean Algorithm is the advanced method accustomed to the basic Euclid’s Division Lemma. The extended Euclidean Algorithm is applied to calculate the greatest common divider between two numbers and is also used the represent the greatest common divisor in terms of p and q.
p*x + q * y = GCD of (p,q).
To understand the Extended Euclidean Algorithm, we can take the same example of 55 and 210.
We have already calculated the highest common factor of 55 and 210 is 5.
With the help of the Extended Euclidean Algorithm, we can represent 5 in the term of these two integers 55 and 210.
5 = 55 * 23 + 210 * (-6)
Hence, 23 and -6 are the two integers that are x and y.
Conclusion
Euclidean Algorithm is a specific algorithm that comes under the umbrella of Euclid’s Division Lemma. As per Euclid’s Division Lemma, if there are two positive numbers let’s say p and q, then there will be another pair of two integers let’s say a and b, p = qa + b, 0 < b < q. Euclid’s Division Algorithm is applied in problems where the highest common factor (HCF) is unknown, and only two positive numbers are provided. There are many shortcuts originating to decrease the solution of the problem by euclidean algorithm, one of them is the extended euclidean algorithm.
