## 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.

###### Lemma 5.3.1. Euclid.

Let \(a\) and \(b\) be integers and \(p\) be a prime number. If \(p \mid ab\text{,}\) then either \(p \mid a\) or \(p \mid b\text{.}\)

###### Proof.

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

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

###### Theorem 5.3.2. Euclid.

There exist an infinite number of primes.

###### Proof.

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{.}\)

###### Theorem 5.3.3. Fundamental Theorem of Arithmetic.

Let \(n\) be an integer such that \(n \gt 1\text{.}\) Then

where \(p_1, \ldots, p_k\) are primes (not necessarily distinct). Furthermore, this factorization is unique; that is, if

then \(k = l\) and the \(q_i\)'s are just the \(p_i\)'s rearranged.

### Exercises 5.3.1 Exercises

###### 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.