## Sieve of Eratosthenes

### Divisors of a number - example I

For example, consider number $$48$$. What are its divisors?

$$48:1=48$$ (remainder $$0$$) $$\rightarrow$$ hence $$1$$ and $$48$$ are divisors of $$48$$
$$48:2=24$$ (remainder $$0$$) $$\rightarrow$$ hence $$2$$ and $$24$$ are divisors of $$48$$
$$48:3=16$$ (remainder $$0$$) $$\rightarrow$$ hence $$3$$ and $$16$$ are divisors of $$48$$
$$48:4=12$$ (remainder $$0$$) $$\rightarrow$$ hence $$4$$ and $$12$$ are divisors of $$48$$
$$48:5=9$$ (remainder $$3$$) $$\rightarrow$$ hence $$5$$ is not a divisor of $$48$$
$$48:6=8$$ (remainder $$0$$) $$\rightarrow$$ hence $$6$$ and $$8$$ are divisors of $$48$$
$$48:7=6$$ (remainder $$6$$) $$\rightarrow$$ hence $$7$$ is not a divisor of $$48$$

Up to know we have found the following divisors: $$1,2,3,4,6,8,12,16,24,48$$. In the last division the quotient is smaller than the divisor. This guarantees that we have already found all divisors.

Indeed, if we continue dividing $$48$$ by numbers greater than $$7$$, the quociente will be less than or equal $$6$$ and we already know what are the exact divisions by numbers less than or equal $$6$$: they are necessarily the divisions by $$8$$, $$12$$, $$16$$, $$24$$ and $$48$$, since these were the quotients obtained by dividing $$48$$ by all natural numbers less than or equal to $$6$$ that produced a remainder $$0$$).

We may then conclude that the divisors of $$48$$ are just the ones indicated above, $$1,2,3,4,6,8,12,16,24,48$$: $D_{48} = \{1, 2, 3, 4, 6, 8, 12, 16, 24, 48\}.$

This picture indicates all divisors of $$48$$, where an arrow from a

number to $$48$$ means that the number is a divisor of $$48$$. In particular, $$48$$ divides $$48$$, so there is an arrow from $$48$$ to itself.

Let us see one more example.