## Section5.3Prime Numbers

Let $p$ be an integer such that $p \gt 1\text{.}$ We say that $p$ is a prime number, or simply $p$ is prime, if the only positive numbers that divide $p$ are $1$ and $p$ itself. An integer $n \gt 1$ that is not prime is said to be composite.

Suppose that $p$ does not divide $a\text{.}$ We must show that $p \mid b\text{.}$ Since $\gcd( a, p ) = 1\text{,}$ there exist integers $r$ and $s$ such that $ar + ps = 1\text{.}$ So

\begin{equation*} b = b(ar + ps) = (ab)r + p(bs)\text{.} \end{equation*}

Since $p$ divides both $ab$ and itself, $p$ must divide $b = (ab)r + p(bs)\text{.}$

We will prove this theorem by contradiction. Suppose that there are only a finite number of primes, say $p_1, p_2, \ldots, p_n\text{.}$ Let $P = p_1 p_2 \cdots p_n + 1\text{.}$ Then $P$ must be divisible by some $p_i$ for $1 \leq i \leq n\text{.}$ In this case, $p_i$ must divide $P - p_1 p_2 \cdots p_n = 1\text{,}$ which is a contradiction. Hence, either $P$ is prime or there exists an additional prime number $p \neq p_i$ that divides $P\text{.}$

The proof of Theorem 5.3.3 can be found in Subsection A.3

### Exercises5.3.1Exercises

###### 1.

Let $p \geq 2\text{.}$ Prove that if $2^p - 1$ is prime, then $p$ must also be prime.

###### 2.

Prove that there are an infinite number of primes of the form $6n + 5\text{.}$

###### 3.

Prove that there are an infinite number of primes of the form $4n - 1\text{.}$

###### 4.

Using the fact that $2$ is prime, show that there do not exist integers $p$ and $q$ such that $p^2 = 2 q^2\text{.}$ Demonstrate that therefore $\sqrt{2}$ cannot be a rational number.