2 Prime numbers and unique factorisation
2.1 Prime numbers
I’m sure you all know this definition:
Definition 2.1
An integer \(p \in \mathbb{N}\) is said to be prime if \(p > 1,\) and the only divisors of \(p\) in \(\mathbb{N}\) are 1 and \(p\) itself. We write \(\mathbb{P}\) for the set of primes.
The first few elements of \(\mathbb{P}\) are \(\{2, 3, 5, 7, 11, \dots \}.\) A number which is not prime is said to be composite.
Exercise 2.2
Show that if \(p > 1\) and \(p\) is not divisible by any integer \(a\) with \(1 < a \leqslant\sqrt{p},\) then \(p\) is prime. Use this to show that 127 is prime. (Hint: \(127 < 12^2 = 144.\))
Remark 2.3
It is conjectured, but not known, that there are infinitely many twin primes – that is, pairs \((p, q)\) of primes with \(q = p + 2,\) such as \((59, 61).\) \(\circledast\)
We’re going to show that any \(n \in \mathbb{N}_+\) can be written uniquely in terms of the primes. First, we need a lemma:
Lemma 2.4
Suppose \(p\) is prime, and \(a, b \in \mathbb{Z}.\) If \(p \mid ab,\) then \(p \mid a\) or \(p \mid b.\)
Proof. Clearly \(\gcd(p, a)\) is a divisor of \(p,\) so it must be 1 or \(p.\) If \(\gcd(p, a) = p,\) then \(p \mid a\) and we’re done. If \(\gcd(p, a) = 1,\) then Euler’s lemma (Lemma 1.20) applies and shows that \(p \mid b.\)
This extends in the obvious way to products of three or more factors: if \(p \mid a_1 \dots a_r,\) then \(p \mid a_i\) for some \(i.\)
Exercise 2.5
Prove the converse: if \(p > 1\) and \(p\) is not prime, there exist integers \(a, b\) with \(p \mid ab\) but \(p \nmid a\) and \(p \nmid b.\)
Remark 2.6
Lemma Lemma 2.4, and its converse, show that a positive integer \(n \in \mathbb{N}_+\) is a prime number iff it is a prime element of the ring \(\mathbb{Z}\) in the sense of the M11 Algebra course.
2.2 Unique factorisation
Theorem 2.7 • Fundamental Theorem of Arithmetic
Every positive integer \(n\) can be written as a product of prime numbers, and its factorisation into primes is unique up to the order of the factors.
Note that this includes \(n = 1,\) which is an empty product (the product of no primes); and the primes themselves, with only one factor in the product.
Proof. Existence: Let \(n \in \mathbb{N}_+.\) By Strong Induction, we may suppose the theorem is true for all \(m\) with \(m < n.\)
If \(n = 1,\) then the statement is trivial (product of no primes). So let’s suppose \(n > 1.\) If \(n\) is prime, we’re again fine (product of one prime). So \(n\) must be of the form \(a b\) with \(1 < a, b < n.\) By the induction hypothesis, both \(a\) and \(b\) are products of primes, hence so is \(n.\)
Uniqueness: Suppose \(n = p_1 p_2 \dots p_r = q_1 q_2 \dots q_s\) are two prime factorisations of \(n.\) We want to deduce that \(s = r\) and the \(q\)’s can be re-ordered such that \(q_i = p_i.\) We shall argue by induction on \(r.\)
If \(r = 0,\) then \(n = 1\); thus \(s = 0\) as well (since any nontrivial product of primes is \(> 1\)) so we’re done.
Now suppose \(r \geqslant 1\) and the theorem is true for \(r-1.\) Then \(p_r \mid q_1\dots q_s.\) Hence \(p_r \mid q_i\) for some \(i,\) and after reordering we may suppose \(p_r \mid q_s.\) Since \(q_s\) is prime (and \(p_r > 1\)), this implies \(p_r = q_s.\) Since \(p_r\) is not zero, we deduce that \(p_1 \dots p_{r-1} = q_1 \dots q_{s-1}.\) By the induction hypothesis, \(r - 1 = s - 1,\) so \(r = s\); and \(q_1, \dots, q_{s - 1}\) are \(p_1, \dots, p_{r-1}\) in some order. So we are done.
Collecting together any powers of primes which occur in a prime factorization, we obtain two alternative formulations:
Corollary 2.8
Every positive integer \(n\) may be expressed uniquely in the form \[n = p_1^{r_1} p_2^{r_2} \dots p_k^{r_k}\] where \(k \geqslant 0,\) \(p_1, \dots, p_k\) are primes with \(p_1 < p_2 < \dots < p_k,\) and \(r_i\) are integers with \(r_i \geqslant 1.\)
Alternatively, every positive integer n may be expressed uniquely in the form \[n = \prod_{p \in \mathbb{P}} p^{e_p}\] where \(e_p \in \mathbb{N}\) for all \(p,\) and all but finitely many \(e_p\) are zero.0◻
The exponent \(e_p\) which appears in this standard factorization of \(n\) is denoted \(\mathop{\mathrm{ord}}_p(n)\); it is characterized by the following property: \[e = \mathop{\mathrm{ord}}_p(n) \iff p^e |n\ \text{and}\ p^{e+1} \nmid n.\] For example, \(700 = 2^2 \cdot 5^2 \cdot 7,\) so \(\mathop{\mathrm{ord}}_2(700) = \mathop{\mathrm{ord}}_5(700) = 2,\) \(\mathop{\mathrm{ord}}_7(700) = 1,\) and \(\mathop{\mathrm{ord}}_p(700) = 0\) for primes \(p \ne 2, 5, 7.\) Every positive integer \(n\) is uniquely determined by the sequence of exponents \(\mathop{\mathrm{ord}}_p(n).\) From the uniqueness of the factorisation, it follows that \[\tag{2.1} \mathop{\mathrm{ord}}_p(m n) = \mathop{\mathrm{ord}}_p(m) + \mathop{\mathrm{ord}}_p(n)\qquad \forall m, n \in \mathbb{N}_+, p \in \mathbb{P}.\]
Proposition 2.9
Let \(m, n \in \mathbb{N}_+.\) Then \(m \mid n\) iff \(\mathop{\mathrm{ord}}_p(m) \leqslant\mathop{\mathrm{ord}}_p(n)\) for all \(p \in \mathbb{P}.\)
Proof. If \(m \mid n,\) then \(n = k m\) for some \(k \in \mathbb{N}_+.\) From (2.1) it follows that \(\mathop{\mathrm{ord}}_p(n) = \mathop{\mathrm{ord}}_p(k) + \mathop{\mathrm{ord}}_p(m) \geqslant\mathop{\mathrm{ord}}_p(m)\ \forall p.\)
Conversely, if \(\mathop{\mathrm{ord}}_p(m) \leqslant\mathop{\mathrm{ord}}_p(n)\) for every \(p,\) let \(k = \prod_p p^{\mathop{\mathrm{ord}}_p(n) - \mathop{\mathrm{ord}}_p(m)},\) which is in \(\mathbb{N}_+\) since all the exponents are non-negative (and all but finitely many of them are zero). Then we have \(n = k m.\)
Corollary 2.10
We have \(\gcd(m, n) = 1\) iff there is no prime which divides both \(m\) and \(n.\)
Proof. The primes which divide \(\gcd(m, n)\) are precisely the primes dividing both \(m\) and \(n,\) by the characterising property of the gcd. It follows from the existence of prime factorisations that for any \(k \in \mathbb{N}_+,\) we have \(k > 1\) iff some prime divides \(k\); applying this to \(k = \gcd(m, n)\) we are done.
Exercise 2.11
Show that for any \(m, n \in \mathbb{N}_+,\) we have \[\gcd(m, n)= \prod_{p \in \mathbb{P}} p^{\min(\mathop{\mathrm{ord}}_p(m), \mathop{\mathrm{ord}}_p(n))}.\]
2.3 Infinitude of primes
No introductory course on number theory could possibly omit the following theorem:
Theorem 2.12 • Euclid
There are infinitely many primes.
Proof. Suppose there are only finitely many primes \(p_1, \dots, p_k.\) Consider the integer \(N = (p_1 p_2 \dots p_k) + 1.\) Then all the \(p_i\) divide \(N - 1\); so none of them can divide \(N\) (since otherwise they’d have to divide 1). But \(N > 1,\) so \(N\) must have some prime factors. This contradicts our assumption that \(\{p_1, \dots, p_k\}\) are all the primes.
There are lots of variants of this argument which can be used to construct primes with some special shape; we’ll see a few in the next chapter.
Remark 2.13
Although there are infinitely many primes, they get “thinner and thinner” as you go further out. Gauss and Legendre conjectured around 1800 that the ratio \[\frac{\#\{p \in \mathbb{P}: p \leqslant X\}}{X / \log X}\] tends to 1 as \(X \to \infty.\) So for large \(X,\) the fraction of integers up to \(X\) which are prime is roughly \(1 / \log(X),\) which tends very slowly to 0.
This conjecture was open for over 100 years, until it was finally proved by Hadamard and de la Vallée Poussin in 1896. A measure of the importance of this theorem is that, among all of the thousands of theorems about prime numbers, theirs is universally known as “the prime number theorem”.
Exercise 2.14
Does there exist \(n \in \mathbb{N}\) such that all of the numbers \(n + 1, n + 2, \dots, n + 20\) are composite?