Most people know that if you have the prime factorizations of two numbers, you can find their GCD. For example, to find gcd(20,12), they will factorize 20 and 12:
20 = 2 * 2 * 5
12 = 2 * 2 * 3
Then they collect the common portions and get the answer: 2*2 is common to both factorizations, so gcd(20,12) = 2*2 = 4.
As another example,
12 = 2 * 2 * 3
90 = 2 * 3 * 3 * 5
The common portion is 2*3, so gcd(12,90) = 2*3 = 6.
This always works, as stated by the following theorem.
Theorem: Suppose p1 through pk are all the distinct prime divisors of x and y, and they have cannonical prime factorizations
x = p1^e1 * ... * pk^ek
y = p1^f1 * ... * pk^fk
where the e's and the f's are natural numbers (including 0). Then gcd(x,y) = p1^min(e1,f1) * ... * pk^min(ek,fk).