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 integers, and let S be the set of positive integers of the form as+bt, where s and t are integers. a)Show that S is nonempty. b)Use the well-ordering property to show that S has a smallest element c. c)Show that if d is a common divisor of a and b, then d is a divisor of c. d)Show that c | a and c | b. [Hint: First, assume that c|a. Then a=qc+r, where 0
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 integers, and let S be the set of positive integers of the form as+bt, where s and t are integers.
a)Show that S is nonempty.
b)Use the well-ordering property to show that S has a smallest element c.
c)Show that if d is a common divisor of a and b, then d is a divisor of c.
d)Show that c | a and c | b. [Hint: First, assume that c|a. Then a=qc+r, where 0<r<c. Show that r∈S, contradicting the choice of c.]
e)Conclude from (c) and (d) that the greatest common divisor of a and b exists. Finish the proof by showing that this greatest common divisor is unique.
Trending now
This is a popular solution!
Step by step
Solved in 2 steps with 1 images
