Chapter 4.7, Problem 31ES

a. Prove by contraposition: For all positive integers n, r. and s, if $rs\le n$, then $r\le \sqrt{n}$or $s\le \sqrt{n}$.

(Hint: Use Theorem T27 in Appendix A.)

b. Prove: For each integer $n>1$ , if n is not prime then there exists a prime number p such that $p\le \sqrt{n}$ and n is divisible by p. (Hint: Use the results of part (a), Theorems 4.4.1, 4.4.3, and 4.4.4, and the transitive property of order.) c. State the contrapositive of the result of part

(b). The results of exercise 31 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.