## Sieve of Eratosthenes

### Multiples and divisors

Given a certain natural number, its multiples (in the set of natural numbers) are all numbers that are obtained by multiplying that number by $$1, 2, 3, 4, 5, ...$$, that is, by all natural numbers. To say that a number is a multiple of another one is equivalent to saying that the latter is a divisor of the former. With the same meaning, one also says that the former is divisible by the latter.

The set of multiples of a number is therefore an infinite set.

For example, the multiples of $$12$$ are obtained by multiplying $$12$$ by $$1, 2, 3, 4, 5, 6, ..., k, ...$$.

We can represent the set of multiples of $$12$$ as follows: $M_{12} = \{12, 24, 36, 48, 60, 72, … , 12 \times k, ... \}\;\;(k\mbox{ an arbitrary natural}).$

Thus, we can say that $$48$$ is a multiple of $$12$$, because there is an integer — $$4$$ — that multiplied by $$12$$ yields $$48$$. The statement "$$48$$ is a multiple of $$12$$" is equivalent to "$$48$$ is divisible by $$12$$" or to "$$12$$ is a divisor of $$48$$". The multiples of $$2$$ are the so-called even numbers $$2, 4, 6, 8, 10, 12, ...$$.

If a number is multiple of a second number and the latter is a multiple of a third number, then the first number is also a multiple of the third one. Equivalently, if a number is divisible by another one and the latter is divisible by a third number, then the first number is also divisible by the third one. This property can also be formulated using the term "divisor" instead of "divisible" or "multiple". Try to do it.

For example, a multiple of a multiple of $$10$$ is also a multiple of $$10$$. We have a similar situation for the multiples of a multiple of $$3$$ (or $$2$$). In particular, any multiple of an even number is even: $$14$$ is even (because $$14 = 7 \times 2$$), therefore $$5 \times 14$$ is also even (since it is $$= 5 \times (7\times 2) = (5 \times 7) \times 2$$ ).

Note that the previous property ensures that if a number is not divisible by a certain number, then it can not be divisible by any multiple of it. For example, if a number is not divisible by $$3$$, then it can not be divisible by any multiple of $$3$$, because, according to what we have just seen, if a number were divisible by any multiple of $$3$$, then it would also be divisible by $$3$$.

Note also that a natural number is a divisor of another given number if and only if the remainder of the (euclidean) division of the second number by the first one is zero. If this is the case, the division of the second number by the quotient obtained in the previous division necessarily has a remainder equal to zero, and therefore this quotient is also a divisor of the given number. For example, $$5$$ is a divisor of $$40$$ because $$40:5=8$$ (with remainder $$0$$), which means that $$40=5 \times 8$$ and, therefore, $$8$$ is also a divisor of $$40$$, with $$40:8=5$$ (with remainder $$0$$).

Unlike the set of multiples, the set of divisors of a number is a finite set, since no divisor can exceed the number.

It is important to note that $$1$$ is a divisor of all numbers, since any number divided by $$1$$ gives the number itself (with remainder zero). For the same reason, any number is a divisor of itself.

Let us see, with examples, how to determine the set of divisors of a natural number.