Exercise 6. Find the largest integer $n \geqslant 3$, satisfying:

"for all integers $k \in\{2,3, \cdots, \mathrm{n}\}$ if $k$ and $\mathrm{n}$ are coprime then $\mathrm{k}$ is a prime number."
## Solution.

First, we notice that \( n = 30 \) satisfies the property. Indeed, if \( 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 \( k = \ell m \) with \( \ell, m > 1 \). Since \( \ell \) and \( m \) are coprime with \( n \), they are coprime with \( 2, 3, 5 \), so \( \ell, m \geq 7 \), which implies that \( k \geq 7 \times 7 = 49 > n \).

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

Let \( p_1, p_2, \ldots, p_k \) be the primes dividing \( n \). Since \( p \geq 11 \), we have \( p_1, p_2, \ldots, p_k \leq 7 \). Therefore, \( n \geq p_1 p_2 \cdots p_k \), which contradicts Bonse's inequality.

Remark: If we do not know Bonse's inequality, we can easily derive it from Bertrand's postulate, which states that \( p_{j+1} < 2p_j \). This implies that \( p_{n+1} < 2p_n \), and by induction, \( p_{n+1} < 2^n p_1 \). Since \( p_1 = 2 \), we have \( p_{n+1} < 2^{n+1} \).

Suppose, for the sake of contradiction, that there exists \( n \geq 8 \) such that \( p_1 p_2 \cdots p_n \leq p_{n+1}^2 \). Let \( m = \left\lfloor \frac{n}{2} \right\rfloor \). We have

\[
\left(p_1 p_2 \cdots p_m\right)^2 < p_1 p_2 \cdots p_n \leq p_{n+1}^2
\]

so \( p_1 p_2 \cdots p_m < p_{n+1} \).

Consider the integers \( N_j = j p_1 p_2 \cdots p_{m-1} - 1 \) for \( 1 \leq j \leq p_m \). 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 \leq q_j \leq 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-1} \), so \( q_j \) divides \( \ell - j \), which is impossible since \( 1 \leq \ell - j < p_m \leq q_j \).

Therefore, there are at least \( p_m \) distinct primes between \( p_m \) and \( p_n \): in other words, \( p_m \leq n - m + 1 \). Since \( n \leq 2m + 1 \), we have \( p_m \leq m + 2 \).

Since \( p_m \geq 2m - 1 \) for all \( m \geq 1 \), this implies \( 2m - 1 \leq m + 2 \), so \( m \leq 3 \), and thus \( n \leq 7 \).

![](https://cdn.mathpix.com/cropped/2024_06_04_d74311deaed1ce0e1dceg-07.jpg?height=79&width=177&top_left_y=2069&top_left_x=974)