Check out the discovery

They are 2, 3, 5, 7, 11, 13, 17 and 19. By 20, the compounds have already been eliminated in these two steps. 1 does not enter: it only has a positive divisor.

In this post we will talk about prime numbers. To do this, we will use the concept of multiples of a natural number or composite numbers. The Greeks before Christ studied the theory of prime numbers through the Sieve of Eratosthenes.

Help us build the math website. Donate as much as you can.

Rectangles laboratory

Choose 12 objects and try 1, 2, 3, 4, 5 and 6 rows. What choices leave the rows with the same number? Then investigate 13: what changes?

Change objects and rows. A divider allows you to form equal rows without remainder.
Check out the investigation

The divisors of 12 are 1, 2, 3, 4, 6, and 12. 13 only has 1 and 13 as positive divisors: it is prime. Control goes up to 12 rows; draw the 13 rows with one object each to complete the investigation.

Property of divisors of natural numbers

In summary of previous posts we saw that natural numbers are given by:

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

When calculating the division of natural numbers, this result may be exact. In this way, we find a divisor of this natural number. To start with the properties of the divisors, we define:

Definition: The set of divisors of the natural number $n$ is given by:

$$\mathcal{D}(n)$$

Divisors of a natural number

Twelve points in rectangles of 1 by 12, 2 by 6, and 3 by 4.
What numbers divide 12? Each rectangle reveals a pair of dividers.

With the definition in hand, we can construct the set of divisors of the natural number $n$:

Natural number $(n)$ $\mathcal{D}(n)$ Dividers
0 $\mathcal{D}(0)$ $ \\{ 1,2, 3, 4, \dots \\} $
1 $\mathcal{D}(1)$ $ \\{ 1 \\} $
2 $\mathcal{D}(2)$ $ \\{ 1,2 \\} $
3 $\mathcal{D}(3)$ $ \\{ 1,3 \\} $
4 $\mathcal{D}(4)$ $ \\{ 1,2,4 \\} $
5 $\mathcal{D}(5)$ $ \\{ 1,5 \\} $
6 $\mathcal{D}(6)$ $ \\{ 1,2,3,6 \\} $
7 $\mathcal{D}(7)$ $ \\{ 1,7 \\} $
8 $\mathcal{D}(8)$ $ \\{ 1,2,4,8 \\} $
9 $\mathcal{D}(9)$ $ \\{ 1,3,9 \\} $
10 $\mathcal{D}(10)$ $ \\{ 1,2,5,10 \\} $
11 $\mathcal{D}(11)$ $ \\{ 1,11 \\} $

Properties

Dividers have some properties. Below we present some of them:

  1. The numbers 1 and $n$ always belong to the set of divisors of the natural number $n$. It is worth remembering that n is different from zero.
$$1, ~n \in \mathcal{D}(n) \quad n\neq 0$$

In fact, for every natural number $n>0$ we have:

$$n = 1~.~n$$

Therefore, the number 1 is a divisor of the natural number $n$, the same goes for $n$.

From the table we built, we note that this property is valid.

  1. If $n>0$ and $m$ belongs to the divisors of $n$, i.e. $m\in\mathcal{D}(n).$ Then $m$ is less than or equal to $n,$ i.e. $m\leq n$.

Prime number definition

In this way, we can define prime numbers.

Definition: If $p$ is prime, then the set of divisors of prime numbers are $1$ and $p,$ more specifically

$$\mathcal{D}(p) = \\{1,p\\}$$

Thus, the prime numbers in the table above are:

Natural number $(n)$ $\mathcal{D}(n)$ Dividers
2 $\mathcal{D}(2)$ $ \\{ 1,2 \\} $
3 $\mathcal{D}(3)$ $ \\{ 1,3 \\} $
5 $\mathcal{D}(5)$ $ \\{ 1,5 \\} $
7 $\mathcal{D}(7)$ $ \\{ 1,7 \\} $
11 $\mathcal{D}(11)$ $ \\{ 1,11 \\} $

If a non-zero number $b$ $(b\neq 0)$ is a divisor of a natural number $a,$ then there exists a natural number $q$ such that $a=bq.$ We construct this as follows:

$$ \begin{aligned} a & |\underline{}\underline{b}\underline{}\\ 0 & \quad q\\ \end{aligned} $$

Note that:

  • if the remainder $r$ is zero, then $b$ is a divisor of $a$ or $a = bq$.
  • if the remainder $r$ is not zero, then $b$ is not a divisor of $a$ or $a = bq + r$.

In the post about odd and even numbers we saw that they can be written as:

  • pair $n = 2 q$
  • odd $n = 2 q + 1$

In particular,

  • every even natural number $n$ is a multiple of 2.
  • the only even prime is 2.

With this, a multiple number is constructed from a prime number:

$$n = p q$$

in which

  • $p$ is a prime number.
  • $n$ is any natural number.
  • $q$ is a multiple of the prime number $p$.

Composite Numbers

Prime factor tree of 36.
Follow the branches to the primes. Why is 36 composite?

Therefore, we can define composite numbers:

Definition: If $p$ is prime and a number $a$ can be constructed by a multiple of a prime. So this number is composite.

Prime number $(p)$ Composite number $(a=pq)$ Set of composite numbers $(n)$
2 $a = 2 q$ $ \\{ 2, 4, 6, 8, \dots \\} $
3 $a = 3 q$ $ \\{ 3, 6, 9, 12, \dots \\} $
5 $a = 5 q$ $ \\{ 5, 10, 15, 20, \dots \\} $
7 $a = 7 q$ $ \\{ 5, 10, 15, 20, \dots \\} $
11 $a = 11 q$ $ \\{ 11, 22, 33, 44, \dots \\} $

Sieve of Eratosthenes

Table of numbers from 1 to 30 with primes highlighted.
Find the cousins. Note that 1 is neither prime nor composite.
C R I V O
$2$ $3$ $4$ $5$
$6$ $7$ $8$ $9$ $10$
$11$ $12$ $13$ $14$ $15$
$16$ $17$ $18$ $19$ $20$
$21$ $22$ $23$ $24$ $25$
$\vdots$ $\vdots$ $\vdots$ $\vdots$ $\vdots$
  1. The first prime is 2, as there is no number greater than 1 and smaller than it that is its divisor. So let’s sift through the multiples of 2.
C R I V O
$2$ $3$ $\cancel{4}$ $5$
$\cancel 6$ $7$ $\cancel 8$ $9$ $\cancel{10}$
$11$ $\cancel{12}$ $13$ $\cancel{14}$ $15$
$\cancel{16}$ $17$ $\cancel 18$ $19$ $\cancel 20$
$21$ $\cancel{ 22}$ $23$ $\cancel{ 24}$ $25$
$\vdots$ $\vdots$ $\vdots$ $\vdots$ $\vdots$
  1. The second prime is 3, as there is no number greater than 1 and smaller than it that is its divisor. So let’s sift through the multiples of 3.
C R I V O
$2$ $3$ $\cancel{4}$ $5$
$\cancel{\cancel{ 6}}$ $7$ $\cancel 8$ $\cancel{9}$ $\cancel{10}$
$11$ $\cancel{\cancel 12}$ $13$ $\cancel{14}$ $\cancel{\cancel 15}$
$\cancel{16}$ $17$ $\cancel{\cancel 18}$ $19$ $\cancel 20$
$\cancel{21}$ $\cancel{ 22}$ $23$ $\cancel{\cancel 24}$ $25$
$\vdots$ $\vdots$ $\vdots$ $\vdots$ $\vdots$
  1. The third prime is 5, as there is no number greater than 1 and smaller than it that is its divisor. So let’s sift through the multiples of 5.
C R I V O
$2$ $3$ $\cancel{4}$ $5$
$\cancel{\cancel{ 6}}$ $7$ $\cancel{ 8}$ $\cancel{9}$ $\cancel{\cancel 10}$
$11$ $\cancel{\cancel 12}$ $13$ $\cancel{14}$ $\cancel{\cancel 1 \cancel 5}$
$\cancel{16}$ $17$ $\cancel{\cancel 18}$ $19$ $\cancel{\cancel 20}$
$\cancel{21}$ $\cancel{ 22}$ $23$ $\cancel{\cancel 24}$ $\cancel{25}$
$\vdots$ $\vdots$ $\vdots$ $\vdots$ $\vdots$
  1. The fourth prime is 7, as there is no number greater than 1 and smaller than it that is its divisor. The 7 sieve will remain as an exercise.

Therefore, the result is prime numbers. This way we obtain the table:

C R I V O
$2$ $3$ $5$
$7$
$11$ $13$
$17$ $19$
$23$
$\vdots$ $\vdots$ $\vdots$ $\vdots$ $\vdots$

These are some points about the theory of prime numbers. In the pure mathematics book (university students) we will talk in more detail.

Eratosthenes’ sieve: cross out the multiples of each cousin. The remaining numbers are primes.