Divisibility and Primes

Sets and Closure#

A set is an unordered collection of distinct mathematical objects.
Sets can be denoted by $S=\{a,b,c\}$, where $S$ is a set and $a,b$ and $c$ are elements of the set $S$.

To represent membership, we use $x \in S$, stating that $x$ is in $S$. Therefore, we can say that $a \in S,$ read as "$a$ is an element of $S$".

A subset is a set whose elements are also all elements of another set; denoted as $T \subseteq S$. We can say that $\{b\} \subseteq S$ as $\{b\}$ is a set containing the element $b$.

Some examples of special sets include:

$$\mathbb{N} = \{0,1,2,3,4,5,\dots\}$$

called the set of natural numbers, which are all whole numbers from zero onwards. It is important to remember that the naturals contains 0.
Another set can be the set of integers,

$$\mathbb{Z} = \{\dots,-3,-2,-1,0,1,2,3,\dots\}$$

which is the set of naturals with the inclusion of the negative numbers.
You can also restrict sets with rules, such as:

$$\mathbb{Z}^+ = \{1,2,3,\dots\}$$

which is the set of positive integers, (notice the $+$ sign).
Another set can be the rational numbers,

$$\mathbb{Q} = \{\frac{p}{q}:p \in \mathbb{Z}, q \in \mathbb{Z}^+ \}$$

where $p$ is any integer, and $q$ is a positive integer, representing any number that is a fraction.
Furthermore, there is the set of the reals,

$$\mathbb{R} = \{\text{All points on the real number line}\},$$

which includes irrational numbers such as $\sqrt{2}$ or $\pi$.
And finally, there is the set of the complex numbers,

$$\mathbb{C} = \{a+bi: a,b \in \mathbb{R}, i^2=-1\}$$

Note:

$$\mathbb{Z}^+ \subseteq \mathbb{N} \subseteq \mathbb{Z} \subseteq \mathbb{Q} \subseteq \mathbb{R} \subseteq \mathbb{C}.$$

A set $S$ is said to be closed under addition if for any $x,y \in S$, $x+y \in S$.
This means that addition between any two elements within a set must also result in an element in that same set:

$$-2,3 \in \mathbb{Z} \Rightarrow -2 + 3 \in \mathbb{Z}.$$

Each of the sets that we've looked at so far are closed under addition.

A set $S$ is said to be closed under multiplication if for any $x,y \in S, x \cdot y \in S$;

$$\sqrt{2},e \in \mathbb{R} \Rightarrow \sqrt{2} \cdot e \in \mathbb{R}$$

Each of the sets that we've looked at so far are also closed under multiplication.

Example. A set $S$ is said to be closed under subtraction if, given any $x,y \in S$, we have that $x - y \in S$.
Decide whether each of the following sets is closed under subtraction.

$$\begin{align*} \text{ Consider } &1,2 \in \mathbb{N}, \mathbb{Z}^+, \\ &1-2 = -1, \\ \text{ However, } &-1 \notin \mathbb{N}, \mathbb{Z}^+. \end{align*}$$

Example. Decide whether each of the following sets is closed under division (excluding division by $0$): $\mathbb{N}, \mathbb{Z}, \mathbb{Z}^+, \mathbb{Q}, \mathbb{R}, \mathbb{C}$.
None of $\mathbb{N},\mathbb{Z}$ or $\mathbb{Z}^+$ are closed under division;

$$\begin{align*} \text{ Consider } &1,2 \in \mathbb{N}, \mathbb{Z}, \mathbb{Z}^+, \\ &1\div 2 = \frac{1}{2}, \\ \text{ However, } &\frac{1}{2} \notin \mathbb{N}, \mathbb{Z}, \mathbb{Z}^+. \end{align*}$$

On the other hand, $\mathbb{Q},\mathbb{R}$ and $\mathbb{C}$ are closed under division; dividing by any non-zero element keeps you in the set. For example, given $\frac{p}{q}, \frac{r}{s} \in \mathbb{Q}$ with $\frac{r}{s} \neq 0$,

$$\frac{p}{q} \div \frac{r}{s} = \frac{ps}{qr},$$

which is still a ratio of integers with a non-zero denominator; i.e. still rational. Therefore, $\mathbb{Q}, \mathbb{R}$ and $\mathbb{C}$ are closed under division, whilst $\mathbb{N}, \mathbb{Z}$ and $\mathbb{Z}^+$ are not.

This failure of closure is basically the reason Number Theory exists; since dividing one integer by another is not guaranteed to give an integer, the special cases where it does are worth studying in their own right. That is exactly the idea of divisibility.

Divisibility#

Given two integers $a$ and $b$, we say that $a$ divides $b$ if we can write $b = ak$, for some integer $k$. This can also be represented by

$$\begin{align*} a \mid b \text{, read as ‘} a \text{ divides } b \text{' and means that } b=ak \text{ for some integer } k. \\ a \nmid b \text{ read as ‘} a \text{ does not divide } b \text{' and means that } b \neq ak \text{ for any integer } k. \end{align*}$$

Notice that the first statement requires at least one integer $k$, whilst the second requires it to be false for any integer $k$.

If $a \mid b$, we can equivalently say that $a$ is a divisor of $b$, $a$ is a factor of $b$, $b$ is divisible by $a$, or $b$ is a multiple of $a$; these all mean exactly the same thing, so don't get thrown off if a question uses one phrasing over another.

Example. Decide whether the following statements are true or false.

$$\begin{align*} 3 \mid 15 &: \text{ True, since } 15 = 3 \times 5. \\ 15 \mid 3 &: \text{ False, since } 3 = 15k \text{ forces } k = \tfrac{1}{5} \notin \mathbb{Z}. \\ 3 \mid 3 &: \text{ True, since } 3 = 3 \times 1. \\ -5 \mid 15 &: \text{ True, since } 15 = (-5) \times (-3). \end{align*}$$

Notice how the order matters ($3 \mid 15$ but $15 \nmid 3$), and how divisors are perfectly allowed to be negative; $k$ just has to be some integer.

Example. Is it true that $0 \mid 3$?
Using our definition, in order for it to be true, we would need to be able to find an integer $k$ such that $3$ is equal to $0$ times $k$;

$$3 = 0k, k \in \mathbb{Z}.$$

However, the right hand side here is always going to be equal to zero regardless of $k$, therefore
$0 \nmid 3$.

Example. Is it true that $3 \mid 0$?
Using our definition again, we need to find an integer $k$ such that 0 is equal to 3 times $k$,

$$0 = 3k, k \in \mathbb{Z},$$

we can see here that setting $k=0$, we see that the statement is true. Therefore, $3 \mid 0$.

Regarding 0, is it true that $0 \mid 0$?
It is indeed true; every number divides 0, including 0 itself.

Example. For which integers $x$ is it true that $0 \mid x$?
By the definition, $0 \mid x$ requires an integer $k$ with

$$\begin{align*} x &= 0k \\ x &= 0. \end{align*}$$

So the only integer that $0$ divides is $0$ itself. Therefore, $0 \mid x$ if and only if $x = 0$.

Be careful not to mix up the two directions: every integer divides $0$, but $0$ divides nothing except $0$.

$$\boxed{x \mid 0 \text{ for all } x \in \mathbb{Z}, \quad \text{but} \quad 0 \mid x \iff x = 0.}$$

A couple of handy facts fall straight out of these lemmas:

• $a \mid am$ for any integer $m$; take $b = c = a$ and $x = m, y = 0$ in Lemma 1.3.
• If $a \mid b$, then $a \mid bm$ for any integer $m$; take $c = b$ and $x = m, y = 0$.

Basically, once $a$ divides something, it also divides every multiple of that thing, and every "integer combination" of things it already divides. Lemma 1.3 is the real workhorse of this topic; most divisibility proofs boil down to writing your target as $bx + cy$ for clever choices of $x$ and $y$.

Example. Suppose that $a$ is a positive integer such that $a \mid 2n+3$ and $a \mid n+1$ for some integer $n$. Show that $a = 1$.
The trick is to use Lemma 1.3 to eliminate $n$. Choosing $x = 1$ and $y = -2$,

$$\begin{align*} a &\mid (2n+3)(1) + (n+1)(-2) \\ a &\mid 2n+3-2n-2 \\ a &\mid 1. \end{align*}$$

The only positive integer dividing $1$ is $1$ itself. Therefore, $a = 1$.

Example. Prove that $3 \mid 4^n - 1$ for all $n \in \mathbb{N}$.
This is a classic induction + divisibility combo; whenever the $n$ sits in an exponent, induction is usually the way to go.
Let $P(n)$ be the statement "$3 \mid 4^n -1$".
Base case: $P(0)$ states that $3 \mid 4^0 - 1$, i.e. $3 \mid 0$, which is true since every integer divides $0$.
Inductive step: suppose that $P(n)$ holds, i.e. $3 \mid 4^n - 1$. Then,

$$\begin{align*} 4^{n+1} - 1 &= 4 \cdot 4^n - 1 \\ &= 4(4^n - 1) + 4 - 1 \\ &= 4(4^n-1) + 3. \end{align*}$$

Since $3 \mid 4^n - 1$ (inductive hypothesis) and $3 \mid 3$ (reflexivity), Lemma 1.3 with $x = 4, y = 1$ tells us that $3 \mid 4(4^n-1) + 3(1)$; that is, $3 \mid 4^{n+1}-1$. Hence $P(n) \Rightarrow P(n+1)$, and by induction $3 \mid 4^n - 1$ for all $n \in \mathbb{N}$. $\blacksquare$

Example. Prove that for all integers $n$, if $3 \nmid n^2$ then $3 \nmid n$.
Proving this directly is awkward, because "$\nmid$" gives us no equation to work with. Instead, we prove the contrapositive, which is logically equivalent:

$$\text{if } 3 \mid n \text{, then } 3 \mid n^2.$$

Proof. Suppose that $3 \mid n$, so $n = 3k$ for some $k \in \mathbb{Z}$. Then,

$$\begin{align*} n^2 &= (3k)^2 \\ &= 9k^2 \\ &= 3(3k^2). \end{align*}$$

Since $3k^2 \in \mathbb{Z}$, we have $3 \mid n^2$; this proves the contrapositive, and hence the original statement. $\blacksquare$
When a divisibility statement starts with "does not divide", try the contrapositive first; it turns $\nmid$ into $\mid$, which hands you an actual equation like $n = 3k$ to substitute.

Primes#

Uhm this is self explanatory so I'm not gonna write much;

A prime is defined as a number in $\mathbb{Z}$ such that it is not $0 \text{ or } \pm1$, and it's only divisors are $\pm 1$ and the number itself.

A composite is a number in $\mathbb{Z}$ that is not $0, \pm 1$ or a prime.

More formally, the lecture defines primes via irreducibility:

Basically, a prime refuses to factorise; the only way to write it as a product of integers is the boring way, $\pm 1$ times $\pm$ itself. The first few prime numbers are $2,3,5,7,11,13,17,19,\dots$, but notice that over $\mathbb{Z}$ the prime integers also include the negatives $-2,-3,-5,-7,\dots$, and likewise the composite integers include $-4, -6, -8, -9, \dots$. The numbers $0$ and $\pm 1$ are deliberately excluded from both camps (what makes them so special gets explored later in the course, in Lectures 2.3, 3.2 and 7.1).

Basically, a prime cannot be "split" across a product; if it divides the whole thing, it must divide at least one of the pieces. This property is actually how prime elements are defined in general (the proof is in Lecture 1.3).

It is important to note that this property fails for composite numbers. For example, $6 \mid 4 \times 9$ (since $4 \times 9 = 36 = 6 \times 6$), yet $6 \nmid 4$ and $6 \nmid 9$; the $6$ got split into a $2$ (hiding inside the $4$) and a $3$ (hiding inside the $9$). That can only happen because $6$ is composite.

Example. Suppose that $p$ is prime and $p \mid a^2$ for some integer $a$. Show that $p \mid a$.
Since $a^2 = a \cdot a$, applying the theorem with $b = a$ gives

$$p \mid a \cdot a \implies p \mid a \text{ or } p \mid a,$$

which is just $p \mid a$. Therefore, $p \mid a$; a prime dividing a perfect square must divide the base. (This is the key step in the classic proof that $\sqrt{2}$ is irrational.)

Example. Prove that $6 \mid n^3 - n$ for all integers $n$.
First, factorise;

$$\begin{align*} n^3 - n &= n(n^2-1) \\ &= (n-1)n(n+1), \end{align*}$$

which is a product of three consecutive integers. Out of any two consecutive integers one must be even, so $2 \mid n^3 - n$; out of any three consecutive integers one must be a multiple of $3$, so $3 \mid n^3 - n$.
Now we combine the two. Write $n^3 - n = 3\ell$ for some $\ell \in \mathbb{Z}$. Since $2 \mid 3\ell$ and $2$ is prime, the prime divisor theorem says that $2 \mid 3$ or $2 \mid \ell$; clearly $2 \nmid 3$, so $2 \mid \ell$, i.e. $\ell = 2k$ for some $k \in \mathbb{Z}$. Hence,

$$\begin{align*} n^3 - n &= 3\ell \\ &= 3(2k) \\ &= 6k. \end{align*}$$

Therefore, $6 \mid n^3 - n$ for every integer $n$. $\blacksquare$
Notice how "$2 \mid m$ and $3 \mid m$, therefore $6 \mid m$" needed an actual argument; you cannot just multiply divisors together in general ($4 \mid 12$ and $6 \mid 12$, but $24 \nmid 12$). It only worked here because one of the divisors was a prime not dividing the other.

Example. Suppose $p \mid a$ where $p$ is prime and $a$ is an integer. Prove that $p \nmid a + 1$.
Suppose, for contradiction, that $p \mid a$ and $p \mid a+1$. By Lemma 1.3 with $x = -1, y = 1$,

$$\begin{align*} p &\mid a(-1) + (a+1)(1) \\ p &\mid 1. \end{align*}$$

But the only divisors of $1$ are $\pm 1$, and a prime is not $\pm 1$; contradiction. Therefore, $p \nmid a+1$. In other words, consecutive integers never share a prime factor — keep this in your back pocket, it is exactly the trick that powers Euclid's proof below.

Mersenne primes are primes of the form $2^p -1$ where $p$ is prime.

Fermat primes are primes of the form $2^{2^n} +1$ where $n$ is a natural number.

Twin prime pairs are pairs of primes that differ from each other by 2, such as $(3,5)$ or $(71,73).$

Sophie Germain primes are primes $p$ for which $2p+1$ is also prime, such as
$3$ (since 7 is prime) or $53$ (since 107 is prime).

For such a fundamental object, surprisingly little is actually known about primes; it is still an open problem whether there are infinitely many of any of the four types above. Some things we do know:

• The largest known Mersenne prime to date is $2^{82\,589\,933} - 1$.
• Only five Fermat primes are currently known: $3, 5, 17, 257, 65537$.
• It was shown in 2018 (Maynard, Tao, Zhang, et al.) that there are infinitely many pairs of primes that differ by at most $246$; the largest known twin prime pair has $388342$ digits in each prime.
• The largest known Sophie Germain pair $(p, 2p+1)$ also starts with a $388342$-digit prime.

This mystery is also useful; finding large primes is computationally hard, but doing arithmetic with them is computationally easy, and cryptography schemes are built exactly on that imbalance (more on this later in the course).

Example. We have $2047 = 2^{11} - 1$, and $11$ is prime. Is $2047$ a Mersenne prime?
No! Checking small prime divisors,

$$\begin{align*} 2047 &= 23 \times 89, \end{align*}$$

so $2047$ is composite, and being composite it cannot be a Mersenne prime (or any kind of prime). A prime exponent $p$ does not guarantee that $2^p - 1$ is prime; it only makes it a candidate. Compare with $2^5 - 1 = 31$ and $2^7 - 1 = 127$, which really are Mersenne primes.

Example. Show that if $2^n - 1$ is prime, then $n$ must be prime.
This explains why the Mersenne definition insists on a prime exponent in the first place. Once again the direct statement is awkward, so we prove the contrapositive: if $n$ is composite, then $2^n - 1$ is composite.
Suppose that $n = ab$, where $a, b$ are integers with $1 < a, b < n$. Recall the factorisation $x^b - 1 = (x-1)(x^{b-1} + x^{b-2} + \dots + x + 1)$; substituting $x = 2^a$,

$$\begin{align*} 2^n - 1 &= (2^a)^b - 1 \\ &= (2^a - 1)\left( (2^a)^{b-1} + (2^a)^{b-2} + \dots + 2^a + 1 \right). \end{align*}$$

Since $1 < a < n$, we have $1 < 2^a - 1 < 2^n - 1$, so $2^a - 1$ is a divisor of $2^n - 1$ that is neither $1$ nor the number itself; hence $2^n - 1$ is composite. $\blacksquare$
For instance, $2^4 - 1 = 15 = (2^2-1)(2^2+1) = 3 \times 5$; a composite exponent never even had a chance.

Example. Classify each of $5$, $31$ and $257$ as Mersenne, Fermat, twin and/or Sophie Germain primes.
For $5$:

$$\begin{align*} 5 &= 2^{2^1} + 1 &&\text{Fermat prime}, \\ (3,5) \text{ and } (5,7) &\text{ are both prime pairs} &&\text{twin prime (twice over)}, \\ 2(5) + 1 &= 11, \text{ which is prime} &&\text{Sophie Germain prime}. \end{align*}$$

It is not Mersenne, since $2^p - 1 = 5$ would need $2^p = 6$, which is not a power of $2$.
For $31$:

$$\begin{align*} 31 &= 2^5 - 1, \text{ and } 5 \text{ is prime} &&\text{Mersenne prime}, \\ (29, 31) &\text{ is a prime pair} &&\text{twin prime}. \end{align*}$$

It is not Fermat ($2^{2^n} = 30$ is impossible) and not Sophie Germain, since $2(31)+1 = 63 = 7 \times 9$ is composite.
For $257$:

$$\begin{align*} 257 &= 2^{2^3} + 1 &&\text{Fermat prime}. \end{align*}$$

It is not Mersenne ($2^p - 1 = 257$ would need $2^p = 258$, which is not a power of $2$), not twin ($255 = 5 \times 51$ and $259 = 7 \times 37$ are both composite) and not Sophie Germain, since $2(257) + 1 = 515 = 5 \times 103$ is composite.
Therefore, $5$ is simultaneously Fermat, twin and Sophie Germain; $31$ is Mersenne and twin; and $257$ is only Fermat. The categories are not mutually exclusive — always check each definition separately.

Two Key Theorems about Primes#

$$n = p_1^{\alpha_1} p_2^{\alpha_2} p_3^{\alpha_3} \dots p_k^{\alpha_k}$$

where $p_1,p_2 \dots p_k$ are primes such that $p_1 < p_2 < \dots < p_k$ and $\alpha_1, \alpha_2, \dots, \alpha_k$ are positive integers for some $k \in \mathbb{Z}^+$.

Strong Induction
Involves two things,
(1). Proving a base case $P(n_0)$.
(2). Proving that if $P(m)$ holds for all $n_0 \leq m < n$, then $P(n)$ holds.
In other words, strong induction involves proving that every value less than $n$ is true in order to verify if $n$ is true for a given statement.
If $p(0)$ and $p(1)$ is true, we can use this information to confirm whether or not $p(2)$ is true;

$$\left. \begin{matrix} P(n_0) \\ P(n_0 + 1) \\ \vdots \\ P(n - 1) \end{matrix} \right\} \longrightarrow P(n).$$

We now use strong induction to prove the Fundamental theorem of Arithmetic.
In order to complete our induction we simply need to confirm if for all $p(m)$,

$$\boxed{P(m)=\text{“The integer } m \text{ has a unique prime factorisation"}. }$$

(1).
Our base case can be $P(2)$, since 2 is the smallest number that is itself a prime and is its own unique prime factorisation. With this, we have completed the first step.

(2).
Since our base case is 2,

$$\left. \begin{matrix} P(2) \\ P(3) \\ \vdots \\ P(n - 1) \end{matrix} \right\} \longrightarrow \quad P(n)$$

Now for the choice of $n$, we have two possibilities,

1. $n$ is prime, meaning that it's prime factorisation is simply $n = n.$
2. $n$ is composite. In this case, $n$ can be written as $n=ab$, where $a,b$ are both integers larger than 1 and less than $n$. Since $a$ is greater than 1 and strictly less than $n$, this means that $a$ is a part of our inductive hypothesis,

$$\left. \begin{matrix} P(2) \\ \vdots \\ P(a) \\ \vdots \\ P(n - 1) \end{matrix} \right\} \longrightarrow \quad P(n)$$

in other words, $a$ has a unique prime factorisation. $b$ is also similarly strictly between 1 and $n$, meaning it also has a unique prime factorisation. We can combine the unique prime factorisations of $a$ and $b$ together to get the $n_{\text{th}}$ prime factorisation.

However, we haven't shown that the $n_{\text{th}}$ prime factorisation is unique, only that it exists.
Let's suppose that $n$ had two prime factorisations; it can be written in two ways:

$$n=p_{1}^{\alpha_1} p_{2}^{\alpha_2} p_{3}^{\alpha_3} \dots p_{k}^{\alpha_k} = q_{1}^{\beta_1} q_{2}^{\beta_2} q_{3}^{\beta_3} \dots q_{\ell}^{\beta_\ell}.$$

Where each $p_k,q_{\ell}$ are primes. Looking at $p_1$, we know that it divides $n$, $p_1 \mid n$, and therefore it divides one of the terms on the RHS, $p_1 \mid q_{1}^{\beta_1} q_{2}^{\beta_2} q_{3}^{\beta_3} \dots q_{\ell}^{\beta_\ell}$. Since all of our $q$ terms give us all of the prime factors of $n$, and $p_1$ is a prime factor of $n$, this means that $p_1$ must be equal to one of those $q$ terms. Suppose that it is equal to $q_i$, giving us

$$n=p_{1}^{\alpha_1} p_{2}^{\alpha_2} p_{3}^{\alpha_3} \dots p_{k}^{\alpha_k} = q_{1}^{\beta_1} \dots p_{1}^{\beta_i} \dots q_{\ell}^{\beta_\ell}.$$

If we divide both sides by $p_1$, we get

$$n > p_{1}^{\alpha_1-1} p_{2}^{\alpha_2} p_{3}^{\alpha_3} \dots p_{k}^{\alpha_k} = q_{1}^{\beta_1} \dots p_{1}^{\beta_i - 1} \dots q_{\ell}^{\beta_\ell}.$$

Since both statements are now smaller than $n$ but larger than $1$, the statements are a part of our inductive hypothesis and therefore must have a unique prime factorisation, meaning that both statements are identical. Since both of the expressions are identical, we can multiply both expressions by $p_1$ to get $n$, meaning that $n$ must have a unique prime factorisation.

This completes the proof.

Example. Find the prime factorisation of $1176$.
Peel off primes from smallest to largest;

$$\begin{align*} 1176 &= 2 \times 588 \\ &= 2^2 \times 294 \\ &= 2^3 \times 147 \\ &= 2^3 \times 3 \times 49 \\ &= 2^3 \times 3 \times 7^2. \end{align*}$$

Therefore, $1176 = 2^3 \cdot 3 \cdot 7^2$, and by the Fundamental Theorem of Arithmetic this is the only way to write $1176$ as a product of primes (the condition $p_1 < p_2 < \dots < p_k$ is what pins down the ordering, so we don't count $3 \cdot 7^2 \cdot 2^3$ as a "different" factorisation).

Example. Use the Fundamental Theorem of Arithmetic to prove that $\sqrt{2}$ is irrational.
Suppose, for contradiction, that $\sqrt{2} = \frac{p}{q}$ for some $p \in \mathbb{Z}, q \in \mathbb{Z}^+$. Squaring both sides and rearranging,

$$\begin{align*} 2 &= \frac{p^2}{q^2} \\ 2q^2 &= p^2. \end{align*}$$

Now count how many times the prime $2$ appears on each side. By the FTA, $p$ and $q$ each have a unique prime factorisation; say $2$ appears in them with exponents $\alpha$ and $\beta$ respectively (possibly $0$). Squaring doubles every exponent, so $2$ appears in $p^2$ exactly $2\alpha$ times — an even number of times — whilst it appears in $2q^2$ exactly $2\beta + 1$ times — an odd number of times. But $2q^2$ and $p^2$ are the same integer, so by uniqueness of the prime factorisation they must contain exactly the same number of $2$s. An even number can never equal an odd number, so we have a contradiction; hence $\sqrt{2}$ is irrational. $\blacksquare$

Basically, a perfect square must contain an even amount of every prime, and $2q^2$ is stuck with an odd amount of $2$s, so it can never be a perfect square. The exact same exponent-counting argument shows $\sqrt{3}, \sqrt{5}, \sqrt{6}, \dots$ are irrational; the FTA turns questions about irrationality into questions about parity.

To prove this theorem, we will use proof by contradiction.

Suppose that there are finitely many primes;

$$p_1,p_2,p_3 \dots p_n,$$

where $n \in \mathbb{Z}^+$. Consider the number

$$P = p_1 p_2 p_3 \dots p_n + 1.$$

By the Fundamental Theorem of Arithmetic, there is a prime $q$ such that

$$q \mid P \quad \text{and} \quad q \mid P - 1,$$

$q \mid P$ as every number must have a unique prime factorisation, and since $P$ is a product of every prime, $q$ definitely divides $P - 1$. Since it divides both $P$ and $P-1$, it must divide $P - (P - 1)$, or $1$, but if $q \mid 1$, that must mean $q$ is 1. However, 1 is not a prime number, and we assumed that $q$ is a prime. This is a contradiction, and hence our original assumption was false.

Example. A common trap is to think that Euclid's construction $P = p_1p_2p_3\dots p_n + 1$ always produces a prime. Show that this is false by considering the first six primes.

$$\begin{align*} P &= 2 \times 3 \times 5 \times 7 \times 11 \times 13 + 1 \\ &= 30030 + 1 \\ &= 30031 \\ &= 59 \times 509, \end{align*}$$

and both $59$ and $509$ are prime, so $30031$ is composite. This doesn't break the proof at all; the proof only needs some prime factor $q$ of $P$, and shows that $q$ cannot be on our supposedly complete list (since $q$ would divide both $P$ and $P - 1$). Here, $59$ and $509$ are indeed both missing from $\{2,3,5,7,11,13\}$, which is exactly the kind of "new prime" the argument promises.
Euclid's argument does not claim that $p_1p_2 \dots p_n + 1$ is prime; it only claims that its prime factors are new.