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 10 math (India)

### Unit 1: Lesson 1

Euclid's division algorithm

# Euclid's division algorithm visualised

In an earlier video, we learnt how to use the Euclid's division algorithm to find the HCF of two numbers. Now let us learn how to visualise Euclid's division algorithm and get an intuition for what we are doing. Created by Aanand Srinivas.

## Want to join the conversation?

• does learning CBSE syllabus help a student of ICSE
• what is the extended euclid's algorithm?
• The extended Euclidean algorithm is an algorithm to compute integers xx and yy such that

ax+by=gcd(a,b)

given a and b

The extended Euclidean algorithm can be viewed as the reciprocal of modular exponentiation.

By reversing the steps in the Euclidean algorithm, it is possible to find these integers x and y. The whole idea is to start with the GCD and recursively work our way backwards. This can be done by treating the numbers as variables until we end up with an expression that is a linear combination of our initial numbers.

https://brilliant.org/wiki/extended-euclidean-algorithm/
• What should I study for GCSE or IGCSE?