Find the largest integer $\mathrm{n} \geqslant 3$, satisfying:
"for all integers $k \in\{2,3, \cdots, \mathfrak{n}\}$ if $k$ and $\boldsymbol{n}$ are coprime then $k$ is a prime number."
First, we notice that $\mathrm{n}=30$ satisfies the property. Indeed, if $\mathrm{k}>1$ is coprime with $n$, then it is coprime with $2,3,5$. If, in addition, $k$ is not prime, then it admits a non-trivial factorization $\mathrm{k}=\mathrm{lm}$ with $\ell, \mathrm{m}>1$. Since $\ell$, $m$ are coprime with $n$, they are coprime with $2,3,5$, so $\ell$, $\mathrm{m} \geqslant 7$, which implies that $k \geqslant 7 \times 7=49>n$.

Conversely, let's show that if $n$ satisfies the property, then $n \leqslant 30$. Suppose, for the sake of contradiction, that $n>30$. Let $p$ be the smallest prime not dividing $n$. Since $p^{2} n$ is not prime but is coprime with $n$, we have $p^{2}>n>30>5^{2}$, so $p \geqslant 7$. In particular, 2, 3, and 5 divide $n$, so 30 divides $n$. Since $\mathrm{n}>30$, we deduce that $\mathrm{p}^{2}>\mathrm{n} \geqslant 60>7^{2}$, so $\mathrm{p}>7$, hence $\mathrm{p} \geqslant 11$.

Let $p_{1}n \geqslant p_{1} \cdots p_{k}$, which contradicts Bonse's inequality.

Remark: if one does not know Bonse's inequality, it can be easily derived from Bertrand's postulate, which states that $\boldsymbol{p}_{j+1}p_{n+1}^{2}$.

Suppose, for the sake of contradiction, that there exists $n \geqslant 8$ such that $p_{1} p_{2} \cdots p_{n} \leqslant p_{n+1}^{2}$. Let $m=\left[\frac{n}{2}\right]$. We have

$$
\left(p_{1} p_{2} \cdots p_{m}\right)^{2}<p_{1} p_{2} \cdots p_{n} \leqslant p_{n+1}^{2}
$$

so $\mathrm{p}_{1} \mathrm{p}_{2} \cdots \mathrm{p}_{\mathrm{m}}<\mathrm{p}_{\mathrm{n}+1}$.
Consider the integers $N_{j}=j p_{1} p_{2} \cdots p_{m-1}-1\left(1 \leqslant j \leqslant p_{m}\right)$. For all $j$, we have $N_{j}<p_{1} p_{2} \cdots p_{m}<$ $p_{n+1}$ and $N_{j}$ is coprime with $p_{1}, p_{2}, \ldots, p_{m-1}$. Therefore, if $q_{j}$ is the smallest prime dividing $N_{j}$, we have $p_{m} \leqslant q_{j} \leqslant p_{n}$.

The $q_{j}$ are distinct because if $j<\ell$ and $q_{j}=q_{\ell}$, then $q_{j}$ divides $N_{\ell}-N_{j}=(\ell-j) p_{1} p_{2} \cdots p_{m}$, so $q_{j}$ divides $\ell-\mathfrak{j}$, which is impossible since $1 \leqslant \ell-\mathfrak{j}<p_{m} \leqslant q_{j}$.

Therefore, there are at least $p_{m}$ distinct primes between $p_{m}$ and $p_{n}$: in other words, $p_{m} \leqslant n-m+1$. Since $n \leqslant 2 m+1$, we have $p_{m} \leqslant m+2$.

Since $p_{m} \geqslant 2 m-1$ for all $m \geqslant 1$, this implies $2 m-1 \leqslant m+2$, so $m \leqslant 3$, and thus $n \leqslant 7$.
![](https://cdn.mathpix.com/cropped/2024_12_06_5f9dc6f56d060e9d13aeg-07.jpg?height=82&width=191&top_left_y=2073&top_left_x=967)