Let p1, p2, p3, … be a list of all prime numbers in ascending order. Here is a table of th...

Let p1, p2, p3, … be a list of all prime numbers in ascending order. Here is a table of the first six:

a. For each i = 1, 2, 3, 4, 5, 6, let Ni = p1 p2 … pi + 1. Calculate N1, N2, N3, N4, N5, and N6.

---

b. For each i = 1, 2, 3, 4, 5, 6, find the smallest prime number qi such that qi divides Ni. (Hint: Use the test for primality from exercise to determine your answers.)

Exercise

a. Prove by contraposition: For all positive integers n, r, and s, if rs ≤ n, then r ≤  or s ≤ .

---

b. Prove: For all integers n > 1, if n is not prime, then there exists a prime number p such that p ≤  and n is divisible by p. (Hints: Use the result of part (a) and Theorems 1, 2, and 3.)

---

c. State the contrapositive of the result of part (b).

The results of exercise provide a way to test whether an integer is prime.

Test for Primality

Given an integer n > 1, to test whether n is prime check to see if it is divisible by a prime number less than or equal to its square root. If it is not divisible by any of these numbers, then it is prime.

Theorem 1

A Positive Divisor of a Positive Integer

For all integers a and b, if a and b are positive and a divides b, then a ≤ b.

Proof:

Suppose a and b are positive integers and a divides b. [We must show that a ≤ b.] Then there exists an integer k so that b = ak. By property T25 of Appendix A, k must be positive because both a and b are positive. It follows that

1 ≤ k

because every positive integer is greater than or equal to 1. Multiplying both sides by a gives

a ≤ ka = b

because multiplying both sides of an inequality by a positive number preserves the inequality by property T20 of Appendix A. Thus a ≤ b [as was to be shown].

Theorem 2

Transitivity of Divisibility

For all integers a, b, and c, if a divides b and b divides c, then a divides c.

Proof:

Suppose a, b, and c are [particular but arbitrarily chosen] integers such that a divides b and b divides c. [We must show that a divides c.] By definition of divisibility,

b = ar and c = bs for some integers r and s.

By substitution

Let k = rs. Then k is an integer since it is a product of integers, and therefore

c = ak where k is an integer.

Thus a divides c by definition of divisibility. [This is what was to be shown.]

Theorem 3

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,

n = r0s0 where r0 and s0 are integers and 1 < r0 < n and 1 < s0 < 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

r0 = r1s1 where r1 and s1 are integers and 1 < r1 < r0 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 r2 and s2 are integers and 1 < r2 < r1 and 1 < s2 < r1.

It follows by definition of divisibility that r2 | r1. But we already know that r1 | n. 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, r2, …, rk ,

where k ≥ 0, 1 < rkk−1 <…< r2 < r1 < r0 < n, and ri | 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 every integer greater than 1 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 1. 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 s such that n = rs and neither r nor s equals either 1 or n. Therefore, in this case 1 < r and 1 < s, and hence n is composite.

---

c. 2, 3, 5, 7, 11, 13

---

d. 4, 6, 8, 9, 10, 12