Given positive integers a and b, there is a positive integer d such that (i) d divides a and d divides b, and (ii) if c is a positive integer which divides both a and b then c divides d (that is, any common divisor of a and b must divide d). Proof Let D be the set of all positive integers of the form as + bt where s and t vary over the set of all integers: D = {as + bt : s and t are integers and as + bt > 0}. Since a(a = a 1 + b 0) is in D, we know that D is not empty and so, by the well-ordering principle, D has a least element d, say. Since d is in D there are integers s and t such that d = as + bt. We have to show that any common divisor c of a and b is a divisor of d. So suppose that c divides a, say a = cg, and that c divides b, say b = ch. Then c divides the right-hand side (cgs + cht) of the above equation and so c divides d. This checks condition (ii). We also have to check that d does divide both a and b, that is we have to check condition (i). We will show that d divides a since the proof that d divides b is similar (a and b are interchangable throughout the statement and proof so 'by symmetry' it is enough to check this for one of them). Applying Theorem 1.1.1 to 'divide d into a', we may write a = dq + r with 0 r < d. We must show that r = 0. We have r = a dq = a (as + bt)q = a(1 sq) + b(tq). Therefore, if r were positive it would be in D. But d was chosen to be minimal in D and r is strictly less than d. Hence r cannot be in D, and so r cannot be positive. Therefore r is zero, and hence d does, indeed, divide a