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.

Main content

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?

  • duskpin sapling style avatar for user bkgupta99
    does learning CBSE syllabus help a student of ICSE
    (2 votes)
    Default Khan Academy avatar avatar for user
  • blobby green style avatar for user nagu89
    what is the extended euclid's algorithm?
    (2 votes)
    Default Khan Academy avatar avatar for user
    • piceratops tree style avatar for user Tisha Jain
      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)
  • male robot hal style avatar for user Sai Ritwik
    What should I study for GCSE or IGCSE?
    (0 votes)
    Default Khan Academy avatar avatar for user
  • starky ultimate style avatar for user Navya Sinha
    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)
    Default Khan Academy avatar avatar for user
  • leaf yellow style avatar for user Manish Pun
    wouldn't 6 be possible?
    6*7 = 32
    6*2 = 12

    making 7 bricks for 32 and 2 bricks for 12.
    (0 votes)
    Default Khan Academy avatar avatar for user

Video transcript