If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

## Class 9 (Assamese)

### Course: Class 9 (Assamese)>Unit 5

Lesson 1: Euclid's definitions, axioms and postulates

# Intro to Euclid's division algorithm

Let's get introduced to Euclid's division algorithm to find the HCF (Highest common factor) of two numbers. Let's learn how to apply it over here and learn why it works in a separate video. Created by Aanand Srinivas.

## Want to join the conversation?

• what is Euclid's Division Lemma?
• A lemma is a proven statement used for proving another statement.
So, according to Euclid's Division Lemma, if we have two positive integers a and b, then there would be whole numbers q and r that satisfy the equation: a = bq + r, where 0 ≤ r < b. a is the dividend. b is the divisor. q is the quotient and r is the remainder. By using this lemma, we can find the HCF of two numbers.
• dose this also work with rational no.
• Yes it does, numbers like 4, 8, 10 etc. are all rational numbers.

sorry for taking too long .
• Is Euclid's Division Lemma and Euclid's Division Algorithm the same ?
• No, though they are closely interlinked.The algorithm uses the lemma to solve a problem.
• What is the difference between Euclid's division lemma and Euclid's division algorithm?
• Euclid's division lemma and Euclid's division algorithm are related concepts in number theory.

Euclid's division lemma states that given two positive integers a and b, there exist unique integers q and r such that a = bq + r, where 0 ≤ r < b. This means that any positive integer a can be divided by another positive integer b, with a unique quotient q and remainder r.

Euclid's division algorithm is a step-by-step process that uses the division lemma to find the greatest common divisor (GCD) of two positive integers a and b. The algorithm states that to find the GCD of a and b, we repeatedly divide the larger number by the smaller number and replace the larger number with the remainder until the remainder is 0. The last non-zero remainder is the GCD.

So the main difference between Euclid's division lemma and Euclid's division algorithm is that the former is a statement that any positive integer a can be divided by another positive integer b, with a unique quotient q and remainder r, while the latter is a specific algorithm that uses the division lemma to find the GCD of two positive integers a and b.
(1 vote)
• In Euclid's lemma if a<b as in 5=12x0+5 then how the lemma is satisfied where 0<=r<b.
(1 vote)
• Hello nisha,
There is one thing we should always keep in mind while doing the euclid's division algorithm is that you should always take the greater number and then divide it by the smaller number. Then you will not yet any constraints.
• I tried solving the second HCF sum. According to the rule shouldn't the HCF be 14 since it is the "highest common factor"?
(1 vote)
• How to find HCF of more than two numbers by Euclid's division algorithm?
(1 vote)
• Find the HCF of any two numbers, say a and b, by applying Euclid's division lemma. This means finding whole numbers q and r such that a = bq + r, where 0 ≤ r < b. If r = 0, then b is the HCF. Otherwise, repeat the process with b and r until r = 0.
Take the HCF of a and b, and find the HCF of it with the third number, say c, using the same method. This will give the HCF of a, b, and c.
Repeat the process with the HCF of a, b, and c, and the next number, until you have covered all the numbers. The final HCF will be the HCF of all the numbers.
(1 vote)
• Explanation xy, or X + Y is written 10 x + Y, what type of write-in, and when does it write?