# 1. The definition of prime number

We start our study of prime numbers explaining the definition of prime number. What’s commonly known is that a prime number is a positive integer number divisible only by itself and 1. This is true except for number 1, that according to that should be prime (1 is divisible by 1, which is also the number itself), but indeed it isn’t. Number 1 in fact is a priori excluded from prime numbers. The reason is related to a theorem, known as the Foundamental Theorem of Arithmetic:

Fundamental theorem of arithmetic

Every integer number greater than 1 can be written as a product of prime numbers. Moreover such expression, called factorization or decomposition into prime factors, is unique apart from the order of the factors.

If 1 was considered prime, this theorem would not be true in its current form and it should be expressed differently, adding an exception. As a consequence, a myriad of theorems that, directly or not, depend from it should be modified in turn, introducing some often unconvenient exceptions… indeed the most simple solution is assuming that 1 is not prime.

The product mentioned in the statement of the Foundamental Theorem of Arithmetic can be made up of any number $k$ of prime factors, not necessarily distinct. For example $12 = 2 \cdot 2 \cdot 3$ is the product of $k = 3$ prime numbers. Usually a product is defined for at least $k = 2$ factors, however for the theory we are getting ready to develop, it will be convenient to extend the idea of product including the case of the product with just one factor ($k = 1$), which is the factor itself. With this assumption, a prime number il also a product of prime numbers: a special product, made up of the number itself that multiplies no other number. For example, here are the factorizations of numbers from 2 to 10:

Number Factorization Number of factors
2 2 1
3 3 1
4 $2 \cdot 2$ 2
5 5 1
6 $2 \cdot 3$ 2
7 7 1
8 $2 \cdot 2 \cdot 2$ 3
9 $3 \cdot 3$ 2
10 $2 \cdot 5$ 2

The fundamental Theorem of arithmetic states not only that every integer number greater than 1 has a factorization into prime factors, but also that this factorization is unique except for the order of the factors. For example, $12 = 2 \cdot 2 \cdot 3$ and there are no other prime numbers, apart from 2 taken two times and 3 taken one time, that multiplied between themselves make 12. The unicity of the factorization is a fundamental property that is at the base of many theorems of number theory, and it’s right here that we can understand why 1 is not considered a prime number. In fact, if 1 was prime, every positive integer would have infinite factorization into prime numbers. For example

$$10 = 5 \cdot 2 = 5 \cdot 2 \cdot 1 = 5 \cdot 2 \cdot 1 \cdot 1 = 5 \cdot 2 \cdot 1 \cdot 1 \cdot 1 = \dots.$$

In order to avoid this, and to be certain to always have a unique factorization, 1 is not considered prime. For this reason the fundamental theorem of arithmetic holds for integers greater than 1: it cannot hold for 1, because it’s not prime and is only the product of itself, so it’s not a product of primes.

Having excluded the number 1 from prime numbers, we can state a correct definition of prime number:

Prime number, first definition

A prime number is an integer number greater than 1, which is divisible obly by itself and 1.

This definition refers to the concept of divisibility, which is worth to point out:

Divisibility

An integer $a$ is divisible by an integer $b$, with $b \neq 0$, if $a = b c$ for some integer $c$.
If $a$ is divisible by $b$ we write $b \mid a$ (“$b$ divides $a$“), otherwise we write $b \nmid a$ (“$b$ does not divide $a$“).

For example, 10 is divisible by 2 because it can be written as $10 = 2 \cdot 5$, where 5 is an integer $c$ such that $10 = 2 \cdot c$. On the contrary, 10 is not divisible by 3 because there isn’t any integer $c$ such that $10 = 3 \cdot c$. In other terms, we can say that 2 divides 10 ($2 \mid 10$) and 3 doesn’t divide 10 ($3 \nmid 10$).

Definition N.2 doesn’t contemplate the case of $b = 0$, so it remains undefined whether a number is divisible by 0 or not.

Here the exclusion of a particular case from a general definition is for a good reason as before, for the purpose of preserving some fundamental and convenient properties, which aren’t valid for the excluded case. In fact we can observe that the number $c$ is univocally determined when $a$ and $b$ have been fixed (with the fraction notation we can write $c = \frac{a}{b}$), which is not true if a = b = 0. In this case in fact we have $0 = 0 c$ for any integer $c$ and not for a specific one. Indeed, for the purpose of guaranteeing the unicity of $c$, it would be enough to exclude from the definition just the case of $a$ and $b$ both 0, instead of $b = 0$: this point could be examined further, but certainly is a matter of secondary importance.

Divisibility has a lot to do with the factorization into prime numbers: in fact, if $b \mid a$ – that is $a = b c$ for some integer $c$ – it means that somehow $b$ is present in the factorization of $a$, as a prime or as a product of primes. For example:

• $2 \mid 10$ and 2 is present in the factorization of 10 as a prime number: $10 = \mathbf{2} \cdot 5$;
• $6 \mid 24$ and 6 is present in the factorization of 24 as a product of primes: $24 = 2 \cdot 2 \cdot \mathbf{2 \cdot 3}$;
• Also $8 \mid 24$ and 8 is present in the factorization of 24 as a product of primes: $24 = \mathbf{2 \cdot 2 \cdot 2} \cdot 3$;

So if $b \mid a$ it means that the factorization of $b$ is contained into the factorization of $a$. In particular, if a prime number $p \mid a$, $p$ must be one of the primes of the factorization of $a$. For example, if $a = p_1 p_2$, with $p_1$ and $p_2$ primes, it must be $p = p_1$ or $p = p_2$. This simple property characterizes prime numbers so strongly that, if conveniently generalized, it can be taken as an alternative definition of prime number:

Prime number, second definition

A prime number is an integer number $p > 1$ such that, if $p \mid bc$, then $p \mid b$ or $p \mid c$, for any integers $b$ and $c$. In other terms, $p$ cannot divide a product of integers $bc$ without dividing at least one of the two factors.

To understand this definition, let’s call $a$ the number $bc$ and let’s factorize it into prime factors: for example if $b = 6$ and $c = 10$, $a = 60$ and we have

$$60 = 2 \cdot 2 \cdot 3 \cdot 5$$

But since 60 is the product of 6 and 10, we can reorder its factorization in such a way to find the prime factors of 6 and those of 10:

(1)
$$60 = \underbrace{2 \cdot 3}_{6} \cdot \underbrace{2 \cdot 5}_{10}$$

For the reasoning above, if $p$ is a prime number dividing 60, $p$ must be present in its factorization (that is $p = 2$ or $p = 3$ or $p = 5$); but then, for how we subdivided it, $p$ can be present in the factorization of 6 (that is $p = 2$ or $p = 3$), and in that case it would divide 6, or it can be present in the factorization of 10 (that is $p = 2$ or $p = 5$), and in that case it would divide 10. Possibly $p$ can be present in both factorizations, as the case of $p = 2$, but it must be present at least in one of them. To better understand this, we can imagine to apply the following algorithm: we scan the list of the prime factors of 60 in the ordering of (1): 2, 3, 2, 5; if we find $p$ in the first two positions, we say that $p \mid 6$; otherwise we say that $p \mid 10$. In this way, if $p$ isn’t a divisor of 60 we won’t find it and we won’t say anything; if instead $p \mid 60$ we will find it in one or more positions and we’ll say at least one utterance between “$p \mid 6$” and “$p \mid 10$“.
It’s also interesting to observe what happens in the case of a not prime number (which is called a composite number), like 4. We have that $4 \mid 60$, so the factorization of 4 must be contained in that of 60. But 4 isn’t prime, so 4 cannot be present in the factorization of 60 as a prime number, but it must be present in the form of a product of prime numbers. This is the reason why 4 divides 60 without dividing 6 and 10, how you can see highlighting the prime factors of 4 ($2 \cdot 2$) in (1):

(2)
$$60 = \underbrace{\mathbf{2} \cdot 3}_{6} \cdot \underbrace{\mathbf{2} \cdot 5}_{10}$$

We can see that the number 4 “breaks” into a 2 appearing among the divisors of 6, and another 2 among the divisors of 10: therefore 4 does not divide either 6 or 10, but it divides their product 60. this cannot happen with a prime number, because a prime number cannot “break” between the factors $b$ and $c$: it must appear “intact” inside one of them.

Tha last example is represented graphically in the picture below: Second definition of prime number: if a prime number (3) divides a product of two factors (6 * 10 = 60), it divides at least one of them (3 | 6). A non-prime number (4) can insted divide such a product (6 * 10 = 60) without dividing any of the two factors.

## Infinity of prime numbers

An important theorem, well known since ancient times, which is a consequence of the definitions above and the Foundamental Theorem of Arithmetic, is the following:

Infinity of prime numbers

The number of primes is infinite.

The proof is so famous and simple that it’s worth to remember it. Let’s suppose that only a finite number $N$ of prime numbers exists. In this case, we could list all the prime numbers in increasing order: $p_1, p_2, \ldots, p_N$, where $p_N$ is the biggest prime number. So, starting from this list of prime numbers, we can construct the number

$$M := p_1 p_2 \ldots p_N + 1 \tag{3}$$

For how it’s defined, this number is not divisible by any of the primes $p_1, p_2, ..., p_N$.

Let’s ask ourselves the question: which prime numbers $M$ is divisible by? Let’s see if for example it’s divisible by $p_1$. If it was, by Definition N.2 (Divisibility) an integer $c$ would exist, such that

$$c \cdot p_1 = M = p_1 p_2 \ldots p_N + 1 \tag{4}$$

Hence, gathering $p_1$:

$$p_1 (c - p_2 \ldots p_N) = 1$$

So, again by Definition N.2, $p_1 \mid 1$. Then $p_1$ could be only +1 or -1; but this is not possible because prime numbers, by Definition N.1, must be greater than 1. This means that the hypothetical number $c$ of equation (4) cannot exist, i.e. $M$ is not divisible by $p_1$.
The argument above does not depend on the choice of $p_1$, in fact it may be repeated also for all the other primes $p_2, \ldots, p_N$, with the result that $M$ is not divisible by any of the primes $p_1, p_2, \ldots, p_N$.

Then $M$, by the Foundamental Theorem of Arithmetic, must be prime.

By the Foundamental Theorem of Arithmetic, $M$ is expressible as a product of prime numbers. So, if it wasn’t prime, it would be equal to the product of at least two prime numbers. In that case, however, each prime appearing in the factorization of $M$ would divide $M$ (for example, if $M = p_1 p_3$, by Definition N.2 we would have that $p_1 \mid M$ and $p_2 \mid M$). But this would be in contrast with the fact that $M$ is not divisible by any prime number.

But, being all primes greater than 1, we have that $M = p_1 p_2 \ldots p_N + 1 \gt p_N + 1 \gt p_N$. So we have reached the contraddiction that $M$ is a prime number greater than the greatest prime number, which is $p_N$. This means that the initial hypothesis, that only a finite number of prime numbers exists, is wrong: there are infinitely many prime numbers.

The proof above is very ancient, tracing back to Euclid (IV – III century B.C.). The mathematician Paul Erdős considered it so well made, that he affirmed it comes “directly from the Book”, referring to an hypothetical book, kept by God, in which there are all the theorems with their most beautiful proofs.