Let me show you my way.
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 $\displaystyle \gcd$
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 $\displaystyle \gcd(9506,12222)=?$
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,
$\displaystyle 25=\underbrace{4}_{\mbox{ Quotient }}\times 6+\underbrace{1}_{\mbox{ Remainder }}$
This is called "Division algorithm".
Here is another example, express 333 and 110 in division algorithm form?
$\displaystyle 333=3\times 110+3$
---
Now we can talk about Euclidean Algorithm
---
We start of by expressing 12222 and 9506 in division algorithm form.
$\displaystyle 12222=1\times 9506+2716$
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,
$\displaystyle 9506=3\times 2716+1358$
Again we find the division algorithm form between number to the right of quotient and remainder,
$\displaystyle 2716=2\times 1358+0$
When we reach 0 as remainder this tells us that the number to the right of quotient is the greatest common divisor. So
$\displaystyle \gcd (12222, 9506)=1358$
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.
Yes, there is. I'm not Quick, but I hope I can answer anyway!
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.
$\displaystyle 2037$
$\displaystyle 203 - 2\cdot 7 = 189$
$\displaystyle 18 - 2\cdot 9 = 0$
0 is divisible by 7, and so is 2037.[/QUOTE]
Here's the derivation:
Consider the number $\displaystyle n$ as a sum of the last digit and the rest of the number, $\displaystyle n = 10\cdot x + y$.
We wanna check if $\displaystyle n\ \equiv\ 0\ (\text{mod 7})$
$\displaystyle 10\cdot x + y\ \equiv\ 0\ (\text{mod 7}) \longleftrightarrow$
$\displaystyle -10\cdot x - y\ \equiv\ 0\ (\text{mod 7}) \longleftrightarrow /gcd(2, 7) = 1/ \longleftrightarrow$ (I at least think $\displaystyle gcd(2, 7) = 1$ is a requirement for using the included $\displaystyle \longleftarrow$ sign)
$\displaystyle 2\cdot(-10\cdot x - y)\ \equiv\ 0\ (\text{mod 7}) \longleftrightarrow$
$\displaystyle -20\cdot x - 2\cdot y\ \equiv\ 0\ (\text{mod 7}) \longleftrightarrow /-20\ \equiv\ 1\ (\text{mod 7})/ \longleftrightarrow$
$\displaystyle x - 2\cdot y\ \equiv\ 0\ (\text{mod 7})$