12 1. The Real Numbers

pattern similar to the one above for addition. Once multiplication is defined, we

can define factors and prime numbers:

Definition 1.2.7. If a number n ∈ N can be written as n = mk with both m ∈ N

and k ∈ N, then k and m are called factors of n and are said to divide n. If n = 1

and the only factors of n are 1 and n, then n is said to be prime.

The order relation in N can be defined as follows:

Definition 1.2.8. If n, m ∈ N, we will say that n is less than m, denoted n m,

if there is a k ∈ N such that m = n + k. We say n is less than or equal to m and

write n ≤ m if n m or n = m.

Some of the properties of this order relation are worked out in the exercises.

One of these is that each factor of n is necessarily less than or equal to n (Exercise

1.2.7).

Example 1.2.9. Prove that each natural number n 1 is a product of primes.

Solution: Here we understand that a prime number itself is a product of

primes – a product with only one factor. Note that if k and m are two numbers

which are products of primes, then their product km is also a product of primes.

Let the proposition Pn be that every m ∈ N, with 1 m ≤ n, is a product of

primes.

Base case: P1 is true because there is no m ∈ N with 1 m ≤ 1.

Induction step: Suppose n is a natural number for which Pn is true. Then each

m with 1 m ≤ n is a product of primes. Now n + 1 1 and so it is either a

prime or it factors as a product km with k and m not equal to 1 or n + 1. In the

first case, Pn+1 is true. In the second case, both k and m are less than n + 1 and,

hence, less than or equal to n. Since Pn is true, k and m are products of primes.

This implies that n + 1 = km is also a product of primes and, in turn, this implies

that Pn+1 is true.

By induction, Pn is true for all n ∈ N and this means that every natural number

n 1 is a product of primes.

Additional Examples of the Use of Induction. At this point we leave the

discussion of Peano’s axioms and the development of the properties of the natural

numbers. The remainder of the section is devoted to further examples of inductive

proofs and inductive definitions. Some of these involve the real number system,

which won’t be discussed until Section 1.4. Nevertheless we are happy to anticipate

its development and use its properties in these examples.

Example 1.2.10. Prove by induction that every number of the form 5n −2n, with

n ∈ N, is divisible by 3.

Solution: The proposition Pn is that 5n − 2n is divisible by 3.

Base case: Since 5 − 2 = 3, P1 is true.

Induction step: We need to show that Pn+1 is true whenever Pn is true. We

do this by rewriting the expression

5n+1

−

2n+1

as

5n+1

− 5 ·

2n

+ 5 ·

2n

−

2n+1

=

5(5n

−

2n)

+ (5 −

2)2n.