Exercises 2.4 Exercises
2.
3.
4.
5.
6.
7.
8.
9.
Hint.
Follow the proof in Example 2.1.4.
10.
11.
12. Power Sets.
Let be a set. Define the power set of denoted to be the set of all subsets of For example,
For every positive integer show that a set with exactly elements has a power set with exactly elements.
13.
Prove that the two principles of mathematical induction stated in Section 2.1 are equivalent.
14.
Show that the Principle of Well-Ordering for the natural numbers implies that 1 is the smallest natural number. Use this result to show that the Principle of Well-Ordering implies the Principle of Mathematical Induction; that is, show that if such that and whenever then
15.
-
14 and 39
-
234 and 165
-
1739 and 9923
-
471 and 562
-
23,771 and 19,945
-
and 3754
16.
Let and be nonzero integers. If there exist integers and such that show that and are relatively prime.
17. Fibonacci Numbers.
-
Prove that
-
Prove that
-
Show that
Hint.
For Item 2.4.17.a and Item 2.4.17.b use mathematical induction. Item 2.4.17.c Show that and Item 2.4.17.d Use part Item 2.4.17.c. Item 2.4.17.e Use part Item 2.4.17.b and Exercise 2.4.16.
18.
19.
20.
Using the division algorithm, show that every perfect square is of the form or for some nonnegative integer
21.
22.
Let Use the division algorithm to prove that every integer is congruent mod to precisely one of the integers Conclude that if is an integer, then there is exactly one in such that and Hence, the integers are indeed partitioned by congruence mod
23.
Define the least common multiple of two nonzero integers and denoted by to be the nonnegative integer such that both and divide and if and divide any other integer then also divides Prove that any two integers and have a unique least common multiple.
Hint.
Let Then since By the Principle of Well-Ordering, contains a least element To show uniqueness, suppose that and for some By the division algorithm, there exist unique integers and such that where Since and divide both and it must be the case that and both divide Thus, by the minimality of Therefore,
24.
25.
26.
27.
28.
29.
Prove that there are an infinite number of primes of the form
30.
Prove that there are an infinite number of primes of the form
31.
Using the fact that 2 is prime, show that there do not exist integers and such that Demonstrate that therefore cannot be a rational number.
You have attempted 1 of 1 activities on this page.