Solved: Use the well-ordering principle for the integers

Chapter 5, Problem 20E

(choose chapter or problem)

Problem 20E

Use the well-ordering principle for the integers to prove Theorem 4.3.4: Every integer greater than 1 is divisible by a prime number.

Theorem

Divisibility by a Prime

Any integer n > 1 is divisible by a prime number.

Proof:

Suppose n is a [particular but arbitrarily chosen] integer that is greater than 1. [We must show that there is a prime number that divides n.] If n is prime, then n is divisible by a prime number (namely itself), and we are done. If n is not prime, then, as discussed in Example 1.

n = r0s0 where r0 and s0 are integers and

1 < ro and 1<so <n

It follows by definition of divisibility that r0|n.

If r0 is prime, then r0 is a prime number that divides n. and we are done. If r0 is not prime, then

ro = r1s1 where r1 and s1 are integers and

1<r10 and 1<s1 < r0.

It follows by the definition of divisibility that r1|r0. But we already know that r0 |n. Consequently, by transitivity of divisibility. r1|n.

If r1 is prime, then r1 is a prime number that divides n, and we are done. If r1 is not prime, then

r1= r2s2 where n and s2 are integers and 1<r1< r2 and 1<s2<r1.

It follows by definition of divisibility that r2|r1. But we already know that r1|r2. Consequently, by transitivity of divisibility, r2| n.

If r2 is prime, then r2 is a prime number that divides n, and we are done. If r2 is not prime, then we may repeat the previous process by factoring r2 as r3s3.

We may continue in this way, factoring successive factors of n until we find a prime factor. We must succeed in a finite number of steps because each new factor is both less than the previous one (which is less than n) and greater than 1. and there are fewer than n integers strictly between 1 and n.* Thus we obtain a sequence

r0,r1,…rk,

where k ≥ 0, 1<rk<rk–1 <…< r2<r1<r0 < n, and r1 | n for each i = 0, 1,2…,k.The condition for termination is that rk should be prime. Hence rk is a prime number that divides n. [This is what we were to show.]

Example

Prime and Composite Numbers

a. Is 1 prime?

b. Is ever)' integer greater than I either prime or composite?

c. Write the first six prime numbers.

d. Write the first six composite numbers.

Solution

a. No. A prime number is required to be greater than 1.

b. Yes. Let n be any integer that is greater than I. Consider all pairs of positive integers r and s such that n = rs. There exist at least two such pairs, namely r = n and s =1 and r = 1 and s = n. Moreover, since n = rs. all such pairs satisfy the inequalities 1 ≤ r ≤n and 1 ≤ s ≤ n. If n is prime, then the two displayed pairs are the only ways to write n as rs. Otherwise, there exists a pair of positive integers r and 5 such that n = rs and neither r nor s equals either 1 or n. Therefore, in this case 1<r and I<s and hence n is composite.

c. 2. 3.5.7. 11, 13

d. 4.6. 8.9. 10. 12