Find all positive integers $n$ such that for all positive integers $m$, $1<m<n$, relatively prime to $n$, $m$ must be a prime number.
Problem
Source: 2nd Final Mathematical Cup Senior Division P4 (2020)
Tags: number theory, relatively prime
01.10.2020 13:44
The answers are $\boxed{1, 2, 3, 4, 6, 8, 12, 18, 24, 30}$. For simplicity, we call such number cute. Claim. Let $\mathcal{P}$ be the set of primes dividing $n$. Let $q$ be the smallest prime number that is not an element of $\mathcal{P}$, then $n$ is cute if and only if $n < q^2$. Proof. If $n$ is cute, then there must be no composite number $pq$ where $p,q$ primes such that $(pq,n) = 1$. However, since we define $q$ be the smallest prime number not in $\mathcal{P}$, then $n < q^2$ as well, or otherwise $q^2$ satisfies $(q^2,n) = 1$. Now, if $n < q^2$, then all of the composite numbers less than $q^2$ must have a prime divisor in common with $\mathcal{P}$, we are done. Now, we'll use the statement above for our proof. Using the same definition, we want to find all cute $n$. Fix an integer $n$. Then it must satisfy \[ \prod_{p \in \mathcal{P}} p < q^2 \]Suppose $q = p_k \ge p_5$, by Bonne Theorem, we know that \[ \prod_{p \in \mathcal{P}} p \ge p_1 p_2 \dots p_{k - 1} > p_k^2 \]Thus, $q \le p_4 = 7$. If $q = 2$, then $n = 1, 3$. If $q = 3$, then $n$ is a multiple of $2$ less than $9$, giving $n = 2, 4, 6,8$. If $q = 5$, then $n$ is a multiple of $6$ less than $25$, giving $n = 6,12,18,24$. If $q = 7$, then $n$ is a multiple of $30$ less than $49$, giving $n = 30$. Remark. Bonne Theorem. Let $p_1 = 2 < p_2 = 3 < \dots$ be a sequence of prime numbers. Then for all $n \ge 4$, \[ p_1 p_2 \dots p_n > p_{n + 1}^2 \]The proof of this is not difficult by induction. Base check is easily checked to be true. Now, notice that by Bertrand postulate on $(p_{k + 1}, 2p_{k+1})$ for $k \ge 4$, we get the bound $p_{k + 2} < 2p_{k + 1}$. Thus, \[ \prod_{i = 1}^{k + 1} p_i = p_{k + 1} \cdot \prod_{i = 1}^k p_i > p_{k + 1} p_{k + 1}^2 > 4p_{k + 1}^2 = (2p_{k + 1})^2 > p_{k + 2}^2 \]
01.10.2020 13:57
IndoMathXdZ wrote: The answers are $\boxed{1, 2, 3, 4, 6, 8, 12, 18, 24, 30}$. For simplicity, we call such number cute. Claim. Let $\mathcal{P}$ be the set of primes dividing $n$. Let $q$ be the smallest prime number that is not an element of $\mathcal{P}$, then $n$ is cute if and only if $n < q^2$. Proof. If $n$ is cute, then there must be no composite number $pq$ where $p,q$ primes such that $(pq,n) = 1$. However, since we define $q$ be the smallest prime number not in $\mathcal{P}$, then $n < q^2$ as well, or otherwise $q^2$ satisfies $(q^2,n) = 1$. Now, if $n < q^2$, then all of the composite numbers less than $q^2$ must have a prime divisor in common with $\mathcal{P}$, we are done. Now, we'll use the statement above for our proof. Using the same definition, we want to find all cute $n$. Fix an integer $n$. Then it must satisfy \[ \prod_{p \in \mathcal{P}} p < q^2 \]Suppose $q = p_k \ge p_5$, by Bonne Theorem, we know that \[ \prod_{p \in \mathcal{P}} p \ge p_1 p_2 \dots p_{k - 1} > p_k^2 \]Thus, $q \le p_4 = 7$. If $q = 2$, then $n = 1, 3$. If $q = 3$, then $n$ is a multiple of $2$ less than $9$, giving $n = 2, 4, 6,8$. If $q = 5$, then $n$ is a multiple of $6$ less than $25$, giving $n = 6,12,18,24$. If $q = 7$, then $n$ is a multiple of $30$ less than $49$, giving $n = 30$. Remark. Bonne Theorem. Let $p_1 = 2 < p_2 = 3 < \dots$ be a sequence of prime numbers. Then for all $n \ge 4$, \[ p_1 p_2 \dots p_n > p_{n + 1}^2 \]The proof of this is not difficult by induction. Base check is easily checked to be true. Now, notice that by Bertrand postulate on $(p_{k + 1}, 2p_{k+1})$ for $k \ge 4$, we get the bound $p_{k + 2} < 2p_{k + 1}$. Thus, \[ \prod_{i = 1}^{k + 1} p_i = p_{k + 1} \cdot \prod_{i = 1}^k p_i > p_{k + 1} p_{k + 1}^2 > 4p_{k + 1}^2 = (2p_{k + 1})^2 > p_{k + 2}^2 \] I found the same solution but was wondering if a solution that doesn't use Bertrand's postulate or Bonne's Theorem exists.
01.10.2020 15:47
The correct source for this problem is Chapter 27 ("A property of the number 30") of the book "The Enjoyment of Mathematics" by Hans Rademacher and Otto Toeplitz, published in 1933 by Springer, Berlin.