How do you work out the highest common factor of two numbers?

Answer 1

Figure out the prime factorization of both numbers and find the largest subset of each factorization which is in the other.

e.g. 112 and 36:
112 = 2*2*2*2*7
36 = 2*2*3*3

36 has two 2's, 112 has two 2's also (plus more, but we can't use them since 36 only has two of them). We can't use any 7's since 36 doesn't have any. Similarly we cannot use any 3's.
The best we can do is use 2*2 = 4.

Another example:
1260 = 2*2*3*3*5*7
1650 = 2*3*5*5*11
Largest subset = 2*3*5 = 30

Last one:
2003 = 1*2003 (prime. Normally, we don't write the 1 since it isn't a Prime number)
1999 = 1*1999 (prime)
Largest subset = 1 (the numbers are co-prime, i.e. the highest common factor is 1)