Determine all positive integers $n$ such that all positive integers less than or equal to $n$ and relatively prime to $n$ are pairwise coprime.
Problem
Source:
Tags: Divisibility, RMN
15.05.2018 19:54
Note that $n=1$ vacuously works, so for the remainder of the proof assume $n\geq 2$. Let $p$ denote the smallest prime not dividing $n$. Suppose $p\geq 11$. Then $2$, $3$, $5$, and $7$ all divide $n$, so $n\geq 2\cdot 3\cdot 5\cdot 7 = 210$. But now $p^2 < n$, and since $p$ and $p^2$ are not relatively prime we have a contradiction. It follows that $p\in\{2,3,5,7\}$. From here, we case. If $p=2$, then we just need $n < 4$. This guarantees $n=3$ is a valid solution. If $p=3$, then $2\mid n$ and $n < 9$. This gives $n=2,4,8$. If $p=5$, then we need $6\mid n$ and $n < 25$. This gives $n=6,12,18,24$. If $p=7$, then we need $30\mid n$ and $n<49$. This gives $n=30$. In conclusion, we have that $n\in\boxed{\{1,2,3,4,6,8,12,18,24,30\}}$.
22.06.2021 13:44
Clearly $n = 1$ works. Let $p_r$ denote the $r$ th prime number. For $k\geq 0$, let $p_{k+1}$ be the smallest prime not dividing $n$. Then, we have $n\geq p_1p_2 \dots p_k$. Also, clearly we must have $p_{k+1}^2 > n$. Now assume $k \geq 5$. We have $p_{k+1}^2 > p_1p_2 \dots p_k$. By Bertrand, we have $p_{k+1} < 2p_k$. So, $4p_k > p_1p_2 \dots p_{k-1}$. Again by Bertrand, we have $p_k < 2p_{k-1}$. Thus, $8 > p_1p_2 \dots p_{k-2}$, implying that $k-2 \leq 2 \implies k \leq 4$, contradiction. So we have $k \leq 4$. If $k = 0$, then $4 > n$, giving the solution $n = 3$. If $k = 1$, then $9 > n$ and $2 \mid n$, checking gives the solutions $n = 2,4,8$. If $k = 2$, then $25 > n$ and $6 \mid n$, so $n = 6,12,18,24$ are the solutions in this case. If $k = 3$, then $49 > n$ and $30 \mid n$, so $n = 30$ is the only solution here. If $k = 4$, then $121 > n$ and $210 \mid n$, so there are no solutions here. So only solutions are $n = 1,2,3,4,6,8,12,18,24,30$.
26.10.2024 09:59
We can get that $2 \mid n, 3 \mid n, 5 \mid n, 7 \mid n$ like above posts, with the solutions $n = 1, 2, 3, 4, 6, 8, 12, 18, 24, 30$ if not. Assume the first $k$ primes divide $n$. Note that $p_{k + 1}^2 < p_1\cdot p_2 \cdots p_k$ (an easy application of bertand's), and $p_{k + 1} < p_1 \cdots p_k$, so $p_{k + 1}$ must divide $n$ as well. Continuing like this, we get that all primes divide $n$.