Why does Euclid's HCF algorithm work? 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$?
He tried to express $32$ as a sum of $12$'s. This is why he &quot;skipped&quot; $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 &quot;jump&quot; to 8, he just divided 32 with 12, and 8 was the remainder.
Indeed he writes $32 = 12 + 12 + 8$.
He says &quot;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)&quot;. And that is of course, 4.
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.