The greatest common divisor of two numbers is a straightforward concept and the calculation of it is one that elementary school students are expected to be able to carry out. However, many of our intuitions about divisibility follow from a non-obvious result about greatest common divisors that we will present in this chapter’s first section. In this chapter we will also investigate a procedure for computing the greatest common divisor of two integers that does not require any kind of factorization of either number.