Chapter 5.2, Problem 36E

well-orderingproperty can be used to show that there is a unique greatest common divisor of two positive integers. Letaandbbe positive integers, and letSbe the set of positive integers of the formas+bt,wheresandtare integers.

1. Show that Sis nonempty.

Use the well-ordering property to show that 5 has a smallest element c.c)Show that ifdis a common divisor ofaandb, thendis a divisor ofc.

1. Show thatc|aand c |b. [Hint:First, assume that c E a. Thena=qc+r, where o< r< c. Show that r £ 5, contradicting the choice of c.]
2. Condude from (c) and (d) that the greatest common divisor of a and it exists. Finish theproof by showing that this greatest common divisor is unique.