Why does Euclid's HCF algorithm work?

Question

I saw this Khan Academy video on the visualization of Euclid's algorithm. The problem was to find the HCF of $32$ and $12$.

---

At $6:53$, the instructor reduced the original problem to $12$ and $8$ as: $$ \left\{ \begin{array}{c} 32 = 12 + 12 + 8 \\ 12 \end{array} \right. $$

Why did he leave the numbers $9, 10$, and $11$ and directly jumped to $8$? How can I be sure that the numbers won't be a factor of $32$ and $12$?

Answer 1

His argument is that if a whole number of bricks fits inside of $12$, then a whole number of bricks also fits inside of $12+12$. Is it clear to you why this is true?

Now if a whole number of the same kind of brick fits inside $32$, then we can remove the whole number of bricks that fit inside $12+12$ from the bricks that fit inside $32$, and the number of bricks that fit inside of the remainder, $8$, will also be a whole number.

So whatever the size of the brick is, if a whole number of that brick fits inside both $12$ and $32$, then a whole number of that brick will fit inside $8$.

If you follow this argument, there is no need to rule out $11$, $10$, and $9$. You ask how you can be sure none of these numbers will be a factor of both $32$ and $12$, but that is the wrong question. After all, $8$ is not a factor of both $32$ and $12$ either. So being a factor of both $32$ and $12$ is not the reason for considering $8$. To repeat, the reason for considering $8$ is that any brick that fits inside of both $12$ and $32$ also fits inside of $8$.

Answer 2

If you do some divisibility checks, you can see that because $3+2 = 5$ and $5 \nmid 9$. Additionally, neither of the numbers end in zero, or consist of the same digit (note this check only works for testing divisibility by eleven for numbers less than 99). I assume that's what's happened here.

Answer 3

He tried to express $32$ as a sum of $12$'s. This is why he "skipped" $9,10,11$. In addition to that note than none of $9,10,11$ divide 32. Hence, he reduced the problem to finding th HCF of 8 and 12, because it would work for 12 and 32 as well, since 12 is a divisor of 32. So In fact, he didnt "jump" to 8, he just divided 32 with 12, and 8 was the remainder.

Indeed he writes $32 = 12 + 12 + 8$.

He says "if you found a break that can cover 12 and the you found another break for 8 with the condition it covers 12 too (5:45)". And that is of course, 4.