From ROSEN, section 4.2, problem 36
The well-ordering property can be used to show that there is a unique greatest common divisor of two positive integers. Let a and b be positive inteters, and let S be the set of postive integers of the form as + bt, where s and t are intergers.
a) Show that S is nonempty.
Since a, b, s, and t are integers and the set of integers is closed under addition and multiplication, as + bt must be an integer.
My question is this: Is it implied that s and t are POSITIVE integers. If s and t were both negative integers, then S could be empty. Could someone explain what I'm missing?
b) Use the well ordering property to show that S has a smallest element c.
Since S was proved to be non-empty in a), then by the well ordering property, S must contain a smallest element since S is a set of positive integers. Call that element c.
c) Show that if d is a common divisor of a and b, then d is a divisor of c.
Since c is an element of S and all elements of S have the form as + bt, then by the theorem (that if d divides a and d divides b then d divides a + b) we show that d divides c.
d) Show that c divides a and c divides b.
Assume that c does not divide a, then a = qc + r where 0 < r < c.
I am stuck proving that r is an element of S, and I don't see how this contradicts the choice of c. I see that r is a positive integer, but how is it of the form as + bt?