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
Quick, is there an easy way to determine whether a number is divisible by 7?
PerfectHacker, thank you! That made a lot of sense even at a glance, so it will probably put me at ease this weekend when I look over it in detail. I'm beginning to think this was a really strange problem to appear in my math book. There really are no explanations given for handling its peculiarities.
Take the last digit and multiply it by 2. So in this case, when you got 2037, the last digit is 7, and multiplied with 2 it's 14. Then you subtract that from "the rest" of the number, which is 203. 203 - 14 = 189. If the new number is divisible by 7, then the original number is as well.
0 is divisible by 7, and so is 2037.[/QUOTE]
Here's the derivation:
Consider the number as a sum of the last digit and the rest of the number, .
We wanna check if
(I at least think is a requirement for using the included sign)