Skip to main content

Section 5.3 Prime 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

Exercises 5.3.1 Exercises


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


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


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


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.