## Exercise 6.

1) Alice wants to color the integers between 2 and 8 (inclusive) using $k$ colors. She wishes that if $m$ and $n$ are integers between 2 and 8 such that $m$ is a multiple of $n$ and $m \neq n$, then $m$ and $n$ are of different colors. Determine the smallest integer $k$ for which Alice can color the integers $2,3, \ldots, 8$ using $k$ colors.
2) Alice wants to color the integers between 2 and 31 (inclusive) using $k$ colors. She wishes that if $m$ and $n$ are integers between 2 and 31 such that $m$ is a multiple of $n$ and $m \neq n$, then $m$ and $n$ are of different colors. Determine the smallest integer $k$ for which Alice can color the integers $2,3, \ldots, 31$ using $k$ colors.
Solution alternative $n^{\circ} 1$ We show, as in the previous case, that for the first question, at least 3 colors are needed and at least 4 in the second.

We propose here to generalize the previous coloring: we construct a coloring with the optimal number of colors to color the integers from 2 to $r$, with $r \geqslant 2$. Let $n \geqslant 2$, and let $n=p_{1}^{a_{1}} \times \cdots \times p_{k}^{a_{k}}$ be its prime factorization. We will color $n$ with the color $a_{1}+\cdots+a_{k}$ (note that since $n \geqslant 2$, we have $a_{1}+\cdots+a_{k} \geqslant 1$). Let's show that this coloring is correct: let $m \neq n$ be two integers such that $m$ divides $n$. Let $n=p_{1}^{a_{1}} \times \cdots \times p_{k}^{a_{k}}$ be its prime factorization. $m$ can necessarily be written in the form $m=p_{1}^{b_{1}} \times \cdots \times p_{k}^{b_{k}}$ with $b_{1} \leqslant a_{1}, \ldots b_{k} \leqslant a_{k}$. Since $m \neq n$, there must exist some $i$ such that $a_{i} \neq b_{i}$, hence $a_{i}>b_{i}$. Thus, we must have $a_{1}+\cdots+a_{k}>b_{1}+\cdots+b_{k}$, so $m$ and $n$ are indeed of different colors.

If $n \leqslant 8$ and $n=p_{1}^{a_{1}} \times \cdots \times p_{k}^{a_{k}}$, then $2^{3}=8 \geqslant n \geqslant 2^{a_{1}+\cdots+a_{k}}$ so $a_{1}+\cdots+a_{k} \leqslant 3$. The coloring uses at most 3 colors for the integers from 2 to 8, so for the first question, the minimal $k$ is 3.

If $n \leqslant 31$ and $n=p_{1}^{a_{1}} \times \cdots \times p_{k}^{a_{k}}$, then $2^{5}=32>n \geqslant 2^{a_{1}+\cdots+a_{k}}$ so $a_{1}+\cdots+a_{k}<5$ and since $a_{1}+\cdots+a_{k}$ is an integer, we have $a_{1}+\cdots+a_{k} \leqslant 4$. The coloring uses at most 4 colors for the integers from 2 to 31, so for the second question, the minimal $k$ is 4.