Elementary Number Theory and Its Application, 6th Edition by Kenneth H. Rosen Exercises 1.1.2

 2. Show that if a and b are positive integers, then there is a smallest positive integer of the form a – bk, k \in Z.

Solution:

Let a and b be positive integers and let S = { n : n is a positive integer and n = a – bk for some k \in \mathbb{Z}. Now S is non empty since a + b = a – b( – 1) is in S . By the Well Ordering Principle S has a least element.

Elementary Number Theory and Its Application, 6th Edition by Kenneth H. Rosen Exercises 1.1.1

1.  Determine whether each of the following sets is well ordered. Either give a proof using the well-ordering property of the set of positive integers, or give an example of a subset of the set that has no smallest element.
a) the set of integers greater than 3
b) the set of even positive integers
c) the set of positive rational numbers
d) the set of positive rational numbers that can be written in the form a/2, where a is a positive integer
e) the set of nonnegative rational numbers

Solution:

We begin by stating the Well Ordering Principle. It states that every non-empty set of positive integers has a smallest element.

(a) The set of Integers greater than 3 is well ordered as it is non-empty set of positive Integers and the smallest element in this set is 3.

(b) The set of even positive Integers is well ordered as it is non-empty set of positive Integers and the smallest element in this set is 2.

(c) The set of positive rational numbers is not well ordered. Let us take a subset of this set as

\left\{ 1,\frac{1}{2},\frac{1}{3},\frac{1}{4},...\right\}

We can see that this non-empty positive subset has no least element. Instead it has a greatest element 1.

(d) The set of positive rational numbers of form \frac{a}{2} where a , is a positive integer is well Ordered.

The smallest positive Integer is 1 so the smallest positive rational number in this set is \frac{1}{2}

(e) The set of non-negative rational numbers is not well ordered. We take a subset of this set as the set of positive rational numbers which has a least element as can been seen from part (c).