If two numbers are divisible by x, then so is their sum and diffference. Call the first number x×y and the second x×z, and invoke the distributive property. The sum is x×(y+z) and the difference is x×(y-z). Both are obviously divisible by x. This simple fact can be used again and again to quickly home in on x. Let's look at a simple example.
What number x divides both 100 and 36? It must also divide 100-36. In fact it divides 100-36-36, which is the remainder of 100÷36. This remainder, 28, is necessarily smaller than 36 - we've made progress. But what divides evenly into 36 and 28? Subtract again to get 8. Then divide 28 by 8, giving a remainder of 4. Finally 8 and 4 produce a remainder of 0, terminating the algorithm. Now 4 divides both 100 and 36, and if any other number, such as 2, also divides 100 and 36, it must divide evenly into 4. After all, 2 is subject to the same procedure, dividing evenly into all the differences and remainders, all the way down to 4.
The above procedure, called Euclid's gcd algorithm, extracts the greatest common divisor x, because any other common divisor y divides evenly into each difference and remainder along the way, until finally, y divides x. The result, x, is truly a "greatest common divisor", since it contains every other common divisor y.
If x is 1, the two numbers are "relatively prime", or "coprime". They have no factors in common.
The word incommensurable originally meant "no common divisors", and it can still be used this way, though it is more often used to describe items or ideas that cannot be reasonably compared, as in incommensurable theories.
If g is the gcd of s and t, what is the gcd of cs and ct? Certainly cg (c×g) divides both cs and ct. If the greatest common divisor is actually larger, let cgk divide cs and ct, where k takes up the slack. Divide through by c, and gk divides both s and t. This is a contradiction, since g is already the gcd of s and t. Thus cg is the gcd of cs and ct. This can be summarized by saying, multiplication distributes over gcd. Multiply two numbers by c, and that multiplies their gcd by c.
Note that the gcd algorithm is efficient, even for large numbers. The remainder (rounding up or down) is at most half the divisor, so it doesn't take long to reach the gcd. Each step introduces another bit of precision. In fact, the algorithm is at least 28% faster than this simple calculation would suggest, but you need the theory of continued fractions to prove this. In any case, the algorithm is efficient. We may not be able to factor two huge numbers, but we can quickly tell if they have any factors in common.
Most modern factoring methods employ the gcd algorithm inside, a real tribute to Euclid. If n = p×q, a factoring program such as the elliptic curve method generates values of k in clever ways, hoping to stumble upon something divisible by p or q. But we don't know what p and q are ahead of time, so how do we measure success? Answer: run the gcd algorithm on k and n. If k is divisible by p, gcd(k,n) will produce p in short order. Of course, you can spend your entire career looking for clever ways to generate k, so that it is more likely to have a factor in common with n. Obviously, choosing k at random won't get you very far.