It is called the "Euclidean Algorithm" (That is you!) and it appears in the Bible of math, "The Elements".
To begin let me mention some terminology.
The largest common factor is also called the greatest common divisor.
It is abbreviated as
Say you want to find the greatest common factor of 9506 and 12222. A complicated thing to do, since you need to look at all the factors.
So we want to know what
In order to find that, you need to know what a remainder and a quotient is. The quotient is the integer part when you divide. The remainder is what remains.
For example, find quotient and remainder when 25 is divided by 6?
When we divide the integer part that remains is 4. And the remainder is 1.
Here is the most important step when you get the quotient and remainder you can write,
This is called "Division algorithm".
Here is another example, express 333 and 110 in division algorithm form?
Now we can talk about Euclidean Algorithm
We start of by expressing 12222 and 9506 in division algorithm form.
According to Euclid this problem of find the greatest common divisor is the same as finding the greatest common divisor between the number to the right of quotient and remainder.
But to do that
We need to express 9506 and 2716 in division algorithm form,
Again we find the division algorithm form between number to the right of quotient and remainder,
When we reach 0 as remainder this tells us that the number to the right of quotient is the greatest common divisor. So