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

Example: Euclid's division algorithm

In an earlier video, we learnt what the Euclid's division algorithm is. Here, let's apply Euclid's division algorithm to find the HCF (Highest common factor) of 1318 and 125. Created by Aanand Srinivas.

Want to join the conversation?

  • leaf green style avatar for user 😎  Tommy 😎
    At why you have written 0? I am always confused when to write 0 and why since class 4th! Please clear my issue.
    (5 votes)
    Default Khan Academy avatar avatar for user
    • mr pink red style avatar for user aanand
      Great question. The idea is that once you do the first step and get a remainder of 68, it is easy to forget that you need to ask how many times 125 goes in 68 and the answer to that will be zero times. This zero is part of the quotient. This shouldn't trouble you too much because you can always just look at the quotient and see if it makes intuitive sense and add a zero if you notice that you have forgotten like I did in the video.
      (8 votes)

Video transcript