Main content

## Class 10 math (India)

# 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(2 votes)
- what is the extended euclid's algorithm?(2 votes)
- 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.

For more info, check-

https://brilliant.org/wiki/extended-euclidean-algorithm/(3 votes)

- What should I study for GCSE or IGCSE?(0 votes)
- I still don't fully understand why this phenomenon takes place. But what i get is that its basically the process of division or simplification done in a different way right?(0 votes)
- wouldn't 6 be possible?

6*7 = 32

6*2 = 12

making 7 bricks for 32 and 2 bricks for 12.(0 votes)- If 6*7 were equal to 32, then yes, 6 would be the GCF. However, 6*7 = 42, 6*6 = 36, and 6*5 = 30. 32 cannot be divided evenly by 6 without a remainder. I think you made a mistake in your arithmetic and put 6*7 as 32 instead of 42.(3 votes)