Chapter 5: Q22E (page 330)
For which nonnegative integer’s n is Prove your answer.
P(n) is true for all integers n>3.
Over 22 million students worldwide already upgrade their learning with Vaia!
All the tools & learning materials you need for study success - in one app.
Get started for free
Prove that whenever n is a nonnegative integer.
The well-ordering property can be used to show that there is a unique greatest common divisor of two positive integers. Let a and be positive integers, and let S be the set of positive integers of the form , 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) Show that if d is a common divisor of a and b, then d is a divisor of c.
d) Show that c I a and c I b. [Hint: First, assume that . Then , where . Show that , 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.
Give a recursive algorithm for finding the maximum of a finite set of integers, making use of the fact that the maximum of n integers is the larger of the last integer in the list and the maximum of the first n - 1 integers in the list.
Prove that if n is an integer greater than 6.
Suppose that a store offers gift certificates in denominations 25 dollars and 40 dollars. Determine the possible total amounts you can form using these gift certificates. Prove your answer using strong induction.
What do you think about this solution?
We value your feedback to improve our textbook solutions.
